Prefix Sum Explained
Answering thousands of range-sum queries by looping over each range is a quadratic waste. Precompute the running total once and every range collapses to a single subtraction — the same trade you make when you keep a running balance instead of re-adding every transaction. The idea takes a minute; the indexing takes longer.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int main() {
vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
int n = a.size();
vector<int> pre(n + 1, 0);
for (int i = 0; i < n; i++) {
pre[i + 1] = pre[i] + a[i];
}
int l = 2, r = 5;
cout << pre[r + 1] - pre[l] << endl;
l = 0; r = 3;
cout << pre[r + 1] - pre[l] << endl;
return 0;
}Uses a size n+1 prefix array with a leading zero, so a range query needs no special case for l = 0.
How it works, step by step
pre[i] is the sum of the first i elements
Note it is the first i, not up to index i. pre[0] = 0 (sum of nothing), pre[1] = a[0], pre[3] = a[0]+a[1]+a[2]. Getting this definition precise up front is what prevents every downstream off-by-one.
Building it is one pass
Each entry is the previous entry plus one new element, so the whole table costs O(n) and a single addition per element. There is no cleverness here; the cleverness is in what it enables.
A range is a difference of two prefixes
The sum of a[l..r] equals everything up to r minus everything before l, which is pre[r+1] - pre[l]. The elements before l are counted in both terms and cancel exactly, leaving the window you asked for.
The leading zero removes the edge case
With a size-n array where pre[i] includes a[i], the query for l = 0 has nothing to subtract and needs an if. The extra slot makes pre[0] = 0 a valid thing to subtract, so one formula covers every range including the whole array.
It generalises past sums
Any operation with an inverse works: XOR prefixes answer range-XOR queries, and counts of a predicate answer how many elements in a range satisfy it. Min and max do not work, because you cannot undo a min — that is what segment trees are for.
Complexity
You pay one linear pass up front to make every subsequent query constant time, which wins as soon as you have more than a handful of queries; it is the wrong trade if the array changes between queries, since any update invalidates every prefix after it.
Common bugs
Writing pre[r] - pre[l] instead of pre[r + 1] - pre[l]
This drops a[r] from every query. With the 1-indexed prefix convention, pre[r] is the sum of everything strictly before index r. The answer is always short by exactly one element, so single-element ranges return 0 and the bug looks like an unrelated logic error.
Sizing the prefix array to n instead of n + 1
The query for the full array reads pre[n], which does not exist. In C++ that is an out-of-bounds read that often returns whatever happens to sit in the vector's spare capacity — frequently 0, which makes the result look almost right.
Integer overflow on large sums
Individual elements can fit in an int while their total does not. Summing 100,000 values around a million overflows a 32-bit int and produces negative range sums. Use long long for the prefix array even when the input is int; the values, not the array size, decide this.
Rebuilding after every update
Prefix sums are for static data. If an element changes, every prefix from that index onward is stale, and rebuilding is O(n) per update — worse than just looping over the range. If updates and queries interleave, you need a Fenwick tree, not this.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
What is a prefix sum array used for?
Answering repeated range-sum queries in constant time. After one O(n) precomputation, the sum of any subarray a[l..r] is a single subtraction, pre[r+1] - pre[l]. It also underpins solutions to subarray-sum-equals-k, equilibrium index, and difference-array range updates.
Why is the prefix array one element longer than the input?
The extra leading zero represents the sum of an empty prefix, which lets the query formula work when l is 0 with no special case. Without it you need an if-statement on every query, which is exactly the kind of branch that gets forgotten and produces wrong answers only at the array boundary.
How do I get the sum from index l to r using a prefix sum?
Use pre[r + 1] - pre[l] with the leading-zero convention, where pre[i] is the sum of the first i elements. The subtraction cancels everything before l, leaving exactly a[l] through a[r] inclusive. If your prefix array has no leading zero, the formula becomes pre[r] - pre[l-1] with a special case for l = 0.
Can prefix sums handle range minimum queries?
No. The technique requires an invertible operation so the unwanted portion can be subtracted out, and minimum has no inverse — knowing the min of the first r elements and the min of the first l tells you nothing about the min in between. Use a sparse table or segment tree for that.