Lesson 0.2 introduced prefix sums for range-sum queries. This lesson turns them into a full tool you can apply to any "how much between here and there?" question: counts instead of sums, two dimensions instead of one, and the mirror-image trick, difference arrays, for when the problem is many range updates instead of many range queries. Each part starts from a brute force, shows the constraint that makes it too slow, and derives the optimisation.
1. The core idea, in one line
Store running totals once: P[k] = a[0] + … + a[k−1], with P[0] = 0. Then any range total is a difference of
two running totals:
a[l] + … + a[r] = P[r + 1] − P[l]
Build: O(n). Each query: O(1). Space: O(n). The trick works for any quantity you can add and subtract: sums, counts, and anything you can encode as 0/1 per element.
2. Counting with prefix sums: accuracy over any window
Problem. A model made n predictions; correct[i] is 1 if prediction i was right, 0 otherwise. Answer q queries
"what fraction was correct between positions l and r?"
ML context. Evaluating a model over many time windows (per day, per week, per drift period) from one log of predictions.
Brute force
def window_accuracy_brute(correct, queries):
out = []
for l, r in queries:
out.append(sum(correct[l:r + 1]) / (r - l + 1)) # O(r − l) per query
return out
correct = [1, 0, 1, 1, 0, 0, 1, 1]
assert window_accuracy_brute(correct, [(2, 6), (0, 7)]) == [3 / 5, 5 / 8]
print("brute force works")
Cost: O(n · q) worst case. With 10⁶ predictions and 10⁴ windows that's 10¹⁰: too slow. The constraint that forces the change is many queries over the same data.
Optimised: prefix counts
from itertools import accumulate
def window_accuracy_prefix(correct, queries):
P = [0, *accumulate(correct)] # O(n) once
return [(P[r + 1] - P[l]) / (r - l + 1) for l, r in queries] # O(1) each
import random
rng = random.Random(2)
correct = [rng.randint(0, 1) for _ in range(500)]
queries = [(l, rng.randint(l, 499)) for l in (rng.randint(0, 499) for _ in range(300))]
fast = window_accuracy_prefix(correct, queries)
slow = [sum(correct[l:r + 1]) / (r - l + 1) for l, r in queries]
assert all(abs(a - b) < 1e-12 for a, b in zip(fast, slow))
print("prefix counts agree with brute force")
Cost: O(n + q) time, O(n) space.
Quick check
You want the number of times the label 'spam' appears in any range of a long label list. How do prefix sums apply?
Show the answer
B. Convert each label to 1 if it's 'spam' else 0, prefix-sum those indicators, and each range count is a difference of two prefix values — Any per-element property becomes countable once encoded as 0/1, and counts add and subtract like sums.
3. Two dimensions: rectangle sums
Problem. Given an R × C grid of numbers (an image, an attention map, a heat map of activity), answer q queries: the sum inside a rectangle with rows r1..r2 and columns c1..c2.
ML context. Classic face detectors computed box features over images in constant time with exactly this structure (an "integral image"); today the same idea gives fast region statistics over activation or attention maps.
Brute force
Loop over every cell in the rectangle: O(area) per query, O(R · C · q) worst case. A 1000 × 1000 image with 10⁴ queries is 10¹⁰ operations.
First principles: extend running totals to 2-D
Let S[r][c] be the sum of everything above and to the left of (r, c) (exclusive), so S has one extra row
and column of zeros. Then a rectangle is the big top-left block, minus the strip above it, minus the strip to its
left, plus the corner that was subtracted twice:
rect(r1..r2, c1..c2) = S[r2+1][c2+1] − S[r1][c2+1] − S[r2+1][c1] + S[r1][c1]
Building S uses the same inclusion–exclusion: S[r+1][c+1] = grid[r][c] + S[r][c+1] + S[r+1][c] − S[r][c].
import random
def build_2d_prefix(grid):
R, C = len(grid), len(grid[0])
S = [[0] * (C + 1) for _ in range(R + 1)]
for r in range(R):
for c in range(C):
S[r + 1][c + 1] = grid[r][c] + S[r][c + 1] + S[r + 1][c] - S[r][c]
return S
def rect_sum(S, r1, c1, r2, c2):
return S[r2 + 1][c2 + 1] - S[r1][c2 + 1] - S[r2 + 1][c1] + S[r1][c1]
def rect_sum_brute(grid, r1, c1, r2, c2):
return sum(grid[r][c] for r in range(r1, r2 + 1) for c in range(c1, c2 + 1))
rng = random.Random(3)
for _ in range(100):
R, C = rng.randint(1, 12), rng.randint(1, 12)
grid = [[rng.randint(-9, 9) for _ in range(C)] for _ in range(R)]
S = build_2d_prefix(grid)
for _ in range(30):
r1, r2 = sorted(rng.randrange(R) for _ in range(2))
c1, c2 = sorted(rng.randrange(C) for _ in range(2))
assert rect_sum(S, r1, c1, r2, c2) == rect_sum_brute(grid, r1, c1, r2, c2)
print("2-D prefix sums agree with brute force")
Cost: O(R · C) to build, O(1) per query, O(R · C) space.
4. The reverse problem: many range updates, then read everything
Problem. Start with n zeros. Apply q updates "add v to every position from l to r". Then return the final array.
ML context. Given many user sessions as (start minute, end minute), count how many sessions are active in each minute: each session is a +1 range update. The same shape appears when marking token spans for labels, or summing overlapping GPU reservations per hour.
Brute force
def apply_updates_brute(n, updates):
a = [0] * n
for l, r, v in updates:
for i in range(l, r + 1): # O(r − l) per update
a[i] += v
return a
assert apply_updates_brute(6, [(1, 3, 5), (2, 5, 2)]) == [0, 5, 7, 7, 2, 2]
print("brute force works")
Cost: O(n · q) worst case. 10⁵ sessions spanning a 10⁶-minute timeline would be 10¹¹ steps.
First principles: record only where things change
A range update changes the array's differences in just two places: at l the value jumps up by v, and just after
r it drops back by v. So record those two edges in a difference array D, then one prefix sum over D
rebuilds the values. (This is prefix sums run backwards.)
import random
from itertools import accumulate
def apply_updates_diff(n, updates):
D = [0] * (n + 1) # one extra slot so r + 1 is always valid
for l, r, v in updates:
D[l] += v # the value steps up at l
D[r + 1] -= v # and steps back down after r
return list(accumulate(D))[:n] # one O(n) sweep rebuilds every value
def apply_updates_brute(n, updates):
a = [0] * n
for l, r, v in updates:
for i in range(l, r + 1):
a[i] += v
return a
assert apply_updates_diff(6, [(1, 3, 5), (2, 5, 2)]) == [0, 5, 7, 7, 2, 2]
rng = random.Random(4)
for _ in range(300):
n = rng.randint(1, 30)
ups = []
for _ in range(rng.randint(0, 20)):
l = rng.randrange(n)
ups.append((l, rng.randrange(l, n), rng.randint(-5, 5)))
assert apply_updates_diff(n, ups) == apply_updates_brute(n, ups)
print("difference array agrees with brute force: O(n + q)")
Cost: O(1) per update, O(n) for the final sweep: O(n + q) total, O(n) space.
Quick check
Each of 10⁵ user sessions is a (start, end) minute range on a 10⁶-minute timeline. You need the number of active sessions in every minute. What's the efficient approach?
Show the answer
C. Difference array: +1 at start, −1 after end, then one prefix sweep: O(minutes + sessions) — Each range update becomes two O(1) marks; one sweep turns the marks into counts.
5. When the constraints change
Prefix sums and difference arrays both rely on the data being fixed while you query (or all updates arriving before any reads). Break that, and you need something else.
| If the constraint becomes… | Best approach | Update | Query |
|---|---|---|---|
| One query | Brute force | — | O(n) |
| Many queries, fixed data | Prefix sums | O(n) rebuild | O(1) |
| Many range updates, then read all | Difference array | O(1) | O(n) once |
| Point updates mixed with range queries | Fenwick tree | O(log n) | O(log n) |
| Range updates mixed with range queries | Segment tree with lazy updates | O(log n) | O(log n) |
| 2-D grid, fixed | 2-D prefix sums | O(R·C) rebuild | O(1) |
| Range min/max instead of sum | Sparse table (static) or segment tree | — | O(1) / O(log n) |
| Floats over very long arrays | Prefix sums with care (rounding drift) | — | O(1) |
Two rows deserve a sentence each:
- Min/max: prefix sums need subtraction to "remove" the part before
l. There's no subtraction for min or max, so prefix sums can't answer range-minimum queries. (Same lesson as rolling max in lesson 1.1.) - Floats: summing 10⁸ floats into one running total accumulates rounding error, so
P[r+1] − P[l]can be visibly off for short ranges deep into the array. Use 64-bit floats, or compensated (Kahan) summation, or recompute short ranges directly.
Quick check
Why can't prefix sums answer 'minimum value between l and r' in O(1)?
Show the answer
A. Prefix sums work by subtracting the part before l, and there's no operation that 'subtracts' a minimum; you need a structure like a sparse table or segment tree — The trick depends on an inverse operation. Sums have subtraction; min and max don't.
6. Preview: prefix sums plus a hash map
One more combination appears constantly in interviews: "count subarrays whose sum is exactly k". A subarray
l..r sums to k exactly when P[r+1] − P[l] = k, that is, when an earlier prefix equals P[r+1] − k. Counting
earlier prefixes in a hash map turns an O(n²) search into O(n). That's lesson 2.8 (Subarray Sum Equals K); it's
the complement idea from Two Sum, applied to prefix sums.
7. Saying it out loud
"Brute force sums each range: O(n · q). Ranges overlap, so I precompute running totals once in O(n), and each query is a difference of two of them, O(1). In 2-D the same idea needs inclusion–exclusion: four lookups. If the problem were many range updates before reading, I'd flip it to a difference array: two marks per update and one sweep, O(n
- q). If updates and queries interleave, I'd switch to a Fenwick or segment tree at O(log n) each."
Check yourself
- Write the formula for a range sum using prefix sums, and say what makes it work.
- How do prefix sums count things that aren't numbers?
- Derive the 2-D rectangle formula from inclusion–exclusion.
- What does a difference array record, and how does it rebuild the final values?
- Which constraint breaks prefix sums, and what replaces them?
- Why can't prefix sums answer range minimums?
Answers
sum(a[l..r]) = P[r+1] − P[l]; it works because sums can be subtracted to remove the prefix before l.- Encode each element as 0/1 for the property, then prefix-sum the indicators.
- Take the block above-left of the bottom-right corner, subtract the strip above and the strip to the left, then add back the top-left corner that was subtracted twice.
- Only the edges of each update (+v at l, −v after r); a prefix sum over those marks gives every position's total.
- Updates interleaved with queries; a Fenwick tree (point updates) or a segment tree (range updates) keeps both at O(log n).
- There's no inverse for min, so you can't remove the part before l.