2D prefix sums

41 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A 3×3 grid of numbers, and lots of questions of the form "what is the sum of the rectangle from row 1, column 1 to row 2, column 2?" By hand you add up the cells inside the rectangle each time. A rectangle of h rows and w columns costs h · w additions, and for a big grid with thousands of queries that is far too slow: a 1000×1000 grid with 10,000 full-size queries is ten billion additions.

In one dimension the fix is prefix sums: store the running total and get any range by one subtraction. The question is how to do the same in two dimensions.

Build the structure, one piece at a time

Piece one: define P[i][j] as the sum of the whole rectangle from the top-left corner (0, 0) down to cell (i − 1, j − 1). Add an extra row and column of zeros at the top and left so that P[0][·] = P[·][0] = 0, which removes every "is this the edge?" special case. Use the grid

Piece two: build P one cell at a time with the rule

P[i][j] = grid[i − 1][j − 1] + P[i − 1][j] + P[i][j − 1] − P[i − 1][j − 1]

Read it as: the cell itself, plus the rectangle above it, plus the rectangle to its left, minus the rectangle that those two both contain (the one diagonally up-left), which would otherwise be counted twice. The first few cells: P[1][1] = 3; P[1][2] = 0 + 0 + 3 − 0 = 3; P[2][1] = 5 + 3 + 0 − 0 = 8; P[2][2] = 6 + 3 + 8 − 3 = 14. The finished table, with the zero border, is

Piece three: answer a query with four lookups. For the rectangle with top-left (r₁, c₁) and bottom-right (r₂, c₂):

sum = P[r₂+1][c₂+1] − P[r₁][c₂+1] − P[r₂+1][c₁] + P[r₁][c₁]

For rows 1–2, columns 1–2: 21 − 4 − 9 + 3 = 11, and indeed 6 + 3 + 2 + 0 = 11.

Why it is correct

Both formulas are the same picture, called inclusion–exclusion. The big corner rectangle down to (r₂, c₂) contains our target plus a strip above it and a strip to its left. Subtracting the corner rectangle above (down to row r₁ − 1) removes the top strip; subtracting the corner rectangle to the left removes the left strip. But the small corner rectangle up-left of the target was inside both strips, so it was removed twice; adding it back once leaves exactly the target. The build rule is the same argument applied to a rectangle of one cell. The invariant "P[i][j] is the sum of the corner rectangle" holds for the zero border and is preserved by each build step because the step is itself an exact inclusion–exclusion.

Why it is fast

Building P is one constant-time rule per cell: O(m · n) for an m×n grid. Each query is four lookups and three arithmetic operations: O(1), no matter how large the rectangle. The 1000×1000 grid with 10,000 queries costs about a million steps to build plus 70,000 for the queries, instead of ten billion. Memory is one extra grid.

How to recognise it in an interview

Cues: "sum of a submatrix", "many queries", "count rectangles whose sum is", "largest square with sum at most". Any time a question asks about the total inside a rectangle more than a handful of times, build the table first.

Say: "I will precompute 2-D prefix sums with a zero border, then every rectangle sum is four lookups." Range Sum Query 2D - Immutable is exactly that. Maximum Side Length of a Square with Sum Less than or Equal to Threshold uses the O(1) rectangle sum inside a search over the side length. Matrix Block Sum is one query per cell with the rectangle clipped to the grid edges.

02The idea in one line

Rectangle sum from four corner lookups by inclusion–exclusion.

Reach for it when: Many rectangle-sum queries, square with sum ≤ threshold, matrix block sums.

Cost: O(mn) build, O(1) per query.

03The walk-through, step by step

The video works one example: Range Sum Query 2D on a 3×3 matrix. These are its captions in order, so you can follow without the video or check a step you missed.

1. Precompute corner sums once, then any rectangle is four lookups
2. P[1][1] = 3 + 0 + 0 − 0 = 3
3. P[2][2] = 6 + 3 + 8 − 3 = 14
4. P[2][3] = 3 + 4 + 14 − 3 = 18
5. P[3][3] = 0 + 18 + 17 − 14 = 21
6. Table complete: each cell = cell + above + left − diagonal
7. Query: sum of rows 1..2, cols 1..2 (the 6,3,2,0 block)
8. = P[3][3] − P[1][3] − P[3][1] + P[1][1]
9. = 21 − 4 − 9 + 3 = 11
10. Build O(m·n), then every query is O(1)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Prefix Sums: Prefix sum + hashmap, Prefix and suffix products, Difference array (range add).