2D Prefix Sums and Difference Arrays

Prefix Sums, lesson 3 of 3

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 cheatsheet

Getting 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)

Here it is on grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]. Row and column labels are P's indices, so grid cell (r, c) lands in P[r + 1][c + 1].

Walkthrough

Build P for a 3 × 3 grid

012301230000000
Step 1 of 5

Row 0 and column 0 are padding zeros, the 2D version of the leading 0.

current / added
subtracted (counted twice)
done

Query the rectangle (r1, c1) to (r2, c2) the same way: take the big block up to the bottom-right corner, cut off the strip above and the strip to the left, then add back the corner block those two cuts both removed:

sum = P[r2+1][c2+1] - P[r1][c2+1]
    - P[r2+1][c1]   + P[r1][c1]
Walkthrough

rect(1, 1, 2, 2) on the grid

012012123456789
Step 1 of 5

Goal: rows 1..2, columns 1..2, that is 5 + 6 + 8 + 9 = 28.

still counted
cut off
cut off twice
the rectangle
Example

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.

Quiz

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.

Walkthrough

n = 5: add 2 to [1..3], then add 1 to [3..4]

diff000000012345out01234
Step 1 of 6

diff has n + 1 = 6 slots, all 0: no changes recorded yet.

+v: change starts
−v: change stops
rebuilt value
Quiz

What does this print?

Exercise

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.