Loading...
Tier II · Intermediate
Precomputed running totals and difference arrays for O(1) range queries.
A prefix array stores running totals, so P[i] is the sum of the first i elements. The whole trick rests on one identity. Any range sum is the difference of two prefix totals, which makes every query a single subtraction.
Six numbers. The goal is the sum of any slice with a single subtraction, however long the slice is.
Watch P get built once, then two slices answered with one subtraction each. Everything before the slice is in both totals, so it cancels out.
| Variant | What it precomputes | Typical use |
|---|---|---|
| Prefix sum | Running totals P[0..n] | Range sums, suffixes |
| Difference array | Neighbor differences | Batched range updates |
| Prefix + hash map | Prefix value counts | Counting subarrays by sum |
The usual slip is the off-by-one. Store a leading zero, P[0] = 0, and the inclusive range [l, r] becomes P[r+1] - P[l] with no special case at the front. The difference array is the inverse of the prefix array. You add d at start, subtract it at end + 1, and one prefix pass recovers the values. When the prefix array is only plumbing under another algorithm, the problem lives there instead, with binary search, monotonic deques, or sieves.
| Approach | Time | Extra space |
|---|---|---|
| Re-add per query | ||
| Prefix sums | ||
| Difference array, updates |
Reach for it when a problem asks for many range totals, how one part compares with the rest, how a pile of range updates nets out, or how many subarrays hit a given sum or remainder.
The problems below start with range-sum queries and the balance point, move through products, the difference array, and a two-dimensional grid, and end with counting subarrays by sum and by residue.