2D Prefix Sums and Difference Arrays
Rectangle sums in O(1), and many range updates in O(1) each.
12 min, 0 of 3 activities solved
View cheatsheetGetting Python ready… examples can run in a moment.
2D prefix sums. For a grid, let P[r][c] be
the sum of the rectangle above and left of cell
(r, c): rows 0..r-1, columns 0..c-1. Pad
with an extra row and column of zeros, just like
the leading 0 in 1D.
Build it by inclusion-exclusion:
P[r+1][c+1] = grid[r][c]
+ P[r][c+1] (above)
+ P[r+1][c] (left)
- P[r][c] (counted twice)
And query the rectangle (r1, c1) to
(r2, c2) the same way:
+-----+-----+
| A | B | want = D
+-----+-----+ = ALL - (A+B) - (A+C) + A
| C | D |
+-----+-----+
sum = P[r2+1][c2+1] - P[r1][c2+1]
- P[r2+1][c1] + P[r1][c1]
The + P[r1][c1] adds back block A, which the
two subtractions removed twice.
Rectangle sums on a small grid
The bottom-right entry of P is the sum of the
whole grid (45). Try rect(0, 1, 1, 2): it
should be 2 + 3 + 5 + 6 = 16.
In the 2D rectangle-sum formula, why is P[r1][c1] ADDED back?
Difference arrays: prefix sums in reverse. Now
flip the problem: many updates like "add v to
every element in l..r", then read the final
array once. Looping over each range is O(n) per
update.
Instead, record only where each change starts and stops:
diff[l] += v # from l on, values go up by v
diff[r + 1] -= v # after r, cancel it
After all updates, a prefix sum over diff
rebuilds the real values. Each update is O(1); the
final pass is O(n). Give diff one extra slot so
r + 1 never falls off the end.
n = 5, add 2 to [1..3]:
diff = [0, 2, 0, 0, -2, 0]
prefix → [0, 2, 2, 2, 0]
What does this print?
Apply range updates
Write range_add(n, updates). Start from an array
of n zeros. Each update (l, r, v) adds v
to every index from l to r inclusive
(0-indexed). Return the final array.
Use a difference array: O(1) per update, then one prefix-sum pass.