Historical Context & Motivation
The idea of accumulating partial sums to accelerate repeated queries has deep roots in both mathematics and computer science. Long before the term prefix sum became standard vocabulary in algorithm design, mathematicians relied on cumulative distribution functions and running totals in statistical tables — essentially the same principle applied by hand. In the context of computing, the technique gained prominence as researchers confronted the fundamental tension between preprocessing cost and query-time efficiency. When an application must answer thousands or millions of range queries over a static array, a brute-force summation for each query quickly becomes the bottleneck.
The core question this lesson addresses is straightforward: given an integer array of length n and q queries each requesting the sum of elements in a contiguous subarray, how can we avoid the naïve O(n × q) total cost? The prefix-sum technique provides an elegant answer — O(n) preprocessing followed by O(1) per query — and it forms the conceptual foundation for more advanced structures such as Fenwick trees and segment trees.
Core Principles & Definitions
At its heart, the prefix-sum pattern exploits a property of addition that computer scientists often take for granted: subtraction of overlapping sums isolates any contiguous subarray. By building a single auxiliary array that stores cumulative totals, every subsequent range query reduces to one subtraction. The following cards distill the foundational ideas you need before diving into implementation.
Prefix Array Construction
Range Query Formula
Zero-Indexed Convention
Time–Space Trade-off
Static Array Assumption
Visual Explanation
Building the Prefix-Sum Array
Observe that every entry P[i] records the sum of A[0] through A[i−1]. The sentinel value P[0] = 0 ensures the formula sum(l, r) = P[r+1] − P[l] works uniformly, even when the query starts at index 0. This is why the idiomatic C++ implementation allocates a vector of size n + 1 rather than n. The construction loop is straightforward: P[i+1] = P[i] + A[i] for i from 0 to n−1.
Mathematical Framework
Formalizing the prefix-sum construction and query formula clarifies both correctness and complexity. Let A be a zero-indexed array of n integers. We define the prefix-sum array P of length n + 1 as follows.
A subtle but important numerical consideration arises for large inputs: because the prefix array accumulates sums, P[n] can grow as large as n × max(|A[i]|). For an array of 105 elements each up to 109, P[n] can reach 1014, which overflows a 32-bit integer. In C++ you should use long long (or int64_t) for the prefix array when element magnitudes and array size combine to exceed 231 − 1 ≈ 2.1 × 109.
C++ Implementation & Breakdown
A clean, idiomatic C++ implementation typically consists of two functions (or a single class): one to construct the prefix array and another to answer queries. Below is the canonical pattern using std::vector<long long> to avoid overflow.
C++17 also provides std::partial_sum (from <numeric>) and std::inclusive_scan / std::exclusive_scan which accomplish the same construction with a single STL call. The choice of exclusive_scan with an initial value of 0 produces the sentinel-based prefix array directly.
std::exclusive_scan(A.begin(), A.end(), P.begin(), 0LL); produces P[0..n−1] where P[0]=0. Note this writes only n values; you still need P[n] = P[n−1]+A[n−1] if you follow the n+1 convention.Worked Example
Suppose you are given the array A = [3, −2, 7, 1, 5, −4, 6] (n = 7) and must answer three range-sum queries: sum(0, 3), sum(2, 5), and sum(4, 6). We walk through the complete process below.
P = [0, _, _, _, _, _, _, _]P = [0, 3, 1, 8, 9, 14, 10, 16]All three queries resolved in O(1) each, and the total work was O(n) for the build plus O(1) × 3 = O(3). Had we summed each subarray from scratch, the total would have been O(4 + 4 + 3) = O(11) additions — worse by a factor that grows linearly with the number and size of queries.
Strengths, Limitations & Comparisons
| Criterion | Prefix Sum | Brute Force |
|---|---|---|
| Preprocessing | O(n) | None |
| Query time | O(1) | O(n) |
| Total for q queries | O(n + q) | O(n × q) |
| Extra space | O(n) | O(1) |
| Supports updates? | No — must rebuild | Yes — always fresh |
| Implementation complexity | Very low | Trivial |
The prefix-sum approach dominates whenever the array is static and the number of queries is non-trivial. Its main limitation — the inability to handle point updates efficiently — is precisely what motivates upgrading to a Fenwick tree (Binary Indexed Tree) which supports both updates and queries in O(log n), or a segment tree which additionally handles non-commutative operations and lazy propagation. Understanding the prefix-sum pattern is therefore not just useful in isolation; it is the conceptual prerequisite for these more powerful structures.
Connection to Advanced Techniques
The 1-D prefix-sum idea generalizes in several powerful directions. In two dimensions, a 2-D prefix sum (also called a summed-area table or integral image) enables O(1) queries for the sum over any rectangular sub-region of a matrix, at the cost of O(m × n) preprocessing. The technique also extends to prefix XOR, prefix GCD, and prefix products, provided the operation has an inverse (or a suitable cancellation rule). In the competitive programming domain, the difference array is the dual construction: it allows O(1) range updates with a deferred O(n) reconstruction via prefix-sum at the end.
| Technique | Build | Query | Update |
|---|---|---|---|
| 1-D Prefix Sum | O(n) | O(1) | O(n) rebuild |
| 2-D Prefix Sum | O(m×n) | O(1) | O(m×n) rebuild |
| Difference Array | O(n) | O(n) reconstruct | O(1) range add |
| Fenwick Tree (BIT) | O(n) | O(log n) | O(log n) |
| Segment Tree | O(n) | O(log n) | O(log n) |
As you advance through competitive programming and algorithm courses, you will encounter scenarios where the simple prefix-sum array is the optimal tool (static data, sum queries), and others where you need the logarithmic flexibility of tree-based structures. Mastering the prefix-sum pattern first ensures you can recognize when the simpler technique suffices, avoiding unnecessary implementation complexity.
Practice Problems
Summary
The prefix-sum pattern transforms repeated range-sum queries on a static array from O(n) per query to O(1) per query after a single O(n) preprocessing pass. The auxiliary array P of size n+1 stores cumulative sums, with the sentinel P[0] = 0 ensuring the formula sum(l, r) = P[r+1] − P[l] applies uniformly to all valid ranges.
Key implementation concerns include using long long to prevent overflow and recognizing that this technique assumes a static (non-updating) array. When updates are required, the natural next step is to study Fenwick trees and segment trees, both of which build on the cumulative-sum intuition established here. The pattern also extends to 2-D prefix sums (summed-area tables) and difference arrays for range-update problems.