A grid query may ask for the sum of a rectangular region, while a batch of updates may add a value to every cell of many rectangles. Visiting every covered cell separately can repeat work. Prefix sums compress the repeated work of queries; a difference grid compresses the repeated work of updates.
Both methods use four signed corners, but their stored meanings differ. A prefix entry is already a sum over a region. A difference entry is an instruction whose effect appears only after accumulation. We will derive the signs and indices for each, rather than treating one remembered formula as sufficient for both tasks.
Use boundaries to define grid rectangles
Definition 1.4.1
(Half-open rectangles and a padded prefix table)
Let be an integer grid with positive height and width . A query uses boundaries satisfying and . Its cells have row indices and column indices .
Define a prefix table of size by
Row zero and column zero are all zero. A boundary equal to or is valid in this table, even though it is not a cell index of . A rectangle with zero height or zero width is empty and has sum zero.
The order of arguments is top, left, bottom, right. With half-open boundaries, rectangle height is and width is , including at the outer grid edges. Negative cell values are permitted; the construction does not require prefix values to be increasing.
Build one prefix entry by inclusion-exclusion
The cell at row , column extends the above and left prefix regions. Their overlap was included twice, so
Proposition 1.4.2
(The prefix recurrence)
For and , the padded table satisfies , and row zero and column zero are zero.
Proof
(Inclusion-exclusion on the enlarged prefix)
The prefix above the new cell covers rows before through column . The prefix to its left covers columns before through row . Their common region is exactly , so subtracting it leaves their union counted once. Adding completes the desired prefix.
In row-major construction, both earlier-row prefixes and the current row's earlier-column prefix have already been computed. Starting from the zero boundaries, induction therefore proves every entry's stated sum meaning. This is a coefficient-counting argument and remains valid for negative values. ∎
Recover an arbitrary rectangle from four prefixes
The answer is
The first term includes the target but also the area above and to the left. The next two remove those areas. Their common upper-left region has now been removed twice, so the last term restores it once. A cell in the target has net coefficient one; every other cell has coefficient zero.
If or , the terms cancel in pairs automatically. No special sentinel cell of the original grid is read. The padded table stores sums for those boundary positions, which is why a query ending exactly at the grid's height or width is valid.
Theorem 1.4.3
(The four-corner rectangle sum)
For and , the sum of over , equals .
Proof
(Each cell has coefficient one or zero)
In the cell appears with coefficient . In the four-corner combination its coefficient is therefore
Because , the first factor is one exactly when and zero otherwise; because , the second factor is one exactly when . So the target cells have coefficient one and every other cell has coefficient zero. When or a factor vanishes identically, which gives the empty sum. ∎
Worked example 1.4.4
(A signed grid and its complete prefix table)
Use
The prefix table is:
| Row boundary a | P[a][0] | P[a][1] | P[a][2] | P[a][3] | P[a][4] |
|---|---|---|---|---|---|
Query includes the last two rows and columns 1,2,3. Its sum is . Directly, the two row contributions are and . The whole-grid sum is .
Worked example 1.4.5
(Edge strips and an empty rectangle)
Use the signed grid and its prefix table above. The whole grid gives , since the zero row and column vanish. The last column gives , which is read directly. The empty rectangle has , so its value is , with no cell read and no special case.
Common mistake
(Treating the bottom and right boundaries as inclusive)
The boundaries are half-open. To sum rows and and columns of the signed grid, the call must be . Passing the last included indices selects only row and columns : , which is , not .
Counterexample mode
The four-corner idea is not a formula for prefix minima
Consider one-row grids and . Their nonempty origin-anchored prefix minima are both zero at every column, yet the last-cell query has minimum five in one and nine in the other.
Thus prefix-minimum data does not even contain enough information to answer that query. Subtraction of additive prefix sums works because contributions can cancel; replacing sums by minima does not preserve that argument. A suitable range-minimum structure has a different invariant.
Reverse the viewpoint for offline rectangle additions
Suppose an update adds integer to every cell in rectangle . Use a zero difference grid of size and write four instructions:
These are corner markers, not the final cell increments. After all updates, accumulate the difference grid in both dimensions. The increment at cell is the sum of over .
Theorem 1.4.6
(Four corner markers add a rectangle)
Let be a zero grid of size , and for each update with , apply the four marker changes above. Then for every cell of , the sum of over , equals the sum of over exactly those updates whose rectangle contains .
Proof
(Corner impulses and a product of step functions)
One corner instruction contributes to a cell precisely when that corner is at or above and at or left of the cell. Let be one when condition is true and zero otherwise. The four contributions of one update total
The first factor is one exactly in the selected row interval; the second is one exactly in the column interval. Their product is one exactly inside the rectangle. Elsewhere it is zero. Negative additions work by the same algebra, and an empty rectangle makes one factor identically zero.
Additions from several updates superpose, so accumulating their combined markers gives the sum of all requested increments. Bottom/right markers at boundaries are stored safely but do not add to any interior cell beyond those boundaries. ∎
Proof X-ray
What the marker proof depends on
The non-obvious move is to factor the two-dimensional indicator into a row factor times a column factor, each a difference of two step functions. That turns the four signs into products: a marker at a "start" row and a "start" column is , a start with an end is , and an end with an end is again. Nothing in the algebra depends on the cells themselves, so overlaps, negative and repeated updates all follow from superposition.
The hypotheses and are what make each factor an indicator. If , the row factor equals on rows , so the "rectangle" would subtract on those rows. The padded row and column exist only so that end markers at the grid edge have somewhere to go. No cell of reads them, because every cell of has and .
Worked example 1.4.7
(Overlapping positive and negative additions)
On a zero grid of height three and width four, apply updates (0,1,2,4,+3) and (1,2,3,4,-2). Their recovered increment grid is
The first rectangle has six cells and adds 18 in total. The second has four cells and adds , so the final total increment is ten, also by rows. In their overlap, each cell receives .
The function below returns this increment grid. To update an existing nonzero grid, add the increments to its original cells. The original grid is not an input to the corner-marker constructor.
Worked example 1.4.8
(An update ending at the bottom-right corner)
On the same grid, add to the single cell , that is, to the rectangle . The markers are , , and . The last three lie in the padded row and column . The cell accumulates only among nonzero entries with , , so it receives . The cell has no nonzero marker in its range, and neither does any other cell, so every other increment is zero. The original value , which the four-corner query evaluates as , becomes .
Reuse the prefix recurrence without confusing its indices
A two-dimensional inclusive accumulation of can use the same padded prefix function. If integrated = prefix_sums(D), the increment at original cell (i,j) is integrated[i+1][j+1], because that entry includes difference indices at most .
Reading integrated[i][j] would omit markers on row or column , shifting the result. The intermediate difference grid has an extra boundary row/column, so its prefix has another padding row/column. This changes only constant factors in storage, not the meaning of the original grid's dimensions.
Concept lensAlgebraic
Markers are the mixed difference of the increments
Let be the increment grid, extended by zeros to and read as zero at negative indices. The markers satisfy , a discrete mixed second difference, and the double accumulation recovers from . The four-corner query is the reverse: a rectangle sum is the mixed difference of the prefix table over the rectangle's corners.
def prefix_sums(grid):
if not grid or not grid[0]:
raise ValueError("a nonempty rectangular grid is required")
height, width = len(grid), len(grid[0])
if any(len(row) != width for row in grid):
raise ValueError("grid rows must have equal length")
prefix = [[0] * (width + 1) for _ in range(height + 1)]
for row in range(height):
for column in range(width):
prefix[row + 1][column + 1] = (
grid[row][column] + prefix[row][column + 1]
+ prefix[row + 1][column] - prefix[row][column]
)
return prefix
def rectangle_sum(prefix, top, left, bottom, right):
height, width = len(prefix) - 1, len(prefix[0]) - 1
if not (0 <= top <= bottom <= height and 0 <= left <= right <= width):
raise ValueError("rectangle boundaries must lie in the grid")
return (prefix[bottom][right] - prefix[top][right]
- prefix[bottom][left] + prefix[top][left])
def rectangle_additions(height, width, updates):
if height < 1 or width < 1:
raise ValueError("grid dimensions must be positive")
difference = [[0] * (width + 1) for _ in range(height + 1)]
for top, left, bottom, right, delta in updates:
if not (0 <= top <= bottom <= height and 0 <= left <= right <= width):
raise ValueError("rectangle boundaries must lie in the grid")
difference[top][left] += delta
difference[bottom][left] -= delta
difference[top][right] -= delta
difference[bottom][right] += delta
integrated = prefix_sums(difference)
return [[integrated[row + 1][column + 1] for column in range(width)]
for row in range(height)]
The grids are finite row sequences with integer cells; dimensions, boundaries and additions are integers as type preconditions. The code checks positive/nonempty shape and rectangle bounds, not integer types. rectangle_sum assumes an unchanged correct prefix table, rather than validating arbitrary tables on each constant-time call. None of the functions modifies the original grid.
For the signed example, rectangle_sum(prefix_sums(grid), 1, 1, 3, 4) returns 9. rectangle_additions(3, 4, [(0,1,2,4,3),(1,2,3,4,-2)]) returns the displayed increments. Empty rectangles are legal; whole grids with zero height or zero width are outside this implementation's contract.
Common mistake
(Reading the integrated table one cell too early)
Let integrated = prefix_sums(D). After the single update on a grid, cell should increase by . The value is integrated[1][1], which is . Reading integrated[0][0] returns the padding zero and loses the update.
Keep static queries and batched updates separate
Counterexample mode
An old prefix table does not observe a later update
Build a prefix table for a zero two-by-two grid, then add one to its whole grid. The old prefix still answers zero for the whole-grid sum, while the changed grid's sum is four.
Four constant-time marker writes describe an update; they do not immediately refresh every queryable prefix. The batch method accumulates markers after the updates. It is not a constant-time solution to arbitrarily interleaved updates and queries. Such a workload requires rebuilding or an appropriate dynamic structure with its own cost bound.
Building a static prefix table costs time and stored cells. Each rectangle query takes accesses and arithmetic operations, so queries cost including preprocessing.
For offline additions, the marker writes cost and recovery costs , giving time and stored cells. Padding by constant numbers of rows and columns preserves this bound because . Writing the full recovered grid itself requires outputs. If all additions precede all queries, recover the grid, combine it with original values, then build a new prefix table for the query phase.
These are arithmetic/cell counts. Prefix values and accumulated markers can be much larger in magnitude than one input cell, and large integers carry bit costs. Python integers keep the sums exact; a fixed-width implementation must preserve intermediate additions and subtractions as well as final answers. The formulas depend on additive cancellation, not nonnegativity or a monotone table.
Exercises and worked solutions
Quick check
(1. Evaluate a rectangle with negative cells)
For the displayed signed grid, evaluate (1,1,3,4) using four prefix entries and by summing the six cells. Which entry gives the whole-grid sum?
Solution · Solution 1
The four terms give . The selected row sums are four and five, also totaling nine. The whole-grid sum is . Negative entries do not invalidate the cancellation proof.
Quick check
(2. Distinguish an empty rectangle from an invalid boundary)
Why is a query with top equal to bottom zero, and why may bottom equal H? Why does this not permit reading the original grid at row H?
Solution · Solution 2
Equal row boundaries make the four terms cancel, and there are no selected rows. A bottom boundary of is represented by the padded prefix table and includes original rows with indices less than it, through . Original cell indices still stop at ; a prefix boundary is not an original cell.
Quick check
(3. Place the four update markers with their signs)
Give the marker changes for adding three to (0,1,2,4). Why must the difference grid support column boundary four, and which integrated entry recovers original cell (0,1)?
Solution · Solution 3
Add three at and , subtract three at and . The right boundary is four even though original columns end at three, so the difference grid includes that boundary column. Original cell (0,1) is recovered from integrated[1][2], including the marker at .
Quick check
(4. Check overlapping increments by area and by cells)
For the two worked updates, give the increment in an overlap cell and the total increment over the grid. Does the returned array already include any original nonzero cells?
Solution · Solution 4
An overlap cell receives . The total is , agreeing with recovered row sums . The returned array contains increments only; add it cellwise to an original grid when needed.
Quick check
(5. State the workload before claiming constant-time operations)
Why do four marker writes not make a later rectangle-sum query correct against an old prefix table? What can be done if all updates finish before all queries begin?
Solution · Solution 5
The old prefix stores sums of old values; markers have not been integrated into its entries. For a batch-first workload, recover all increments, add original values, and build a fresh prefix table before answering queries. Arbitrary interleaving needs further maintenance and cannot inherit constant-time query/update claims from these separate phases.
Quick check
(6. Separate algebra, stored cells and output costs)
Why can sums use four-corner subtraction but minima cannot be substituted into the same proof? Why do cells and constant arithmetic per query not automatically mean the same bounds in bits?
Solution · Solution 6
Additive contributions have inverses and cancel; minima do not retain removed-region information, as [0,5] and [0,9] demonstrate. Stored sums may need more bits than individual cells, and arithmetic on large integers has its own cost. Recovering an entire grid also requires writing outputs, even though each marker update used four writes.