In a 2D prefix-sum table, why is one corner term added back in the submatrix formula?
answer
- Two removals share a region
- Something got taken away twice
- Count each cell exactly once
- Inclusion-exclusion over four corners
- Corner term is zero at the edges
basics
~20 sBecause the two subtracted strips overlap. Removing everything above the submatrix and everything to its left takes the top-left corner rectangle away twice, so it must be added back once to leave each cell counted exactly once.
solid answer
~50 sA 2D prefix table stores, at `P[i][j]`, the sum of the whole rectangle from the origin to row i-1, column j-1. To get the sum of an inner block you start from the big rectangle that ends at its bottom-right corner, subtract the strip above it and the strip to its left — but those two strips both contain the rectangle above-and-left of the block, so that region has now been removed twice. Adding it back once restores the count: `P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]`. This is inclusion-exclusion, the same reasoning that builds the table (`P[i][j]` also subtracts one doubly-counted corner). Build is O(rows·cols), every query is O(1) with four lookups. The cruel part in review: omitting the `+ P[r1][c1]` term still passes any fixture whose block starts in row 0 or column 0, because that term is zero there.
code
pseudocode · 10 lines// grid[0..rows-1][0..cols-1], P is (rows+1) x (cols+1), zero-filled
for i in 0..rows-1:
for j in 0..cols-1:
P[i+1][j+1] = P[i][j+1] + P[i+1][j] - P[i][j] + grid[i][j]
...
// impressions in rows r1..r2, cols c1..c2, both ends included
answer = P[r2+1][c2+1]
- P[r1][c2+1] // strip above the block
- P[r2+1][c1] // strip left of the block
+ P[r1][c1] // removed twice, add back oncego deeper
Recall that a 2D block sum takes four table lookups, not a loop, and that the table is padded with a zero row and column. Being able to state the four-term shape is enough at this level.
Derive the formula out loud rather than reciting it: name what each term removes and why one region is removed twice. Expect to be asked for the build recurrence too, which hides the same subtraction.
Demonstrate how you would catch the missing corner term in review — an interior-block test with non-zero data above-and-left, checked against an independent brute-force scan. Note that the failure is a silently low number, not a crash.
Weigh the dense table against the workload: it duplicates the dataset in memory with wider accumulators, and the memory multiplies per added dimension. Decide when precomputed aggregates belong in the serving path versus being computed in a batch layer.
## The setup Picture an ad-impression heatmap: a grid where cell (i, j) holds impressions served in geographic band i during hour bucket j. Analysts ask for totals over rectangular blocks — a group of bands across a stretch of hours. Scanning a block costs O(height·width); with many queries over a static grid, precomputing pays. ## What the table holds Define `P[i][j]` as the sum of every cell in rows 0..i-1 and columns 0..j-1 — the axis-aligned rectangle anchored at the origin, with i rows and j columns. As in one dimension, the table gets an extra row and column of zeros (dimensions (rows+1) × (cols+1)) so that blocks touching row 0 or column 0 need no special case. ## Building it — inclusion-exclusion appears immediately `P[i+1][j+1] = P[i][j+1] + P[i+1][j] - P[i][j] + grid[i][j]` Read it as: the rectangle one row shorter, plus the rectangle one column narrower, minus their shared overlap (which the first two terms both counted), plus the new cell that neither contained. Drop the `- P[i][j]` and every total inflates, quietly and increasingly, as you move down and right. The build is one pass over the grid: O(rows·cols) time, O(rows·cols) memory. ## Querying — the same idea, mirrored For the inclusive block rows r1..r2, columns c1..c2: `P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]` - `P[r2+1][c2+1]` — everything from the origin down to the block's bottom-right corner. Too much. - `- P[r1][c2+1]` — remove the full-width strip above the block. - `- P[r2+1][c1]` — remove the full-height strip to its left. - Those two strips share the rectangle above-and-left of the block; it has been removed twice. - `+ P[r1][c1]` — add that shared rectangle back once. After the four terms, each cell inside the block is counted exactly once and each cell outside exactly zero times. Four lookups, three arithmetic operations, O(1) per query irrespective of block size. ## The reviewer's trap The missing `+ P[r1][c1]` is the defect that survives a test suite. `P[r1][c1]` is zero whenever `r1 = 0` or `c1 = 0`, because the padded row and column are zeros. So a fixture built from a single row of the grid, or any block anchored at the top or the left edge, passes with the broken formula. Only an interior block — one that starts at neither edge and has a non-empty region above-and-left — exposes it, and then the answer is merely *too small*, not obviously nonsense. When reviewing this code, the check is not "does the formula look symmetric" but "is there a test with r1 > 0 and c1 > 0, with non-zero data in the corner". Sign errors in the two subtracted terms fail the same way for the same reason. ## Cost and shape | Approach | Preprocess | Per block query | Extra space | |---|---|---|---| | Scan the block | none | O(height·width) | O(1) | | 2D prefix table | O(rows·cols) | O(1), four lookups | O(rows·cols) | The memory is the real constraint: the table is dense and mirrors the grid exactly, even if the grid is mostly zeros, and its entries are cumulative so they need a wider accumulator than the cells do. ## Generalising The pattern is dimension-agnostic. In d dimensions a block query is an alternating sum over the 2^d corners of the query box, with sign determined by how many coordinates are taken from the low end. Two dimensions gives the familiar four terms; three gives eight. Constant for fixed d, but the constant doubles per dimension and the table's memory multiplies, so beyond three dimensions this stops being attractive long before the arithmetic becomes the problem. Everything here depends on the same property as the one-dimensional case: the combining operation must be associative and invertible, since the whole derivation is additions and subtractions of overlapping regions.
- A colleague's submatrix query omits the corner term and all tests pass. Which test would you demand?One with an interior block — top row greater than 0, left column greater than 0 — and non-zero data in the rectangle above-and-left of it. The omitted term equals exactly that region's total, and it is zero whenever the block touches the top or left edge, which is why single-row and origin-anchored fixtures pass. Assert against a brute-force scan of the same block so the expected value is derived independently rather than copied from the implementation.
- How does the query generalise if the heatmap gains a third axis, say day-of-week?The same inclusion-exclusion, one dimension up: the answer is an alternating sum over the 2^d corners of the query box, so three dimensions needs eight terms with signs set by how many coordinates come from the low end. Query time stays constant for fixed d but the constant doubles per dimension, and the table's memory multiplies by each axis's length — which is what actually rules this out well before the arithmetic does.
- The heatmap is mostly zeros. Is the table still worth building?Often not. The table is dense: it costs memory proportional to the whole grid no matter how sparse the data, and every entry is a cumulative total needing a wider accumulator than a cell. With few queries, iterating the non-zero entries and aggregating directly is cheaper in both time and space. The table earns its keep when queries are numerous, the grid is genuinely dense, or block sizes are large relative to the grid.
Two overlapping stains on a tablecloth. Measure each and add them up and you have counted the overlap twice; to get the true covered area you subtract the overlap once.
saying these in an interview costs you the question
- Subtracts both strips and stops, double-removing the corner
- Adds the corner term instead of subtracting during the build
- Says the query cost grows with the block's area
- Claims edge-anchored tests are enough to validate the formula
- Thinks the table is cheap on memory when the grid is sparse