Prefix Sum

01 / The shared mechanism

Pay O(N) once to build a cumulative table — every range query that follows reduces to a constant-time subtraction. Flip the trick inside-out and you get cheap range updates instead.

01 / The one-sentence essence

Pay O(N · M) once to build a corner table — every rectangle-sum query that follows is a single inclusion–exclusion over four prefix corners.

Problemsum of mat[r1..r2][c1..c2] in O(1)Matrix5×5Rect(1,1)..(3,3)

mat

prefix

Two grids: input mat on the left, prefix table prefix on the right. The prefix has one extra row and column of zeros along the top and left.

step

0 / 31

phase

build

result

0 / 31

r1c1r2c2

02 / The pattern signature

# build the 2-D prefix table onceprefix[0][*] ← 0; prefix[*][0] ← 0for i in 0..n−1:for j in 0..m−1:prefix[i+1][j+1] ← mat[i][j]+ prefix[i][j+1] + prefix[i+1][j] − prefix[i][j]# query: rectangle sum (r1, c1)..(r2, c2) by inclusion–exclusionrectSum(r1, c1, r2, c2) ←prefix[r2+1][c2+1] − prefix[r1][c2+1] − prefix[r2+1][c1] + prefix[r1][c1]# subtract the two over-stripes, then add back the doubly-removed corner

03 / When to recognize this pattern

"sum of a rectangle in a matrix"

The literal canonical signal. The grid is fixed; queries can be in any order, any count. Build once, query forever — in two dimensions.

"block sum / sub-matrix sum"

Block, tile, window, region — anything that reads as a contiguous rectangle of cells collapses to four corner reads.

"inclusion–exclusion on corners"

The visual hook of this pattern. Two big rectangles overlap a corner; you subtract both and add it back once.

"many rectangle queries"

Same amortization story as 1-D — only pays off when query count is not tiny. A single rectangle sum is no faster than a naïve scan.

04 / Common pitfalls

Forgetting to add back the corner.

The two subtractions (prefix[r1][c2+1] and prefix[r2+1][c1]) both contain the top-left rectangle (0,0)..(r1−1, c1−1) — you've removed it twice. The + prefix[r1][c1] restores it once. Drop the add-back and every query is too small by exactly that corner's sum.

ii.

Off-by-one on the +1 offsets in both dimensions.

The prefix is (n+1) × (m+1) with a zero-padded top row and left column. Every read of the table is at r+1 / c+1 for the inclusive far corner and at r / c for the exclusive near corner. Mixing the two conventions inside one query is the #1 source of bugs here.

iii.

Building cell-by-cell with the wrong recurrence direction.

Each prefix[i+1][j+1] reads three already-computed cells (top, left, top-left). You must iterate rows outer and columns inner (or vice versa) — never diagonally or bottom-up — or those reads will be stale.

05 / Go practice — on LeetCode

Four problems, ordered by difficulty. No solutions here, by design.

01Range Sum Query 2D — Immutable— LC 304medium→02Matrix Block Sum— LC 1314medium→03Find Kth Largest XOR Coordinate Value— LC 1738medium→04Max Sum of Rectangle No Larger Than K— LC 363hard→

— / When to use which

1-D linear

Use when you have many range-sum queries on a fixed array.

range-sum · running-total · LC 303

2-D grid

Use for rectangle queries on a matrix — inclusion-exclusion on the corners.

matrix-region · block-sum · LC 304

difference

Flip the direction: many range updates, then a single read of every cell.

range-add · car-pooling · flight-bookings

hash map

Count subarrays whose sum hits a target — prefix + map of seen prefixes.

subarray-sum-k · divisible-by-k · LC 560