Repeated range-sum queries should not rescan the same values. A prefix array stores prefix[i], the sum of the first i elements, with prefix[0] = 0 for the empty prefix. An inclusive range [l, r] then costs one subtraction: prefix[r + 1] - prefix[l]. The shared prefix before l cancels, leaving exactly the requested range.
Visualization
The trace uses seven days of sales, [4, 7, 2, 9, 5, 3, 8]. It writes every running total into the prefix array, then answers [2, 5]: prefix[6] - prefix[2] = 30 - 11 = 19.
prefix[k] accumulates every element strictly before index k, so prefix[r + 1] covers a[0..r] and prefix[l] covers a[0..l-1]. Subtracting them removes the common head a[0..l-1] exactly, leaving a[l] + ... + a[r]. The prefix[0] = 0 sentinel and the length-(n + 1) array are what let l = 0 use the same formula as any other left bound: prefix[0] supplies the empty sum with no special case.
Complexity
Prefix Sum complexity
n
number of elements in the source array
Both curves are per-query. The prefix array costs O(n) to build once, so the pattern only pays off when the number of queries outgrows that single pass.
When the Precompute Stops Holding
The source array must remain static during the query phase. One element update invalidates every later prefix. Workloads that mix writes with reads need a Fenwick tree for point updates and sums, or a segment tree for broader associative range aggregation. Lazy range updates require an update operation that composes correctly with the stored aggregate.
The +1 convention prevents a special case at the left edge. prefix[k] covers elements before k, so an inclusive query [l, r] uses prefix[r + 1] - prefix[l]. Mixing that half-open prefix definition with closed endpoints shifts the result by one element. Single-element and full-array queries expose the mismatch quickly.
The running total may overflow even when every input fits its type. A million large int values exceed 32-bit range long before the array ends, so the prefix storage and subtraction should use a wider type such as long.
Diagram and C# Implementation
Range sum as a difference of prefixes
flowchart LR
A["prefix[l]<br/>sum of a[0..l-1]"] --> C["prefix[r+1] - prefix[l]"]
B["prefix[r+1]<br/>sum of a[0..r]"] --> C
C --> D["sum of a[l..r]"]
C# implementation
public static long[] BuildPrefix(int[] a)
{
var prefix = new long[a.Length + 1]; // prefix[0] = 0, length n + 1
for (int i = 0; i < a.Length; i++)
prefix[i + 1] = prefix[i] + a[i]; // long guards against overflow
return prefix;
}
// Sum of a[l..r] inclusive.
public static long RangeSum(long[] prefix, int l, int r) => prefix[r + 1] - prefix[l];
`RangeSum` assumes `0 <= l <= r < n`. The leading `0` and the extra prefix slot remove the `l == 0` and `r == n - 1` boundary cases.
Comparison
Approach
Stronger case
Semantic limit
Naive re-sum
A handful of queries, or an array that changes constantly
Re-reads the whole range every time
Prefix sum
Many range sums over a static array
Any element write invalidates the stored suffix of totals