Satellite imagery analysis. You have a grayscale image — a grid of pixel intensities, each cell storing a number from 0 to 255. A weather model asks: “What's the average brightness in this rectangular region?” An object detector asks: “What's the total intensity in this bounding box?” A compression algorithm asks a hundred thousand such questions per frame.

In 1D, you solved this elegantly. One prefix array, O(1) per query. But a 2D grid isn't a line — it's a sheet. The “sum of a rectangle” doesn't reduce to a single subtraction anymore. The brute force is nested loops: for each row in the rectangle, iterate across each column, summing as you go. For an m x n rectangle inside a 1000 x 1000 grid, that's up to a million additions per query. For 10,000 queries, that's 10 billion operations. Per frame.

What if you could answer any rectangular query — any top-left corner, any bottom-right corner, any size — with exactly 4 lookups and 3 arithmetic operations?

The idea is the same trade-off you used in 1D: precompute a table so that queries become cheap. But the precomputation is trickier. In 1D, each prefix cell depends on one predecessor. In 2D, the construction follows a pattern you'll discover when you try to fill the grid — and if you don't handle the overlap correctly, every cell in your table will be wrong.

Get the construction right, and you've unlocked O(1) rectangle queries. Get it wrong, and your table looks plausible but quietly double-counts an entire region.

First, feel the cost of brute force on a 2D grid. Then build the 2D prefix matrix — where each cell records the sum of the entire rectangle above and to the left.

The key twist: the construction formula has a subtraction term that doesn't exist in 1D. If you miss it, every cell is wrong.

The query formula — p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1] — looks like four arbitrary terms to memorize. It's not. It's inclusion-exclusion, the same counting principle you use when computing “how many people like cats OR dogs” from overlapping survey responses.

Let's walk through it with a concrete picture. Say you want the sum of a rectangle from row 2, column 1 to row 4, column 3 inside a larger grid. You have a 2D prefix table p where p[i][j] holds the sum of all cells from the origin (0,0) to (i-1, j-1).

Step 1 — Start with the big rectangle. p[r2+1][c2+1] gives you the sum of everything from the origin to the bottom-right corner of your query. This is too much — it includes cells above and to the left of your target rectangle.

Step 2 — Subtract the top strip. p[r1][c2+1] is the sum of everything from the origin down to just above your rectangle (same right boundary). Subtracting it removes all the rows you don't want above the query.

Step 3 — Subtract the left strip. p[r2+1][c1] is the sum of everything from the origin extending to the left of your rectangle (same bottom boundary). Subtracting it removes all the columns you don't want to the left of the query.

Step 4 — Add back the corner. Here's the catch: the top strip and the left strip overlap. The rectangle from the origin to (r1-1, c1-1) — the top-left corner region — was included in the big rectangle, then subtracted by the top strip, and subtracted again by the left strip. It's been removed twice. So you add it back once: + p[r1][c1].

That's the entire formula. It's not four things to memorize — it's one principle applied systematically: add the whole, peel off two overlapping pieces, correct for the double-peel.

The construction formula uses the same principle in reverse. To compute p[i][j], you add the cell above (p[i-1][j]), the cell to the left (p[i][j-1]), subtract the overlap (p[i-1][j-1]), and add the current grid value. It's inclusion-exclusion all the way down.

And the principle scales. For a 3D prefix cube (yes, these exist — think volumetric data, space-time queries), you'd have 8 terms: include the big cube, exclude three faces, re-include three edges, exclude the corner. Each additional dimension doubles the number of terms but follows the same alternating sign pattern: +, -, +, -, ... corresponding to subsets of dimensions.

The same inclusion-exclusion shows up everywhere in computer science: in probability (P(A or B) = P(A) + P(B) - P(A and B)), in combinatorics (counting elements in unions of sets), in Mobius inversion, and in database query optimization. Once you internalize the overlapping-rectangle picture, the formula writes itself — you never need to memorize it.

That's the real skill: not remembering p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1], but being able to derive it from first principles in thirty seconds by drawing two overlapping strips on the back of an envelope.