2D Prefix Sum Algorithm Tutorial

The 2D Prefix Sum technique extends the 1D prefix sum to matrices, enabling $O(1)$ range sum queries after $O(nm)$ preprocessing.

Problem: Given an $n \times m$ grid, answer $q$ queries asking for the sum of a rectangular submatrix.

Naive approach: For each query, iterate over the submatrix. Time: $O(q \cdot nm)$.

With 2D prefix sums: Preprocess in $O(nm)$, answer each query in $O(1)$. Total: $O(nm + q)$.

Applications:

• Image processing (box blur, integral images)
• Game development (terrain analysis)
• Competitive programming (range queries on grids)

Define $P[i][j]$ as the sum of all elements in the rectangle from $(1,1)$ to $(i,j)$.

Formula: $P[i][j] = a[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]$

We add the cell value, plus the prefix sum above, plus the prefix sum to the left, then subtract the overlap (which was counted twice).

function build_prefix(grid):
    n, m = dimensions of grid
    P = (n+1) x (m+1) array of zeros  // 1-indexed with padding

    for i from 1 to n:
        for j from 1 to m:
            P[i][j] = grid[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]

    return P

Time: $O(nm)$, Space: $O(nm)$

To find the sum of the rectangle from $(r_1, c_1)$ to $(r_2, c_2)$:

Formula: $\text{sum} = P[r_2][c_2] - P[r_1-1][c_2] - P[r_2][c_1-1] + P[r_1-1][c_1-1]$

Intuition: Start with the entire rectangle from $(1,1)$ to $(r_2, c_2)$. Subtract the region above and the region to the left. Add back the corner (subtracted twice).

function query(P, r1, c1, r2, c2):
    return P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]

Time per query: $O(1)$

Grid:

Prefix sum array $P$ (with zero padding):

Query: Sum of $(2,2)$ to $(3,3)$

$P[3][3] - P[1][3] - P[3][1] + P[1][1]$ $= 45 - 6 - 12 + 1 = 28$ ✓

Verification: $5+6+8+9 = 28$

1. Off-by-one errors with indexing

Use 1-indexed prefix sums with a padding row/column of zeros. This avoids special cases for $r_1=1$ or $c_1=1$.

2. Integer overflow

With $n=m=500$ and values up to $10^6$, the maximum sum is $500 \times 500 \times 10^6 = 2.5 \times 10^{11}$. Use 64-bit integers.

3. Confusing row/column order

Be consistent: $(r, c)$ means row $r$, column $c$. Some problems use $(x, y)$ which might mean column $x$, row $y$.

4. Forgetting the double subtraction

When building: subtract $P[i-1][j-1]$ (counted twice). When querying: add $P[r_1-1][c_1-1]$ (subtracted twice).

Complexity Summary:

• Preprocessing: $O(nm)$
• Per query: $O(1)$
• Total: $O(nm + q)$