2D Prefix Sums

Extending to a grid

A matrix version of the same problem: given a 2D grid, answer many "sum of the rectangle from (r1, c1) to (r2, c2)" queries in O(1) each, after preprocessing. The 1D idea generalizes — but the subtraction needs care, because a 2D rectangle isn't a simple prefix-minus-prefix the way a 1D range was.

Picture a large rectangular rug marked off in a grid of unit squares, and imagine you could weigh any rectangular patch of it instantly if you already knew the weight of every patch anchored at the rug's corner. To find the weight of a patch that starts partway in — not anchored at the corner — you'd naturally try: take the big corner-anchored patch that reaches the patch's far edge, then trim off the strip above it and the strip to its left. But those two strips overlap in one small square, up in the corner — trim both and you've cut that shared square out twice. You have to weigh it back in once to get the patch you actually wanted. That's the whole 2D story in one picture; the rest of this lesson is just writing it as arithmetic.

Building the 2D prefix sum

Define prefix[i][j] as the sum of every cell in the rectangle from (0,0) to (i−1, j−1) — the top-left rectangle "ending" at row i, column j (again 1-indexed to sidestep boundary special cases, prefix[0][*] = prefix[*][0] = 0). The recurrence builds each cell from three neighbors already computed:

prefix[i][j] = grid[i-1][j-1]                  (this cell's own value)
             + prefix[i-1][j]                   (rectangle above)
             + prefix[i][j-1]                   (rectangle to the left)
             - prefix[i-1][j-1]                 (the overlap, counted twice above)

grid:              prefix (1-indexed, padded):
1  2  3             0  0  0  0
4  5  6             0  1  3  6
7  8  9             0  5 12 21
                     0 12 27 45

The - prefix[i-1][j-1] term is the crux: the "above" rectangle and the "left" rectangle both already include the top-left overlapping rectangle, so adding both double-counts it — subtracting it once corrects the overcounting. This is inclusion-exclusion, the same principle behind counting unions of overlapping sets, applied to areas instead of set sizes.

def build_prefix_2d(grid: list[list[int]]) -> list[list[int]]:
    rows, cols = len(grid), len(grid[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            prefix[i][j] = (
                grid[i - 1][j - 1]
                + prefix[i - 1][j]
                + prefix[i][j - 1]
                - prefix[i - 1][j - 1]
            )
    return prefix

Querying a rectangle in O(1)

The sum of the rectangle from (r1, c1) to (r2, c2) inclusive (0-indexed into grid) is another inclusion-exclusion, in reverse — start from the big rectangle ending at (r2, c2), then subtract the strip above the region and the strip to its left, then add back the corner that got subtracted twice:

sum = prefix[r2+1][c2+1]
    - prefix[r1][c2+1]        (strip above the region)
    - prefix[r2+1][c1]        (strip to the left of the region)
    + prefix[r1][c1]          (corner subtracted twice — restore it once)

Four terms, four array lookups, O(1) regardless of the rectangle's size — exactly the 1D case's guarantee, extended by one dimension of inclusion-exclusion.

The pattern behind the pattern

Both formulas — build and query — are the same move: express a region as a combination of easier-to-know regions, correcting for double-counted overlap. This is worth recognizing as a general technique (inclusion-exclusion), not a 2D-prefix-sum-specific trick — it resurfaces anywhere you need "count/sum of A or B" from "count/sum of A" and "count/sum of B" when A and B might overlap.