2-D Prefix Sums

A 2-D prefix sum is the matrix version of the running-total trick: precompute one table and then read the sum of any axis-aligned rectangle in constant time with four lookups. It turns "what is the total of this sub-block?" from an O(m·n)-per-query scan into O(1).

For the grid [[3, 0, 1], [2, 1, 4], [1, 5, 1]], the sum of the rectangle from (0,1) to (1,2) is 0 + 1 + 1 + 4 = 6. We will read exactly that with the four-corner formula.

Intuition

Think of pre[i][j] as "how much money is in the whole rectangle from the top-left corner of the grid down to here?" Once you have those running totals, any sub-rectangle is the big rectangle minus the parts you do not want.

Imagine cutting out a rectangle from inside a larger one. Start with the big block that ends at the bottom-right corner. Subtract the strip sitting above your rectangle and the strip sitting to its left. But those two strips overlap in one square — the top-left corner block — and you just removed it twice, so you add it back once. That add-back is the classic inclusion-exclusion move, and it is the only subtle part of the whole technique.

Building the table uses the very same idea in reverse. Each new cell is its own grid value plus the cell above plus the cell to the left, minus the top-left overlap that those two share.

Walk through it

Step through the animation on the right. The left grid is the input; the right grid is the padded pre table, which has an extra zero row on top and an extra zero column on the left so every neighbour read is in bounds.

Phase 1 — build. The fill pointer sweeps the table cell by cell, row by row. For each target cell, three contributing neighbours light up: the cell up and the cell left are added (shown as one color), and the up-left overlap is subtracted (a second color) because it is double-counted by the other two. Watch pre[2][2] get written as grid[1][1] + up + left - upLeft.

Phase 2 — query. Now we answer the rectangle (0,1)..(1,2). The four corners of the pre table light up with their inclusion-exclusion signs: the big block pre[2][3] is +, the strip-above pre[0][3] and strip-left pre[2][1] are both -, and the doubly-removed corner pre[0][1] is +. Add them with their signs and the rectangle sum drops out: 8 - 1 - 3 + 2 = 6.

The code, line by line

def build_prefix(grid):
    m, n = len(grid), len(grid[0])
    pre = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            pre[i + 1][j + 1] = (grid[i][j]
                + pre[i][j + 1] + pre[i + 1][j]
                - pre[i][j])
    return pre
 
def rect_sum(pre, r1, c1, r2, c2):
    return (pre[r2 + 1][c2 + 1]
            - pre[r1][c2 + 1]
            - pre[r2 + 1][c1]
            + pre[r1][c1])

• Line 3 allocates the (m+1)×(n+1) table filled with zeros. That extra zero row and zero column are the padding — they make pre[i][j+1], pre[i+1][j], and pre[i][j] always valid, even on the first row and column.
• Lines 6–8 are the build recurrence: each cell is its grid value plus the cell directly above plus the cell directly to the left, minus the top-left overlap that those two both include.
• Line 12 reads the big block pre[r2+1][c2+1] — everything from the grid origin to the bottom-right corner of the query.
• Lines 13–14 subtract the strip above and the strip to the left of the rectangle.
• Line 15 adds back pre[r1][c1], the top-left corner block that both strips removed, fixing the double subtraction.

Complexity

The win is amortized over many queries: you pay O(m*n) once to build, then every rectangle-sum question — no matter how big the rectangle — costs four reads. With q queries the total is O(m*n + q) instead of O(q * m * n) for repeated brute-force scans.

When to use / pitfalls

Practice