Prefix Sums: Answering Range Queries in O(1) After O(n) Preprocessing

The Core Idea and Its Invariant

A prefix sum (also called a cumulative sum, running total, or scan) of an array a[0..n−1] is an array P of length n+1 satisfying one invariant:

P[0] = 0
P[i] = a[0] + a[1] + … + a[i−1]   for 1 ≤ i ≤ n

Equivalently, P[i] = Σₖ₌₀ⁱ⁻¹ a[k]. The single most important consequence is the telescoping identity: the sum of any contiguous range a[l..r] (inclusive) equals a difference of two prefix values:

sum(l, r) = P[r+1] − P[l]

Because P[r+1] = a[0]+…+a[r] and P[l] = a[0]+…+a[l−1], everything before index l cancels, leaving exactly a[l]+…+a[r]. The off-by-one convention — making P length n+1 with a leading zero — is what makes this clean: it removes the special case for l = 0 (a query starting at the front). This exclusive-prefix, half-open convention is the same one that makes C++ std::partial_sum and Python itertools.accumulate composable.

Building It: One Pass, O(n)

The construction is a single left-to-right pass that maintains the invariant incrementally. Each new prefix is the previous prefix plus one array element:

function build(a[0..n−1]):
    P[0] ← 0
    for i ← 0 to n−1:
        P[i+1] ← P[i] + a[i]
    return P

• Loop invariant: before iteration i, P[0..i] already hold correct exclusive prefixes of a. The assignment extends the correct region by one, so by induction all n+1 entries are correct at exit.
• In-place variant: you can overwrite the array itself — a[i] += a[i−1] for i from 1 — giving an inclusive prefix sum with zero extra space. Then sum(l, r) = a[r] − (l > 0 ? a[l−1] : 0). The trade-off is you lose the tidy no-branch query.
• Parallel prefix sum: the naive recurrence looks strictly sequential, but the Blelloch scan (Guy Blelloch, 1990) computes it in O(log n) depth with O(n) work using an up-sweep/down-sweep tree — this is why GPUs (CUDA's thrust::inclusive_scan) can prefix-sum billions of elements per second.

Both build and query touch each element a constant number of times, so preprocessing is Θ(n) time and Θ(n) space, and every query is O(1).

Why the Amortization Wins

Prefix sums are the canonical precompute-once, query-many trade. Answering q range-sum queries naively costs O(nq) in the worst case (each query can span the whole array). Prefix sums cost Θ(n + q) total: Θ(n) to build plus O(1) per query. The crossover is immediate — even q = 2 queries on a large array already favor precomputation once you account for the scan.

• The trade you are making: you spend Θ(n) extra memory and give up the ability to do fast point updates. Changing one element a[j] invalidates every P[i] for i > j, forcing an O(n) rebuild of the suffix. Prefix sums are therefore a static-array structure.
• When updates matter: if the array mutates between queries, escalate to a Fenwick tree (Binary Indexed Tree, Peter Fenwick, 1994) or a segment tree, which support both point update and range query in O(log n). Prefix sums are literally the degenerate 'all builds, no updates' corner of that design space.
• Constant factors: the O(1) query is a single subtraction with perfect cache locality (two nearby array reads). Nothing beats it when the data is read-only. A Fenwick tree's O(log n) query, by contrast, chases ⌈log₂ n⌉ scattered indices.

Two Dimensions: The Integral Image

The idea lifts to a grid. Given a matrix A[m][n], define P[i][j] = Σ of all A[r][c] with r < i and c < j — the sum of the rectangle above-and-left of cell (i, j). This is the summed-area table, introduced to computer graphics by Frank Crow in 1984 and popularized in vision as the integral image by the Viola–Jones face detector (2001).

Build with a 2D recurrence (inclusion–exclusion on the corner):

P[i][j] = A[i−1][j−1] + P[i−1][j] + P[i][j−1] − P[i−1][j−1]

Then the sum of any axis-aligned submatrix with top-left (r1,c1) and bottom-right (r2,c2) inclusive is a four-point query:

sum = P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1]

• Build: Θ(mn). Query: O(1) — exactly four array reads regardless of rectangle size.
• Why Viola–Jones cared: a Haar-like feature evaluates the difference of pixel sums in adjacent rectangles. With an integral image, each feature costs a fixed handful of lookups, letting the detector scan thousands of feature windows per frame in real time.

The Dual Trick: Difference Arrays for Range Updates

Prefix sums answer range queries fast. Their inverse — the difference array — makes range updates fast, and the two are dual operations (differencing then prefix-summing is the identity). To add a value v to every element in a[l..r], you do not touch r−l+1 cells. Instead, on a difference array D:

D[l]   += v      // start the +v here
D[r+1] −= v      // stop it just after r

After processing all updates, take the prefix sum of D to recover the final array. This gives O(1) per range update and O(n) to materialize once at the end — turning k range updates from O(nk) into O(n + k).

• Where it appears: the classic LeetCode 'Corporate Flight Bookings' / 'Range Addition' problems, airline seat allocation, and Kadane-style batch offsetting. Databases and interval-scheduling code use the same 'plus at start, minus after end, then scan' pattern (an event sweep).
• 2D difference array: add v to a whole subrectangle in O(1) with four corner updates, then a 2D prefix sum reconstructs the grid — a staple for problems with many rectangle stamps.

Beyond Addition: Prefix Scans in General

The prefix-sum pattern is really prefix-scan over any associative operator. Replace + with any monoid operation ⊕ that has an identity, and the same one-pass recurrence and O(1) (or O(log n) for invertible ops) queries follow:

• Prefix XOR: with ⊕ = xor, P[i] = a[0] ⊕ … ⊕ a[i−1], and the range XOR a[l..r] = P[r+1] ⊕ P[l] (xor is its own inverse — subtraction becomes another xor). This underpins many 'subarray with XOR = k' problems solved with a hashmap of prefixes.
• Prefix product: works when you can divide out; when you cannot (a zero appears, or no modular inverse), fall back to the left-product / right-product pair trick, exactly the 'product of array except self' construction.
• Prefix min/max: associative but not invertible — you cannot recover an arbitrary range min by combining two prefixes, so range-min queries need a sparse table (O(1) query, O(n log n) build) or a segment tree instead. This is a crucial distinction: prefix sums give O(1) ranges only because + has an inverse.
• Prefix counts + hashmap: 'count subarrays summing to k' is O(n) by storing a frequency map of seen prefix sums and looking up P[i] − k — the workhorse of a whole genre of interview questions.

Pitfalls, Edge Cases, and Overflow

Prefix sums are simple enough that the bugs are almost always bookkeeping, not algorithmic:

• Off-by-one: the single most common mistake. With the length-n+1, leading-zero convention, inclusive sum(l, r) = P[r+1] − P[l]. If you build an inclusive prefix (no leading zero, length n), it becomes P[r] − P[l−1] with a guard for l = 0. Pick one convention and never mix them.
• Integer overflow: the cumulative total can be enormous even when individual elements are small. Summing 10⁵ elements each up to 10⁹ overflows 32-bit (max ≈ 2.1×10⁹) badly — use 64-bit (long long, int64) for the prefix array. This is a real, frequent failure in contest and production code.
• Floating-point drift: a prefix sum of floats accumulates rounding error, and a range query P[r+1] − P[l] can subtract two large nearly-equal values (catastrophic cancellation). Use Kahan summation or exact/decimal types when precision matters.
• Empty and out-of-range queries: a valid empty range (l > r) should return 0 — the formula handles it if you clamp, but many implementations forget to guard. Half-open [l, r) queries are cleaner: P[r] − P[l], no +1.
• Staleness after mutation: because prefix sums are static, any code path that mutates a after building P silently returns wrong answers. If mutation is possible, you need a Fenwick or segment tree, not a prefix sum.

Range-sum data structures: query, update, and build costs

Structure	Build	Range query	Point update	Space
Naive scan	O(1)	O(n)	O(1)	O(n)
Prefix sum	Θ(n)	O(1)	O(n)	Θ(n)
Fenwick (BIT)	O(n)	O(log n)	O(log n)	Θ(n)
Segment tree	O(n)	O(log n)	O(log n)	Θ(n)
Sqrt decomposition	O(n)	O(√n)	O(1)	Θ(n)