PrefixAlgorithmaka summed-area table, integral image, matrix prefix sum, cumulative sum matrix

2D Prefix Sum

Precompute P[i][j] = sum of the rectangle from (0,0) to (i-1,j-1) so any submatrix sum is four lookups via inclusion–exclusion.

▶ VisualizePattern: Prefix SumPractice (2)
Progress

Overview

A 2D prefix sum (summed-area table, or integral image in computer vision) extends Prefix Sum to matrices. P[i][j] holds the sum of all cells with row < i and column < j. Building it costs O(R·C); after that the sum of any axis-aligned submatrix with corners (r1, c1) to (r2, c2) inclusive is P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1] — four reads, O(1).

It is the standard tool for Range Sum Query 2D, counting cells of a type in a rectangle, "maximum sum submatrix of size k × k", and — combined with a 1D technique over column ranges — for maximum-sum submatrix in O(C² · R) using Kadane's Algorithm. The same corner-marking idea in reverse gives 2D Difference Array range updates.

matrixsubmatrixrange queryinclusion-exclusionO(1) queryintegral image

Intuition

A mental model before the formal terms.

Imagine every cell knows the total weight of everything above-and-left of it, including itself. To weigh a rectangle in the middle of the grid, take the big top-left total at its bottom-right corner, chop off the strip above it and the strip to its left — but those two strips overlap in the top-left corner block, which was removed twice, so add it back once. Four numbers, no scanning.

How it works

  1. Allocate P of size (R+1) × (C+1) with row 0 and column 0 all zeros (sentinels).
  2. For each i in 1..R, j in 1..C: P[i][j] = a[i-1][j-1] + P[i-1][j] + P[i][j-1] − P[i-1][j-1].
  3. Query sum(r1, c1, r2, c2) (inclusive): P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1].
  4. Alternative build: first prefix-sum each row, then prefix-sum each column of the result — same table, sometimes easier to write correctly.
  5. For k × k window problems, evaluate the query for every valid top-left corner: O(R·C) after preprocessing.

Why it works

Build recurrence by inclusion–exclusion: the rectangle [0,i) × [0,j) is the union of [0,i-1) × [0,j) (above) and [0,i) × [0,j-1) (left) plus the single cell (i-1, j-1). The two rectangles overlap in [0,i-1) × [0,j-1), which is counted twice in the sum P[i-1][j] + P[i][j-1], so subtract P[i-1][j-1] once.

Query by inclusion–exclusion: the target rectangle [r1,r2] × [c1,c2] equals the big rectangle P[r2+1][c2+1] minus the rows above (P[r1][c2+1]) minus the columns to the left (P[r2+1][c1]); those two removed regions overlap in P[r1][c1], which was subtracted twice, so add it back. Every cell in the target is counted exactly once; every cell outside it nets to zero.

The sentinel row and column make queries touching the top or left edge (r1 = 0 or c1 = 0) fall out of the same formula with no special cases.

Recognition

How to tell a problem wants this.

  • "Sum of the elements inside the rectangle defined by its upper-left (row1, col1) and lower-right (row2, col2)", "submatrix sum", "Range Sum Query 2D — Immutable".
  • "Count the number of 1s / obstacles / trees inside a rectangle" for many rectangles.
  • "Maximum sum of a k × k block", "number of submatrices that sum to target", "largest square with sum ≤ threshold" (binary search on size plus O(1) block sums).
  • Matrix dimensions up to 10^3 × 10^3 and 10^4–10^5 queries — O(R·C) per query is far too slow, O(1) is required.
  • Image processing terms: "integral image", "box filter", "Haar features".
“sum of subarray” → Prefix Sum

Interactive visualization

Play, step, change the input. ← → and space work too.

0
0
0
0
0
0
0
0
0
Input matrix a
c0c1c2c3
3014
5632
1201
4101
1/19Build a (R+1)×(C+1) prefix table where P[r][c] is the sum of the top-left r×c block of a. Row 0 and column 0 are zeros so borders need no special cases.
Cell being computedAdded (up / left)Subtracted (diagonal)Queried submatrixAnswer
PseudocodeLearn 2D Prefix Sum →
1P = (R+1) × (C+1) zeros
2for r in 1..R, c in 1..C:
3  P[r][c] = a[r-1][c-1] + P[r-1][c] + P[r][c-1] - P[r-1][c-1]
4sum(r1,c1,r2,c2) = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
Variables
R4
C4
Complexity
best O(R·C)
avg O(R·C + q)
worst O(R·C + q)
space O(R·C)
Speed

Pseudocode

1P = (R+1) x (C+1) zeros
2for i in 1..R:
3  for j in 1..C:
4    P[i][j] = a[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]
5sum(r1, c1, r2, c2) =
6  P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Implementations

1# Range Sum Query 2D - Immutable: O(R*C) build, O(1) sum_region
2class NumMatrix:
3    def __init__(self, a: list[list[int]]):
4        rows = len(a)
5        cols = len(a[0]) if rows else 0
61 · Allocate (R+1) x (C+1) with a sentinel row and column of zeros
7        self.p = [[0] * (cols + 1) for _ in range(rows + 1)]
82 · Build by inclusion-exclusion: cell + above + left - overlap
9        for i in range(1, rows + 1):
10            for j in range(1, cols + 1):
11                self.p[i][j] = (a[i - 1][j - 1]
12                                + self.p[i - 1][j]
13                                + self.p[i][j - 1]
14                                - self.p[i - 1][j - 1])
15 
163 · A rectangle sum is four lookups with the same sign pattern
17    def sum_region(self, r1: int, c1: int, r2: int, c2: int) -> int:
18        p = self.p
19        return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1]
Walkthrough
  1. The table is built with a list comprehension [[0] * (cols + 1) for _ in range(rows + 1)] — a fresh row list per iteration.
  2. len(a[0]) if rows else 0 guards the empty matrix before any indexing.
  3. The build recurrence is wrapped in parentheses across four lines — Python's implicit line continuation keeps the inclusion-exclusion readable.
  4. Local alias p = self.p in sum_region skips repeated attribute lookups in the hot path.
  5. Python ints never overflow, so the table needs no width analysis at any matrix size.
Complexity (this implementation)
time O(R·C + q) · space O(R·C)

Nested Python lists store pointers to int objects — several times the memory of a numpy int64 array for big grids.

Language notes
  • The aliasing trap is [[0] * (cols + 1)] * (rows + 1): the outer * copies *references*, so all rows are the same list. The comprehension form creates distinct rows.
  • For heavy numeric grids, numpy.cumsum(numpy.cumsum(a, axis=0), axis=1) (with zero padding) builds the table in vectorised C.
  • itertools.accumulate handles the row pass; the column pass still needs a loop — the manual double loop is clearer.
Common mistakes in this language
  • Building rows with * (rows + 1) and aliasing every row to one list.
  • Writing range(rows) in the build and leaving the last row of the table zero.
  • Flipping the sign on the overlap term — the pattern is + big, - above, - left, + corner, in both build and query.
Language differences that matter here
  • Overflow of the corner total (R * C * max|a|): C++ must store long long (int overflow is UB); JS/TS doubles are exact to 2^53; Python ints are unbounded.
  • Row aliasing traps: JS new Array(n).fill(row) and Python [row] * n both alias one row object across the whole table; C++ vector construction deep-copies rows and has no such trap.
  • Memory layout: C++ nested vectors scatter rows (flat vector + manual indexing is cache-friendlier); Python nested lists box every int (numpy fixes it); JS engines usually keep small-int arrays packed.
  • Empty-matrix guard: C++ a[0] on an empty vector is UB, Python raises IndexError, JS returns undefined and poisons arithmetic with NaN — all three need the explicit rows ? ... : 0 check.
  • Vectorised builds: Python has numpy.cumsum twice; C++ can std::partial_sum per row then per column; JS/TS hand-roll the double loop.

Complexity

Best
O(R·C)
Average
O(R·C + q)
Worst
O(R·C + q)
Space
O(R·C)

O(R·C) build, O(1) per rectangle query. Generalizes to d dimensions with 2^d terms per query.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Many rectangle-sum (or rectangle-count) queries on a static matrix.
  • Sliding a fixed-size block over a grid and scoring each position.
  • As the inner primitive of maximum-sum submatrix, "count submatrices with sum = target", or binary search on block size.
  • Image processing: box blur, integral-image features.
Avoid it when
  • Cells are updated between queries — use a 2D Fenwick Tree (O(log R · log C) per operation) or a 2D segment tree.
  • Rectangle max/min queries — not invertible; use a 2D sparse table or segment tree.
  • Very large sparse grids (10^9 × 10^9 coordinates) — compress coordinates first, or use offline sweeps.
  • Single query on a small matrix — a double loop is clearer.

Alternatives

Prefix SumFenwick TreeSegment TreeDifference Array

Common mistakes

  • Omitting the sentinel row/column and then writing separate branches for r1 = 0 or c1 = 0.
  • Getting the sign pattern wrong: it is + big − above − left + corner for both build and query. Writing − corner double-subtracts.
  • Mixing inclusive (r2, c2) from the problem with the exclusive indexing of P — the +1 belongs on r2/c2, not on r1/c1.
  • Overflow in Java/C++/Go when R · C · max|a| exceeds 2^31; use 64-bit storage.
  • Confusing row/column order when the matrix is given as a[row][col] but the query is (x, y).

Interview patterns

  • Range Sum Query 2D — Immutable (the NumMatrix class).
  • Number of Submatrices That Sum to Target: fix a pair of rows, collapse columns to a 1D array, then Subarray Sum Equals K.
  • Maximum Side Length of a Square with Sum ≤ Threshold: binary search on side length with O(1) square sums.
  • Matrix Block Sum: each output cell is a (2k+1) × (2k+1) clamped rectangle query.
  • Count Submatrices With All Ones / largest rectangle of 1s — prefix counts per row then a Monotonic Stack (largest rectangle in histogram) per row.
Interview questions on this
Mock interviews

Example problems

Subarray Sum Equals KmediumRange Sum Query 2D — Immutablemedium