2D Prefix Sum - Algorithm Tutorial | Repovive

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.

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:

\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}

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

\begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 3 & 6 \\ 0 & 5 & 12 & 21 \\ 0 & 12 & 27 & 45 \end{bmatrix}

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

$P[3][3] - P[1][3] - P[3][1] + P[1][1]$ ✓

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 .

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

2D Prefix Sum Algorithm Tutorial

Introduction

Practice this Algorithm

Related Algorithms

Building the Prefix Sum

Querying a Submatrix

Visual Example

Common Mistakes