Prefix Sums & Difference Arrays
Why this exists
Suppose you hold an array of 10 million daily sales figures and someone asks "what was the total between day 1,203,114 and day 4,998,201?" A loop over the range costs about four million additions. Now suppose they ask ten thousand such questions. Forty billion additions. The data never changed between questions; you were just recomputing overlapping sums from scratch every time.
A prefix sum array fixes this with one idea: precompute the running total up to every position once, and then every range sum is the difference of two running totals. Build in , answer each query in . The same trick, read in reverse, gives the difference array: if you have many range updates and only need the final array at the end, record each update as two endpoint marks and settle the account once with a single prefix pass.
The idea is old and everywhere. Accountants have kept running balances for centuries; a ledger's "balance" column is literally a prefix sum of the transactions. Frank Crow introduced the two-dimensional version to computer graphics in 1984 as the summed-area table for texture filtering, and Viola and Jones made it famous in 2001 as the integral image that let their face detector evaluate thousands of rectangular features per window in constant time each. Blelloch's 1990 survey Prefix Sums and Their Applications showed the operation (also called scan) is a fundamental parallel primitive — it is the building block behind stream compaction, radix sort and allocation on GPUs. Databases expose it as the running-total window function SUM(x) OVER (ORDER BY t). Monitoring systems store counters as monotonically increasing prefix sums and compute rates by differencing them.
In interviews, prefix sums show up directly ("range sum query") and, more often, in disguise: "count the subarrays whose sum is k", "longest subarray with equal 0s and 1s", "product of array except self", "apply these flight bookings". Each of these is a prefix-sum problem once you see that a contiguous range is the difference of two prefixes. This page teaches that way of seeing, proves why the hash-map counting trick is exact, and shows where the technique stops working and what replaces it.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "sum of elements between indices l and r", many queries, array never changes | 1D prefix sums, per query |
| "sum of the submatrix / rectangle", many queries, matrix immutable | 2D prefix sums with inclusion–exclusion |
| "count subarrays whose sum equals k" (negatives allowed) | Prefix sum + hash map of prefix counts, seeded with {0: 1} |
| "count subarrays whose sum is divisible by k" | Prefix sum modulo k + hash map of residue counts |
| "longest subarray with sum k" / "with equal number of 0s and 1s" | Prefix sum + hash map of first occurrence of each prefix |
| "product of all elements except self", "no division" | Prefix products and suffix products |
| "XOR of a range", "pairs with XOR equal to k" | Prefix XOR (XOR is its own inverse) |
| "apply these range increments, then report the final array" | Difference array: two marks per update, one prefix pass at the end |
| "paint / add v to every cell in a rectangle, many times" | 2D difference array with four corner marks |
| "pick an index with probability proportional to its weight" | Prefix sums + binary search |
| "cumulative distribution", "running total", "balance after each transaction" | The prefix array itself is the answer |
| Range updates interleaved with range queries | Prefix sums are not enough — Fenwick tree or segment tree |
| "minimum / maximum over a range" | Prefix min/max only for prefix-anchored ranges; arbitrary ranges need a sparse table or segment tree |
The deepest trigger is structural: whenever a quantity over a contiguous range can be written as for some function of position, you are looking at a prefix-sum problem. Sums, counts, XORs and products (without zeros) all qualify. Minimum and maximum do not, and the section on variations explains exactly why.
Intuition & first principles
Think of an odometer. It shows the total distance the car has ever travelled. To learn how far you drove today, you do not re-measure the road; you subtract this morning's reading from tonight's. The odometer is a prefix sum of all the trips. The subtraction works because addition is invertible: knowing the total up to tonight and the total up to this morning determines the day's distance uniquely.
Formally, for an array define
So is the sum of the first elements, . There are prefix values. Then for any
Everything from to is in ; everything from to is in ; the difference leaves exactly through .
Why the leading zero matters
Many beginners define prefix[i] = a[0] + ... + a[i] (no leading zero, length ). It works, but every range query then needs a branch: sum(l, r) = prefix[r] - (l > 0 ? prefix[l-1] : 0). Forgetting that branch is the single most common prefix-sum bug. With the convention there is no special case: sum(l, r) = P[r+1] - P[l] is correct for every valid , including , because is the "sum of nothing". The extra element costs one integer and buys the removal of a branch from the hot path and from your head. Use this convention always; this page and the rest of Archon do.
Half-open intervals
The same convention reads naturally in half-open form: the sum of a[l:r] (Python slice, inclusive, exclusive) is P[r] - P[l]. Half-open ranges compose cleanly: a[l:m] and a[m:r] partition a[l:r], and the prefix formula reflects that, (P[m]-P[l]) + (P[r]-P[m]) = P[r]-P[l]. When translating a problem that uses inclusive bounds , convert to half-open first, then apply the formula. That is where the +1 comes from.
From "range sum" to "count subarrays with sum k"
Here is the leap that turns a bookkeeping trick into an algorithmic technique. A subarray a[l..r] has sum exactly when , i.e. . Fix the right end . The number of valid left ends is the number of earlier prefix indices whose prefix value equals . If, while scanning left to right, you maintain a hash map from prefix value to how many times that value has appeared among , the count for this is a single lookup. Sum those lookups over all and you have the answer in expected time — for any integers, positive or negative. The sliding-window approach, which the sliding window lesson covers, cannot do this when negatives are present, because growing the window no longer monotonically grows the sum.
The map must start with {0: 1}: has "appeared" once before any element is read. That seed is what counts the subarrays that start at index 0. Drop it and every subarray starting at the beginning is silently missed.
The reverse direction: difference arrays
If prefix sums turn "range query" into "point lookups", the inverse operation turns "range update" into "point updates". Define the difference array (with ). Then is the prefix sum of . Adding to every element of changes exactly two differences: rises by (the step into the range) and falls by (the step out). Record all updates this way in each, then recover with one prefix pass. The approach is only valid when you do not need to read the array between updates — if queries are interleaved, you need a Fenwick tree or a segment tree, discussed under when prefix sums are not enough.
Mechanics
1D prefix sums and range queries
flowchart LR
A["a = [3, -1, 4, 1, -5, 9]"] --> B["P[0] = 0"]
B --> C["P[1] = 0 + 3 = 3"]
C --> D["P[2] = 3 + (-1) = 2"]
D --> E["P[3] = 2 + 4 = 6"]
E --> F["P[4] = 6 + 1 = 7"]
F --> G["P[5] = 7 + (-5) = 2"]
G --> H["P[6] = 2 + 9 = 11"]
H --> Q["sum(l, r) = P[r+1] - P[l]"]
Build: one pass, one addition per element. The trace below shows for a = [3, -1, 4, 1, -5, 9] and three range queries.
| i | a[i] | P[i+1] = P[i] + a[i] |
|---|---|---|
| — | — | P[0] = 0 |
| 0 | 3 | P[1] = 0 + 3 = 3 |
| 1 | -1 | P[2] = 3 + (-1) = 2 |
| 2 | 4 | P[3] = 2 + 4 = 6 |
| 3 | 1 | P[4] = 6 + 1 = 7 |
| 4 | -5 | P[5] = 7 + (-5) = 2 |
| 5 | 9 | P[6] = 2 + 9 = 11 |
| Query [l, r] | Formula | Value | Check by direct addition |
|---|---|---|---|
| [0, 2] | P[3] - P[0] = 6 - 0 | 6 | 3 + (-1) + 4 = 6 |
| [2, 4] | P[5] - P[2] = 2 - 2 | 0 | 4 + 1 + (-5) = 0 |
| [1, 5] | P[6] - P[1] = 11 - 3 | 8 | -1 + 4 + 1 + (-5) + 9 = 8 |
Notice the second query: a range with a sum of zero appears as two equal prefix values, . That observation — "equal prefixes bracket a zero-sum range" — is the heart of the contiguous-array problem below.
Counting subarrays with sum k
Scan once. Keep running (the current prefix ), a map count from prefix value to occurrences, and the answer. At each step look up running - k, add its count to the answer, then record running in the map. The order matters: look up before inserting, otherwise a subarray of length zero would be counted when .
Trace on a = [1, 2, 3, -2, 2, 1], , map seeded with {0: 1}:
| i | a[i] | running prefix P[i+1] | needed = P[i+1] − k | count[needed] | answer so far | map after inserting P[i+1] |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | -2 | 0 | 0 | {0: 1, 1: 1} |
| 1 | 2 | 3 | 0 | 1 | 1 | {0: 1, 1: 1, 3: 1} |
| 2 | 3 | 6 | 3 | 1 | 2 | {0: 1, 1: 1, 3: 1, 6: 1} |
| 3 | -2 | 4 | 1 | 1 | 3 | {0: 1, 1: 1, 3: 1, 4: 1, 6: 1} |
| 4 | 2 | 6 | 3 | 1 | 4 | {0: 1, 1: 1, 3: 1, 4: 1, 6: 2} |
| 5 | 1 | 7 | 4 | 1 | 5 | {0: 1, 1: 1, 3: 1, 4: 1, 6: 2, 7: 1} |
Answer: 5. Brute force confirms it; the five subarrays (as inclusive index pairs) are (0,1) = 1+2, (1,3) = 2+3−2, (2,2) = 3, (2,4) = 3−2+2 and (4,5) = 2+1. Notice at the lookup hit the seed 0: that is the subarray starting at index 0. Without the seed the answer would have been 4.
Subarrays divisible by k
Replace "equal prefix" by "equal prefix residue". is divisible by exactly when . So keep a map (or an array of size ) of residue counts, and for each new prefix add the count of its own residue before incrementing it. On [4, 5, 0, -2, -3, 1] with this yields 7, the known answer for LeetCode 974.
The trap is negative numbers. In Python, (-3) % 5 is 2 — the result always takes the sign of the divisor. In C, C++, Java and JavaScript, -3 % 5 is -3 — the result takes the sign of the dividend. A residue of −3 and a residue of 2 are the same class but different hash keys, so the count silently splits in two. Normalise with ((x % k) + k) % k, or use Math.floorMod(x, k) in Java. Alternatively keep the running residue itself in after every step, so it never goes negative in the first place.
Longest subarray with sum k, and the 0/1 trick
To find the longest subarray with sum you want, for each right end, the earliest left end with . So store the first index at which each prefix value occurs instead of a count, and never overwrite it. The seed becomes first[0] = -1: prefix 0 occurs "before index 0", so a subarray from 0 to has length .
"Longest contiguous subarray with an equal number of 0s and 1s" is the same problem in costume: map every 0 to −1, every 1 to +1, and ask for the longest subarray with sum 0. On [0, 1, 0, 0, 1, 1, 0] the answer is 6 (drop the first element, or equivalently the last).
Product of array except self
Division is tempting but breaks on zeros and on overflow. Instead: left[i] = product of everything strictly before (a prefix product), right[i] = product of everything strictly after (a suffix product), answer left[i] * right[i]. Both can live in the output array: fill it with prefix products in a forward pass, then sweep backwards carrying a running suffix product and multiply it in. For [1, 2, 3, 4] the answer is [24, 12, 8, 6]. This is a prefix-sum problem over the multiplicative monoid, with "no division" forcing you to use the two-sided decomposition instead of the inverse.
Prefix XOR
XOR is associative, commutative and its own inverse (), so it behaves exactly like addition for prefix purposes: , , and the XOR of a[l..r] is . On [1, 3, 2, 6, 4] the prefix XOR array is [0, 1, 2, 0, 6, 2] and the XOR of indices 1..3 is , matching . "Count pairs with " is the hash-map counting pattern: for each look up how many earlier values equal . See Bit Manipulation for the algebra.
Prefix min and max
prefMin[i] = min(a[0..i-1]) is computable in one pass and answers "minimum of a[0..i]" in . It is useful for one-sided problems — "best time to buy and sell stock" is max over of — and for the classic "is there a j>i with a[j] > a[i]" style questions via a suffix max. But it cannot answer arbitrary range minima, because min has no inverse. More on that under variations.
2D prefix sums
Let be an matrix. Define of size with = sum of the top-left block, i.e. of all with and . The zero row and zero column are padding, the 2D analogue of .
Build by inclusion–exclusion:
The block above-and-left is counted in both the "above" and "left" blocks, so it is subtracted once.
flowchart TD
S["S[i+1][j+1] = sum of rows < i+1, cols < j+1"]
S --> U["+ S[i][j+1] (everything above, including the row's left part)"]
S --> L["+ S[i+1][j] (everything left, including the column's top part)"]
S --> O["- S[i][j] (above-left block, counted twice)"]
S --> C["+ A[i][j] (the new cell)"]
Query the rectangle with top-left and bottom-right , both inclusive:
Take the big block ending at , cut off the strip above row , cut off the strip left of column , and add back their overlap which was removed twice.
Worked on the 3×4 matrix
1 2 3 4
5 6 7 8
9 10 11 12
the table (4×5, zero-padded) is
0 0 0 0 0
0 1 3 6 10
0 6 14 24 36
0 15 33 54 78
and the query for rows 1..2, columns 1..2 (cells 6, 7, 10, 11) is . Direct addition: . The whole matrix is , and rows 0..1 × columns 2..3 (cells 3, 4, 7, 8) is .
Counting squares and rectangles. "How many axis-aligned squares have sum at most T" is a 2D prefix sum plus a double loop over top-left corners, per candidate and with binary search on when the predicate is monotone (LeetCode 1292). "Count square submatrices with all ones" (LeetCode 1277) uses a different prefix-like recurrence — dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) for a one cell — and sums the table: the example matrix [[0,1,1,1],[1,1,1,1],[0,1,1,1]] gives 15.
Difference arrays for range updates
Keep of length (the extra slot absorbs updates that end at without a bounds check — the same "extra zero removes a branch" idea). To add on : D[l] += v; D[r+1] -= v. After all updates, the final array is the prefix sum of (dropping the last slot).
Trace: , three updates.
| Step | Update | D after (length 9) |
|---|---|---|
| start | — | [0, 0, 0, 0, 0, 0, 0, 0, 0] |
| 1 | +5 on [1, 4] | [0, 5, 0, 0, 0, -5, 0, 0, 0] |
| 2 | −2 on [0, 2] | [-2, 5, 0, 2, 0, -5, 0, 0, 0] |
| 3 | +3 on [3, 7] | [-2, 5, 0, 5, 0, -5, 0, 0, -3] |
Materialising with a running sum: [-2, 3, 3, 8, 8, 3, 3, 3]. Check by hand: index 0 gets only −2; indices 1–2 get 5 − 2 = 3; indices 3–4 get 5 + 3 = 8; indices 5–7 get 3. Three updates cost six writes instead of 5 + 3 + 5 = 13, and with updates on an array of size the total is instead of .
2D difference arrays
Adding to every cell of the rectangle – needs four marks on a array:
D[r1][c1] += v
D[r1][c2+1] -= v
D[r2+1][c1] -= v
D[r2+1][c2+1] += v
Materialise with a 2D prefix sum. The signs mirror the 2D query formula, which is no coincidence: the difference array is the inverse of the prefix operator in both dimensions, and the query formula is just the 2D prefix operator's "inverse" applied to the rectangle indicator. On a 3×4 grid, adding 2 on rows 0..1 × cols 0..1 and then 3 on rows 1..2 × cols 1..3 yields [[2,2,0,0],[2,5,3,3],[0,3,3,3]], verified against direct application.
Prefix sums + binary search: weighted random pick
Given weights w = [1, 3, 2], pick index with probability . Build , draw an integer uniformly from , and return the largest with — bisect_right(P, t) - 1. Values map to index 0; map to index 1; map to index 2. Exactly 1, 3 and 2 of the six outcomes, as required. build, per draw. The same "prefix + binary search" shape appears in reservoir-free sampling, in finding the bucket of a value in a histogram, and in consistent hashing rings.
When prefix sums are not enough
Prefix sums assume the array is static between build and queries. Difference arrays assume you need the result only after all updates. If updates and queries interleave — "add 5 to index 3; what is the sum of 0..7; add −2 to index 6; …" — every point update invalidates prefix values, so you are back to per operation one way or the other.
The fix is to store partial sums in a tree instead of a line. A Fenwick tree (binary indexed tree) keeps carefully chosen partial sums so that both a point update and a prefix query touch of them; it is, quite literally, a dynamic prefix-sum array, and it is the subject of the Fenwick Trees lesson in the trees module. A segment tree generalises further to any associative operation, including min and max, with range updates via lazy propagation. Both are introduced in Advanced Data Structures. The rule of thumb:
| Updates | Queries | Tool |
|---|---|---|
| none (after build) | range sums | prefix sums |
| many range adds, then done | final array | difference array |
| point updates | prefix / range sums, interleaved | Fenwick tree |
| range updates | range queries, interleaved, any associative op | segment tree with lazy propagation |
| none | range min / max / gcd | sparse table ( query) or segment tree |
The ladder: brute force → better → optimal
Range sum queries
Rung 1 — recompute per query. For each query loop from to . precompute, per query, total. Fine for small; hopeless when both are .
Rung 2 — prefix sums. precompute, per query, total, extra memory. The improvement comes from sharing: every query's answer is assembled from two shared values rather than private ones. The trade is memory ( integers) and a loss of flexibility (updates break it).
There is no rung 3 for the static case — per query is optimal, and the precompute is unavoidable because each element must be read at least once.
Count subarrays with sum k
Rung 1 — all pairs, recompute. Three nested loops: for each sum the elements. .
Rung 2 — all pairs, running sum. Fix , extend while accumulating. time, space. Already uses the prefix idea implicitly (the running sum is ).
Rung 3 — prefix sums + hash map. One pass, expected time, space for the map. The improvement comes from turning "for every check " into a single hash lookup: instead of iterating candidates we index them. If the values are small integers in a known range you can replace the hash map with an array and make the time deterministic.
What about a sliding window? If all elements are positive, the window sum is monotone in both endpoints and a two-pointer window finds every qualifying subarray in with space — strictly better. The hash-map version is the one that survives negative numbers, zeros, and "divisible by k", and is therefore the general tool.
| Problem | Approach | Time | Extra space | Handles negatives | Needs |
|---|---|---|---|---|---|
| range sum, q queries | loop per query | yes | nothing | ||
| range sum, q queries | prefix array | yes | static array | ||
| subarray sum = k | all pairs | yes | nothing | ||
| subarray sum = k | sliding window | no | all elements ≥ 0 (or > 0 for exact count) | ||
| subarray sum = k | prefix + hash map | expected | yes | hashable sums | |
| q range updates, final array | apply each | yes | nothing | ||
| q range updates, final array | difference array | yes | no reads between updates |
Correctness
Range query formula
Claim: for , .
By definition (the empty sum for ). The indices in split into (exactly the terms of ) and . Subtracting cancels the first group and leaves the second. The argument needs only associativity, commutativity and the existence of additive inverses — i.e. that the values form an abelian group. That is precisely the property min and max lack.
Hash-map counting
Claim: the algorithm returns exactly the number of pairs with and .
Define a bijection between subarrays and prefix-index pairs: a[l..r] corresponds to with . Under this bijection, "sum is " becomes , i.e. .
Loop invariant. After processing elements (so running ):
- Just before the lookup for element ,
count[v]. Index is included because was inserted at the end of the previous iteration (or by the seed when ). answerequals the number of valid pairs with .
Initialisation. Before any element, count = {0: 1} records (the set ), and answer = 0 because there are no pairs with . Both hold.
Maintenance. At step we compute and add count[P_{i+1} - k] to the answer. By invariant 1, that is the number of with , which is exactly the number of subarrays ending at with sum — each such gives one subarray, distinct give distinct subarrays, and every subarray ending at with sum has such an . Then we insert , restoring invariant 1 for . Invariant 2 holds because the pairs with are precisely the ones we just counted.
Termination. After steps, answer counts all pairs with , i.e. all subarrays.
Two corollaries fall out. The seed {0: 1} is not a hack: it is the base case of the invariant. And inserting after looking up is essential: if were inserted first, then for the lookup would see itself and count the empty subarray , which is not a subarray.
Difference array
Claim: after marking each update as D[l] += v; D[r+1] -= v, the prefix sum of at index equals the total added to .
For one update, the prefix sum of its two marks at index is if and (we have passed the but not the ), and otherwise (neither or both passed). So one update contributes exactly to the indices in . The prefix-sum operator is linear, so the prefix sum of the sum of all marks is the sum of the individual contributions. The 2D proof is identical with the 2D prefix operator and the rectangle indicator decomposed into four quadrant indicators.
Complexity
| Operation | Time | Extra space |
|---|---|---|
| build 1D prefix | (or if done in place) | |
| 1D range query | — | |
| subarray-sum-equals-k | expected (hash), worst with array-indexed counts | distinct prefixes |
| build 2D prefix | ||
| 2D rectangle query | — | |
| difference array, q updates | marks + materialise | |
| 2D difference array | + | |
| weighted pick | build, per draw |
Constants are tiny and the access pattern is sequential, so the build runs at memory bandwidth: on modern hardware a prefix pass over 64-bit integers takes on the order of 100 ms, limited by the roughly 800 MB streamed. The one data-dependent chain — each depends on — limits instruction-level parallelism to one addition per cycle on a single core, which is why SIMD and GPU libraries implement scan with the work-efficient tree algorithm from Blelloch instead of a naive loop. The hash-map variant is dominated by cache misses in the map rather than arithmetic; when the prefix values are bounded (small positive integers, or residues modulo ) a plain array of counts is often 5–10× faster. Treat such speedup figures as indicative; measure on your machine (Benchmarks). The memory-layout reasons are covered in How Data Structures Live in Memory.
Worst-case for hash maps in adversarial settings is via collisions; see Hash Tables for why this rarely matters and how languages mitigate it.
Implementation
Each block below contains four functions — 1D prefix build with range query, subarray-sum-equals-k, 2D prefix with rectangle query, and a difference array — plus a test section with the same data as the trace tables. Sums use 64-bit integers in Java and C++ because elements of magnitude reach , far past the 32-bit limit of .
from collections import defaultdict
def build_prefix(a: list[int]) -> list[int]:
"""P[0] = 0, P[i+1] = P[i] + a[i]. Length n + 1."""
p = [0] * (len(a) + 1)
for i, x in enumerate(a):
p[i + 1] = p[i] + x
return p
def range_sum(p: list[int], l: int, r: int) -> int:
"""Sum of a[l..r] inclusive."""
return p[r + 1] - p[l]
def count_subarrays_with_sum(a: list[int], k: int) -> int:
seen = defaultdict(int)
seen[0] = 1 # P[0] = 0 has occurred once
running = 0
answer = 0
for x in a:
running += x
answer += seen[running - k] # look up first ...
seen[running] += 1 # ... then record
return answer
def build_prefix_2d(m: list[list[int]]) -> list[list[int]]:
rows, cols = len(m), len(m[0])
s = [[0] * (cols + 1) for _ in range(rows + 1)]
for i in range(rows):
for j in range(cols):
s[i + 1][j + 1] = m[i][j] + s[i][j + 1] + s[i + 1][j] - s[i][j]
return s
def rect_sum(s: list[list[int]], r1: int, c1: int, r2: int, c2: int) -> int:
"""Sum of the inclusive rectangle (r1, c1)..(r2, c2)."""
return s[r2 + 1][c2 + 1] - s[r1][c2 + 1] - s[r2 + 1][c1] + s[r1][c1]
def apply_range_updates(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
"""Each update (l, r, v) adds v to every index in [l, r]."""
d = [0] * (n + 1)
for l, r, v in updates:
d[l] += v
d[r + 1] -= v
out = [0] * n
running = 0
for i in range(n):
running += d[i]
out[i] = running
return out
if __name__ == "__main__":
a = [3, -1, 4, 1, -5, 9]
p = build_prefix(a)
assert p == [0, 3, 2, 6, 7, 2, 11]
assert range_sum(p, 0, 2) == 6
assert range_sum(p, 2, 4) == 0
assert range_sum(p, 1, 5) == 8
assert count_subarrays_with_sum([1, 2, 3, -2, 2, 1], 3) == 5
assert count_subarrays_with_sum([1, 1, 1], 2) == 2
assert count_subarrays_with_sum([0, 0], 0) == 3 # [0], [0], [0,0]
m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
s = build_prefix_2d(m)
assert rect_sum(s, 1, 1, 2, 2) == 34
assert rect_sum(s, 0, 0, 2, 3) == 78
assert rect_sum(s, 0, 2, 1, 3) == 22
assert apply_range_updates(8, [(1, 4, 5), (0, 2, -2), (3, 7, 3)]) == [-2, 3, 3, 8, 8, 3, 3, 3]
print("prefix sums: all tests passed")
import java.util.HashMap;
import java.util.Map;
public class PrefixSums {
/** P[0] = 0, P[i+1] = P[i] + a[i]. Length n + 1. Uses long to avoid overflow. */
static long[] buildPrefix(int[] a) {
long[] p = new long[a.length + 1];
for (int i = 0; i < a.length; i++) {
p[i + 1] = p[i] + a[i];
}
return p;
}
/** Sum of a[l..r] inclusive. */
static long rangeSum(long[] p, int l, int r) {
return p[r + 1] - p[l];
}
static long countSubarraysWithSum(int[] a, long k) {
Map<Long, Integer> seen = new HashMap<>();
seen.put(0L, 1); // P[0] = 0 has occurred once
long running = 0, answer = 0;
for (int x : a) {
running += x;
answer += seen.getOrDefault(running - k, 0); // look up first ...
seen.merge(running, 1, Integer::sum); // ... then record
}
return answer;
}
static long[][] buildPrefix2D(int[][] m) {
int rows = m.length, cols = m[0].length;
long[][] s = new long[rows + 1][cols + 1];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
s[i + 1][j + 1] = m[i][j] + s[i][j + 1] + s[i + 1][j] - s[i][j];
}
}
return s;
}
/** Sum of the inclusive rectangle (r1, c1)..(r2, c2). */
static long rectSum(long[][] s, int r1, int c1, int r2, int c2) {
return s[r2 + 1][c2 + 1] - s[r1][c2 + 1] - s[r2 + 1][c1] + s[r1][c1];
}
/** Each update {l, r, v} adds v to every index in [l, r]. */
static long[] applyRangeUpdates(int n, int[][] updates) {
long[] d = new long[n + 1];
for (int[] u : updates) {
d[u[0]] += u[2];
d[u[1] + 1] -= u[2];
}
long[] out = new long[n];
long running = 0;
for (int i = 0; i < n; i++) {
running += d[i];
out[i] = running;
}
return out;
}
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
}
public static void main(String[] args) {
int[] a = {3, -1, 4, 1, -5, 9};
long[] p = buildPrefix(a);
check(java.util.Arrays.equals(p, new long[]{0, 3, 2, 6, 7, 2, 11}), "prefix array");
check(rangeSum(p, 0, 2) == 6, "query [0,2]");
check(rangeSum(p, 2, 4) == 0, "query [2,4]");
check(rangeSum(p, 1, 5) == 8, "query [1,5]");
check(countSubarraysWithSum(new int[]{1, 2, 3, -2, 2, 1}, 3) == 5, "subarray sum = 3");
check(countSubarraysWithSum(new int[]{1, 1, 1}, 2) == 2, "subarray sum = 2");
check(countSubarraysWithSum(new int[]{0, 0}, 0) == 3, "subarray sum = 0");
int[][] m = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
long[][] s = buildPrefix2D(m);
check(rectSum(s, 1, 1, 2, 2) == 34, "rect (1,1)-(2,2)");
check(rectSum(s, 0, 0, 2, 3) == 78, "whole matrix");
check(rectSum(s, 0, 2, 1, 3) == 22, "rect (0,2)-(1,3)");
long[] out = applyRangeUpdates(8, new int[][]{{1, 4, 5}, {0, 2, -2}, {3, 7, 3}});
check(java.util.Arrays.equals(out, new long[]{-2, 3, 3, 8, 8, 3, 3, 3}), "difference array");
System.out.println("prefix sums: all tests passed");
}
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <unordered_map>
#include <vector>
using std::int64_t;
using std::vector;
// P[0] = 0, P[i+1] = P[i] + a[i]. Length n + 1. int64_t to avoid overflow.
vector<int64_t> buildPrefix(const vector<int>& a) {
vector<int64_t> p(a.size() + 1, 0);
for (std::size_t i = 0; i < a.size(); ++i) {
p[i + 1] = p[i] + a[i];
}
return p;
}
// Sum of a[l..r] inclusive.
int64_t rangeSum(const vector<int64_t>& p, int l, int r) {
return p[r + 1] - p[l];
}
int64_t countSubarraysWithSum(const vector<int>& a, int64_t k) {
std::unordered_map<int64_t, int> seen;
seen[0] = 1; // P[0] = 0 has occurred once
int64_t running = 0, answer = 0;
for (int x : a) {
running += x;
auto it = seen.find(running - k); // look up first ...
if (it != seen.end()) answer += it->second;
++seen[running]; // ... then record
}
return answer;
}
vector<vector<int64_t>> buildPrefix2D(const vector<vector<int>>& m) {
std::size_t rows = m.size(), cols = m[0].size();
vector<vector<int64_t>> s(rows + 1, vector<int64_t>(cols + 1, 0));
for (std::size_t i = 0; i < rows; ++i) {
for (std::size_t j = 0; j < cols; ++j) {
s[i + 1][j + 1] = m[i][j] + s[i][j + 1] + s[i + 1][j] - s[i][j];
}
}
return s;
}
// Sum of the inclusive rectangle (r1, c1)..(r2, c2).
int64_t rectSum(const vector<vector<int64_t>>& s, int r1, int c1, int r2, int c2) {
return s[r2 + 1][c2 + 1] - s[r1][c2 + 1] - s[r2 + 1][c1] + s[r1][c1];
}
struct Update { int l, r, v; };
// Each update adds v to every index in [l, r].
vector<int64_t> applyRangeUpdates(int n, const vector<Update>& updates) {
vector<int64_t> d(n + 1, 0);
for (const Update& u : updates) {
d[u.l] += u.v;
d[u.r + 1] -= u.v;
}
vector<int64_t> out(n);
int64_t running = 0;
for (int i = 0; i < n; ++i) {
running += d[i];
out[i] = running;
}
return out;
}
int main() {
vector<int> a = {3, -1, 4, 1, -5, 9};
vector<int64_t> p = buildPrefix(a);
assert((p == vector<int64_t>{0, 3, 2, 6, 7, 2, 11}));
assert(rangeSum(p, 0, 2) == 6);
assert(rangeSum(p, 2, 4) == 0);
assert(rangeSum(p, 1, 5) == 8);
assert(countSubarraysWithSum({1, 2, 3, -2, 2, 1}, 3) == 5);
assert(countSubarraysWithSum({1, 1, 1}, 2) == 2);
assert(countSubarraysWithSum({0, 0}, 0) == 3);
vector<vector<int>> m = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
auto s = buildPrefix2D(m);
assert(rectSum(s, 1, 1, 2, 2) == 34);
assert(rectSum(s, 0, 0, 2, 3) == 78);
assert(rectSum(s, 0, 2, 1, 3) == 22);
vector<int64_t> out = applyRangeUpdates(8, {{1, 4, 5}, {0, 2, -2}, {3, 7, 3}});
assert((out == vector<int64_t>{-2, 3, 3, 8, 8, 3, 3, 3}));
std::cout << "prefix sums: all tests passed\n";
return 0;
}
// P[0] = 0, P[i+1] = P[i] + a[i]. Length n + 1.
function buildPrefix(a: number[]): number[] {
const p: number[] = new Array(a.length + 1).fill(0);
for (let i = 0; i < a.length; i++) {
p[i + 1] = p[i] + a[i];
}
return p;
}
// Sum of a[l..r] inclusive.
function rangeSum(p: number[], l: number, r: number): number {
return p[r + 1] - p[l];
}
function countSubarraysWithSum(a: number[], k: number): number {
const seen = new Map<number, number>();
seen.set(0, 1); // P[0] = 0 has occurred once
let running = 0;
let answer = 0;
for (const x of a) {
running += x;
answer += seen.get(running - k) ?? 0; // look up first ...
seen.set(running, (seen.get(running) ?? 0) + 1); // ... then record
}
return answer;
}
function buildPrefix2D(m: number[][]): number[][] {
const rows = m.length, cols = m[0].length;
const s: number[][] = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
s[i + 1][j + 1] = m[i][j] + s[i][j + 1] + s[i + 1][j] - s[i][j];
}
}
return s;
}
// Sum of the inclusive rectangle (r1, c1)..(r2, c2).
function rectSum(s: number[][], r1: number, c1: number, r2: number, c2: number): number {
return s[r2 + 1][c2 + 1] - s[r1][c2 + 1] - s[r2 + 1][c1] + s[r1][c1];
}
// Each update [l, r, v] adds v to every index in [l, r].
function applyRangeUpdates(n: number, updates: [number, number, number][]): number[] {
const d: number[] = new Array(n + 1).fill(0);
for (const [l, r, v] of updates) {
d[l] += v;
d[r + 1] -= v;
}
const out: number[] = new Array(n).fill(0);
let running = 0;
for (let i = 0; i < n; i++) {
running += d[i];
out[i] = running;
}
return out;
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error("FAILED: " + what);
}
function same(a: number[], b: number[]): boolean {
return a.length === b.length && a.every((v, i) => v === b[i]);
}
const a = [3, -1, 4, 1, -5, 9];
const p = buildPrefix(a);
check(same(p, [0, 3, 2, 6, 7, 2, 11]), "prefix array");
check(rangeSum(p, 0, 2) === 6, "query [0,2]");
check(rangeSum(p, 2, 4) === 0, "query [2,4]");
check(rangeSum(p, 1, 5) === 8, "query [1,5]");
check(countSubarraysWithSum([1, 2, 3, -2, 2, 1], 3) === 5, "subarray sum = 3");
check(countSubarraysWithSum([1, 1, 1], 2) === 2, "subarray sum = 2");
check(countSubarraysWithSum([0, 0], 0) === 3, "subarray sum = 0");
const m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]];
const s = buildPrefix2D(m);
check(rectSum(s, 1, 1, 2, 2) === 34, "rect (1,1)-(2,2)");
check(rectSum(s, 0, 0, 2, 3) === 78, "whole matrix");
check(rectSum(s, 0, 2, 1, 3) === 22, "rect (0,2)-(1,3)");
check(same(applyRangeUpdates(8, [[1, 4, 5], [0, 2, -2], [3, 7, 3]]), [-2, 3, 3, 8, 8, 3, 3, 3]), "difference array");
console.log("prefix sums: all tests passed");
Variants worth having in your fingers
Longest subarray with sum k (first-occurrence map, Python):
def longest_subarray_with_sum(a: list[int], k: int) -> int:
first = {0: -1} # prefix 0 occurs "before" index 0
running, best = 0, 0
for i, x in enumerate(a):
running += x
if running - k in first:
best = max(best, i - first[running - k])
first.setdefault(running, i) # keep the EARLIEST index only
return best
def longest_equal_zeros_ones(bits: list[int]) -> int:
return longest_subarray_with_sum([1 if b else -1 for b in bits], 0)
assert longest_subarray_with_sum([1, -1, 5, -2, 3], 3) == 4 # [1,-1,5,-2]
assert longest_subarray_with_sum([-2, -1, 2, 1], 1) == 2 # [-1,2]
assert longest_equal_zeros_ones([0, 1, 0, 0, 1, 1, 0]) == 6
assert longest_equal_zeros_ones([0, 1]) == 2
print("longest-subarray variants ok")
Subarrays divisible by k, with the negative-residue fix made explicit:
def subarrays_divisible_by(a: list[int], k: int) -> int:
counts = [0] * k
counts[0] = 1
residue, answer = 0, 0
for x in a:
residue = (residue + x) % k # Python % is already non-negative for k > 0
# In C/C++/Java/JS write: residue = ((residue + x) % k + k) % k
answer += counts[residue]
counts[residue] += 1
return answer
assert subarrays_divisible_by([4, 5, 0, -2, -3, 1], 5) == 7
assert subarrays_divisible_by([5], 9) == 0
print("divisible-by-k ok")
Weighted random pick (prefix + binary search, LeetCode 528 shape):
import bisect
import random
class WeightedPicker:
def __init__(self, weights: list[int]) -> None:
self.prefix = [0]
for w in weights:
self.prefix.append(self.prefix[-1] + w)
self.total = self.prefix[-1]
def pick(self, rng: random.Random) -> int:
t = rng.randrange(self.total) # uniform in [0, total)
return bisect.bisect_right(self.prefix, t) - 1
picker = WeightedPicker([1, 3, 2])
assert picker.prefix == [0, 1, 4, 6]
# every target value maps to the correct index: 0 -> 0, 1..3 -> 1, 4..5 -> 2
assert [bisect.bisect_right(picker.prefix, t) - 1 for t in range(6)] == [0, 1, 1, 1, 2, 2]
rng = random.Random(42)
hist = [0, 0, 0]
for _ in range(60000):
hist[picker.pick(rng)] += 1
assert abs(hist[1] / 60000 - 0.5) < 0.02 and abs(hist[2] / 60000 - 1 / 3) < 0.02
print("weighted pick ok")
Real-world uses
Integral images in computer vision. Crow's 1984 summed-area table and the Viola–Jones 2001 integral image are exactly the 2D prefix sum of pixel intensities. A Haar-like feature — "sum of pixels in this rectangle minus sum in that one" — becomes a handful of table lookups regardless of rectangle size. The Viola–Jones detector evaluates many thousands of such features over every 24×24 window of an image; without the integral image each 24×24 sum would be 576 additions, with it four lookups. OpenCV's cv::integral and box-filter blurs rely on it; so do adaptive thresholding and fast local-mean / local-variance computations (the variance one uses a second table of squared pixels).
Cumulative histograms and CDFs. Histogram equalisation maps each intensity through the cumulative distribution, which is the prefix sum of the histogram. Order statistics ("the 95th percentile latency") are read off a prefix sum of bucket counts; HDR histograms and Prometheus histogram buckets are stored cumulatively for exactly this reason — the le buckets in Prometheus are prefix sums, so any quantile can be estimated from them with a single scan.
Database running totals. SQL window functions compute prefix sums declaratively: SUM(amount) OVER (ORDER BY ts ROWS UNBOUNDED PRECEDING) is the running balance. Engines implement it with a single ordered pass maintaining an accumulator — the algorithm from this page — and some (ClickHouse, DuckDB) use segment-tree-based aggregation for sliding frames. See Advanced SQL for the window-function syntax and semantics.
Monitoring counters. A Prometheus counter is a monotonically increasing prefix sum of events. The query rate(http_requests_total[5m]) computes — a range sum via prefix difference, divided by the window length. Storing the prefix rather than the per-interval count means a dropped scrape loses no information: the next successful scrape still yields the correct total over the gap. The same reasoning underlies network interface byte counters (ifInOctets in SNMP) and /proc/stat CPU time counters.
Time-series bucketing. Downsampling a stream into fixed buckets ("requests per minute from per-second counts") is a difference of prefix sums at bucket boundaries; range-aggregate queries over immutable chunks in time-series engines precompute per-chunk sums for the same reason. Time-Series Storage Engines covers the chunking that makes this fast at scale.
Fenwick trees as dynamic prefix sums. Every system that needs "prefix sum with point updates" — order-statistics on a live leaderboard, counting inversions online, rank queries in a compressed index — uses a Fenwick tree, which is a prefix-sum array rearranged so that updates and queries both cost . Understanding the static version first is what makes the tree version obvious.
Parallel scan on GPUs. CUDA's Thrust inclusive_scan, CUB, and every GPU radix sort use prefix sums to compute output offsets: after counting items per bucket, the exclusive prefix sum of the counts tells each bucket where to start writing. Stream compaction ("keep only the elements that pass a predicate, packed") is a prefix sum of the 0/1 predicate followed by a scatter.
Scheduling and capacity. "Car pooling" and "corporate flight bookings" are difference arrays: each trip adds passengers on ; materialise and check the maximum against capacity. Calendar systems, meeting-room load, and rate limiters with time-bucketed counters all reduce to the same accounting.
Pitfalls & edge cases
Off-by-one on inclusive bounds. The formula is P[r+1] - P[l] for inclusive and P[r] - P[l] for half-open . Decide which convention the problem uses before writing a line, and write a two-element test (a = [5, 7], query the whole thing, expect 12) to catch the mistake instantly.
Overflow. In Java and C++ an int prefix of values up to overflows at the 3rd element. Use long / int64_t for prefix arrays and for the hash-map keys, and remember that long * long products in "product except self" can overflow too (LeetCode guarantees the product fits in 32 bits; real inputs do not). In JavaScript, number is exact only up to ; beyond that use BigInt. Python integers are arbitrary precision and cannot overflow, which is one reason prefix problems feel easier there.
Negative modulo. -3 % 5 is -3 in C, C++, Java and JavaScript. Normalise with ((x % k) + k) % k or Math.floorMod. Python's % already returns a value in for positive .
2D index shifts. The prefix table is one larger in each dimension; S[i+1][j+1] corresponds to A[i][j]. Mixing padded and unpadded indices is the most common 2D bug. Name things explicitly (S vs A) and never reuse i for both.
Forgetting the seed. {0: 1} in the counting map and {0: -1} in the first-occurrence map. Both encode "the empty prefix exists". Omitting them drops every subarray that starts at index 0.
Lookup before insert. With , inserting the current prefix before looking it up counts the empty subarray at every position.
Overwriting first occurrences. For longest subarray, keep the earliest index (use setdefault in Python, putIfAbsent in Java). For shortest, keep the latest. For count, keep a count. Three problems, three map semantics.
Mutating the input. Building the prefix in place (a[i] += a[i-1]) saves memory but destroys the original values, which you may need later (for example to print the subarray). It also breaks the convention unless you shift indices. Only do it when the problem explicitly permits and you are sure the originals are not needed.
Difference array length. must have slots so that D[r+1] is valid when . Allocating and guarding with if r + 1 < n works too, but is one more branch to get wrong.
Empty input. build_prefix([]) returns [0], and there are no valid queries. The hash-map count on an empty array returns 0. Make sure your 2D code does not index m[0] on an empty matrix.
Floating point. Prefix sums of floats accumulate rounding error, and P[r+1] - P[l] suffers catastrophic cancellation when both are large and nearly equal. For money use integers (cents); for floats consider Kahan summation or a segment tree with pairwise summation.
Variations
Prefix over any associative operation — but inversion needs a group. You can build a prefix array for any associative operation (min, max, gcd, matrix product, string concatenation). You can answer arbitrary range queries by subtraction only when the operation has inverses — when the values form a group: addition, XOR, multiplication of non-zero values modulo a prime. min and max are idempotent (min(x, x) = x) and have no inverse: knowing min(a[0..r]) and min(a[0..l-1]) tells you nothing about min(a[l..r]) if the smaller value lives in the prefix. Idempotence does buy you something else, though: overlapping ranges are harmless, so a sparse table storing minima of all power-of-two-length ranges answers any range-min query in by overlapping two blocks. That structure is covered in Advanced Data Structures.
Prefix counts per character. For substring questions like "how many vowels in s[l..r]" or "can s[l..r] be rearranged into a palindrome", keep one prefix count per alphabet symbol: cnt[c][i] = number of c in s[0..i-1]. Memory is for lowercase English; queries are . The "can be rearranged into a palindrome" question (LeetCode 1177) further compresses this into a prefix XOR of a 26-bit mask, because only the parity of each count matters.
Prefix sums on trees via Euler tour. Flatten a rooted tree by DFS entry time; every subtree becomes a contiguous range of the flattened array, and subtree sums become range sums. "Prefix sums on a path" uses root-to-node prefix sums with a lowest common ancestor to subtract the shared part. Both are developed in the trees and graphs modules.
Prefix products with zeros. Product-of-range queries break on zero because zero has no inverse. Track the count of zeros as a separate prefix (any range containing a zero has product zero) and take the product prefix over the non-zero values, or reset the prefix at each zero as LeetCode 1352 ("Product of the Last K Numbers") does.
Modular prefix products with a prime modulus do form a group on non-zero residues, so product(l..r) = P[r+1] * inverse(P[l]) mod p works, with the inverse from Fermat's little theorem. This is the engine of polynomial string hashing, where the hash of any substring is a prefix-hash difference — developed in the strings module.
Prefix sums of prefix sums. Applying the operator twice gives "add an arithmetic progression on a range" in via a second-order difference array, and "sum of all subarray sums" in one pass. Useful in contest problems; the correctness argument is linearity applied twice.
Sliding window vs. prefix sum. When all values are non-negative and you want the best window rather than all windows, sliding window achieves space. Prefix sums with a hash map pay space to handle arbitrary signs and exact counting. Knowing which to reach for is a frequent interview discriminator.
Monotonic structures. "Maximum subarray sum" (Kadane) is max over r of (P[r+1] - min over l ≤ r of P[l]), i.e. a running prefix minimum of the prefix array. "Shortest subarray with sum at least k" with negatives (LeetCode 862) needs a monotonic deque over the prefix array. Both show the prefix array as a substrate on which other techniques run.
Practice ladder
Each problem is described in my own words; follow the link for the formal statement.
1. Range Sum Query – Immutable (LeetCode 303) — Build a class that answers inclusive range sums on a fixed array. Teaches the P[r+1] - P[l] convention and nothing else; do it in under five minutes.
Hint
Store the -length prefix array in the constructor. Every query is a single subtraction.
2. Static Range Sum Queries (CSES 1646) — Same idea with elements and queries, values up to . Teaches you to use 64-bit sums and fast I/O.
Hint
The sum of values of is : use long / int64_t. In Python, read all input at once with sys.stdin.buffer.
3. Range Sum Query 2D – Immutable (LeetCode 304) — Rectangle sums on a fixed matrix. Teaches the 2D build and the four-term query formula.
Hint
Pad the table by one row and one column of zeros. Build with +above +left -aboveleft +cell; query with big - top - left + topleft.
4. Forest Queries (CSES 1652) — Count trees in rectangular regions of a 1000×1000 grid under queries. Teaches 2D prefix sums at scale and 1-based input handling.
Hint
Convert the character grid to 0/1 and build the 2D prefix table once. The queries are 1-based inclusive — map to the padded table carefully.
5. Subarray Sum Equals K (LeetCode 560) — Count contiguous subarrays summing to exactly ; values may be negative. The canonical prefix + hash map problem.
Hint
Keep a map from prefix value to count, seeded with {0: 1}. For each new prefix add count[prefix - k], then increment count[prefix].
Solution
from collections import defaultdict
def subarray_sum(nums: list[int], k: int) -> int:
seen = defaultdict(int)
seen[0] = 1
running = answer = 0
for x in nums:
running += x
answer += seen[running - k]
seen[running] += 1
return answer
assert subarray_sum([1, 2, 3, -2, 2, 1], 3) == 5
assert subarray_sum([1, 1, 1], 2) == 2
assert subarray_sum([1, -1, 0], 0) == 3
print("560 ok")
expected time, space. The proof is in the Correctness section above.
6. Subarray Sums II (CSES 1661) — Count subarrays with sum exactly for up to and values that may be negative. Same algorithm as 560; teaches you to trust it at scale and to use a hash map rather than an array.
Hint
Identical to LeetCode 560. Watch the 64-bit range of the prefix values and use a dictionary keyed by the exact prefix.
7. Subarray Sums Divisible by K (LeetCode 974) — Count subarrays whose sum is a multiple of . Teaches residue classes and the negative-modulo fix.
Hint
Two prefixes with the same residue mod bracket a subarray divisible by . Count residues with an array of size seeded counts[0] = 1. Normalise negatives. CSES "Subarray Divisibility" (task 1662) is the same problem with .
Solution
def subarrays_div_by_k(nums: list[int], k: int) -> int:
counts = [0] * k
counts[0] = 1
residue = answer = 0
for x in nums:
residue = (residue + x) % k
answer += counts[residue]
counts[residue] += 1
return answer
assert subarrays_div_by_k([4, 5, 0, -2, -3, 1], 5) == 7
assert subarrays_div_by_k([5], 9) == 0
assert subarrays_div_by_k([-1, 2, 9], 2) == 2
print("974 ok")
time, space. Each residue class with occurrences contributes pairs, which is what the running count accumulates.
8. Contiguous Array (LeetCode 525) — Longest subarray with equally many 0s and 1s. Teaches the 0 → −1 transformation and the first-occurrence map.
Hint
Map 0 to −1 and look for the longest subarray with sum 0. Store the first index where each prefix value appears, seeded {0: -1}.
Solution
def find_max_length(nums: list[int]) -> int:
first = {0: -1}
running = best = 0
for i, b in enumerate(nums):
running += 1 if b else -1
if running in first:
best = max(best, i - first[running])
else:
first[running] = i
return best
assert find_max_length([0, 1, 0, 0, 1, 1, 0]) == 6
assert find_max_length([0, 1]) == 2
assert find_max_length([0, 0, 0]) == 0
print("525 ok")
time, space. Only the earliest index per prefix value is stored, because a later index can only give a shorter subarray.
9. Product of Array Except Self (LeetCode 238) — Each output is the product of all other elements, no division, extra space. Teaches prefix/suffix decomposition when inverses are unavailable.
Hint
Fill the output with prefix products (out[i] = product before ), then sweep right-to-left carrying a running suffix product and multiplying it in.
Solution
def product_except_self(nums: list[int]) -> list[int]:
n = len(nums)
out = [1] * n
for i in range(1, n):
out[i] = out[i - 1] * nums[i - 1] # prefix product, exclusive
suffix = 1
for i in range(n - 1, -1, -1):
out[i] *= suffix # multiply in suffix, exclusive
suffix *= nums[i]
return out
assert product_except_self([1, 2, 3, 4]) == [24, 12, 8, 6]
assert product_except_self([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]
print("238 ok")
time, extra space beyond the output. Zeros are handled naturally because no division occurs.
10. Count Number of Nice Subarrays (LeetCode 1248) — Count subarrays with exactly odd numbers. Teaches "transform then count": map odd → 1, even → 0, and it is 560.
Hint
Replace each element by x % 2 and count subarrays with sum exactly using the prefix-count map.
11. Matrix Block Sum (LeetCode 1314) — For each cell, the sum of the block within distance . Teaches 2D prefix queries with clamped boundaries.
Hint
Build the 2D prefix table; for each cell clamp and to the matrix and apply the four-term query.
12. Corporate Flight Bookings (LeetCode 1109) — Many bookings each add seats to a range of flights; report seats per flight. The canonical difference-array problem.
Hint
d[first-1] += seats; d[last] -= seats (1-based input), then prefix-sum .
Solution
def corp_flight_bookings(bookings: list[list[int]], n: int) -> list[int]:
d = [0] * (n + 1)
for first, last, seats in bookings: # 1-based inclusive flights
d[first - 1] += seats
d[last] -= seats
out = [0] * n
running = 0
for i in range(n):
running += d[i]
out[i] = running
return out
assert corp_flight_bookings([[1, 2, 10], [2, 3, 20], [2, 5, 25]], 5) == [10, 55, 45, 25, 25]
assert corp_flight_bookings([[1, 2, 10], [2, 2, 15]], 2) == [10, 25]
print("1109 ok")
time for bookings, space. Each booking is two writes regardless of its length.
13. Car Pooling (LeetCode 1094) — Trips pick up and drop off passengers at positions; decide whether capacity is ever exceeded. Teaches difference arrays with half-open intervals (passengers leave at the drop-off).
Hint
d[from] += p; d[to] -= p (no +1, because the drop-off position is exclusive), then check the running sum never exceeds capacity.
14. Product of the Last K Numbers (LeetCode 1352) — Stream of numbers; query the product of the last . Teaches prefix products with the zero problem and the reset trick.
Hint
Keep a prefix-product list starting at [1]. On a zero, reset the list to [1]. A query for larger than the list length minus one spans a zero and returns 0; otherwise prefix[-1] // prefix[-1-k].
15. Shifting Letters II (LeetCode 2381) — Apply many range shifts (forward or backward) to a string's letters. Teaches difference arrays with signed updates and a final modulo-26 materialisation.
Hint
d[l] += ±1; d[r+1] -= ±1, prefix-sum, then shift each character by running % 26 (normalised to be non-negative).
Common mistakes & interview follow-ups
"What if the array receives updates between queries?" Prefix sums degrade to per update. Switch to a Fenwick tree ( point update and prefix query, trivially from the same mental model) or a segment tree if you need range updates or non-invertible operations. Name both and explain the trade: Fenwick is smaller and faster for sums; segment trees are more general.
"What if the input is a stream and you cannot store it?" The hash-map counting algorithm is streaming: it needs only the running prefix and the map, never the array. Range queries over a stream need the prefix values at the two endpoints; if queries arrive after the fact you must store the prefix array (or a sample of it), which is the time-series bucketing idea.
"What if memory is tight — can you avoid the map?" If values are bounded, use an array indexed by prefix value. If you only need "does any subarray sum to k" rather than "how many", you can sometimes sort the prefix array and two-pointer it in time with extra space beyond the prefix array (which can be built in place). For range queries alone, the prefix array can replace the input in place.
"Why does the sliding window fail here?" With negative numbers, extending the window can decrease the sum and shrinking it can increase it, so there is no monotone relationship to exploit; the window may need to grow and shrink arbitrarily and would miss subarrays. Prefix + hash map never assumes monotonicity.
"Can you do 2D range sums with 2D updates?" A 2D Fenwick tree gives for point update and rectangle query. 2D range update with 2D range query needs a 2D segment tree or a 2D Fenwick with four auxiliary trees — know that it exists and is heavy.
"How do you handle the overflow in Java here?" Prefix array of long; if even long is insufficient (products), use BigInteger or take everything modulo a prime as the problem allows.
"Count subarrays with sum in [lo, hi]?" count(≤ hi) − count(≤ lo−1), where count(≤ x) over prefix pairs needs an order-statistic structure (Fenwick over compressed prefix values, or merge-sort-based counting) in . A plain hash map cannot do inequalities.
"Minimum size subarray with sum at least k, with negatives?" The prefix array plus a monotonic deque of candidate left ends gives (LeetCode 862). Mention the deque and that non-negative inputs allow the simpler sliding window.
Common mistakes interviewers watch for: forgetting the {0: 1} seed; using int; writing P[r] - P[l] for inclusive bounds; inserting before looking up; using a sliding window with negatives; building the 2D table with + where a − belongs.
Quick quiz
1. Why does the prefix array have elements rather than ?
Answer
So that represents the empty prefix. Then sum(l, r) = P[r+1] - P[l] holds for every with no special case for , and the hash-map algorithms get their seed ({0: 1} or {0: -1}) for free.
2. In "count subarrays with sum k", what goes wrong if you insert the current prefix into the map before looking up prefix - k?
Answer
For the lookup finds the prefix you just inserted and counts the empty subarray at every position, inflating the answer by . For the order does not matter, but the habit does.
3. Why cannot a prefix-min array answer "minimum of a[l..r]" for arbitrary ?
Answer
Because min has no inverse. Knowing the minimum of and of does not determine the minimum of when the global minimum lies before . Range sums work because addition has inverses (the integers form a group). For range min use a sparse table or segment tree.
4. You have range increments to apply to an array of zeros, and only then need the final array. Complexity of the naive approach versus a difference array?
Answer
Naive: up to writes. Difference array: marks plus one prefix pass — about operations.
5. Give the 2D query formula for the rectangle – inclusive, with a zero-padded table .
Answer
. Remove the strip above and the strip left of , then add back their overlap which was removed twice.
Further reading / sources
- Guy E. Blelloch, Prefix Sums and Their Applications, CMU-CS-90-190 (1990) — the canonical survey of scan as a primitive, including the parallel work-efficient algorithm.
- Franklin C. Crow, "Summed-area tables for texture mapping", SIGGRAPH 1984 — origin of the 2D prefix sum in graphics.
- Paul Viola and Michael Jones, "Rapid Object Detection using a Boosted Cascade of Simple Features", CVPR 2001 — the integral image.
- Peter M. Fenwick, "A New Data Structure for Cumulative Frequency Tables", Software: Practice and Experience 24(3), 1994 — dynamic prefix sums.
- cp-algorithms: Fenwick tree and Segment tree — the dynamic successors of the static prefix array, with the sum query as the motivating case.
- Antti Laaksonen, Competitive Programmer's Handbook, chapter 9 "Range queries" — prefix sums, sparse tables, Fenwick and segment trees side by side.
- Prometheus documentation on counters and
rate().
Previous lesson: Sliding Window · Next lesson: Matrices & 2D Grids
Related: Module 1 overview · Arrays & Strings · Hash Tables · Two Pointers · Monotonic Stack & Deque · Intervals · Advanced Data Structures · Bit Manipulation · Complexity Analysis · Course home