2D Prefix Sum - Algorithm Tutorial | Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/2d-prefix-sum

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/2d-prefix-sum

Introduction

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)

Building the Prefix Sum

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

text

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

Querying a Submatrix

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

text

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

Visual Example

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]$ $= 45 - 6 - 12 + 1 = 28$ ✓

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

Common Mistakes

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

2D Prefix Sum Algorithm Tutorial

Introduction

Building the Prefix Sum

Querying a Submatrix

Visual Example

Common Mistakes

Implement this Algorithm

Related Algorithms