Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Two-dimensional prefixes: constant-time static rectangle sums

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A two-dimensional prefix grid stores the total above and left of every boundary in an extra top row and left column. Each cell combines its source value with the prefix above and the prefix to its left, then removes their shared top-left overlap. A rectangle query applies the same inclusion and exclusion to four prefix corners. This implementation accepts half-open row and column bounds: [top, bottom) by [left, right). Empty rectangles return zero. It rejects ragged input rows because a rectangle needs one consistent column count. The grid is a frozen snapshot; the program does not expose a point update method or silently repair stale prefixes after source changes.

Operational case

The capacity grid has rows 23, 47, 19, 61; 38, 52, 29, 74; and 13, 41, 67, 31. The rectangle spanning rows [0, 2) and columns [1, 3) totals 147. The whole grid totals 495. A zero-height rectangle over rows [1, 1) totals zero even when its column span is nonempty. The padded border removes separate code paths for a query touching row zero or column zero. A rectangle whose bottom or right bound exceeds the grid shape is rejected before any arithmetic, which keeps inclusive and exclusive coordinates from drifting between callers.

Working Python program

python
class CapacityGridPrefix:
    def __init__(self, capacity_rows):
        self.rows = len(capacity_rows)
        self.columns = len(capacity_rows[0]) if self.rows else 0
        if any(len(row) != self.columns for row in capacity_rows):
            raise ValueError("capacity grid must be rectangular")
        self.prefix = [[0] * (self.columns + 1) for _ in range(self.rows + 1)]
        for row in range(self.rows):
            for column in range(self.columns):
                self.prefix[row + 1][column + 1] = (
                    capacity_rows[row][column]
                    + self.prefix[row][column + 1]
                    + self.prefix[row + 1][column]
                    - self.prefix[row][column]
                )

    def rectangle_sum(self, top, left, bottom, right):
        if not 0 <= top <= bottom <= self.rows or not 0 <= left <= right <= self.columns:
            raise IndexError("invalid half-open rectangle")
        return (
            self.prefix[bottom][right]
            - self.prefix[top][right]
            - self.prefix[bottom][left]
            + self.prefix[top][left]
        )


if __name__ == "__main__":
    grid = CapacityGridPrefix([[23, 47, 19, 61], [38, 52, 29, 74], [13, 41, 67, 31]])
    print("center=", grid.rectangle_sum(0, 1, 2, 3), sep="")
    print("full=", grid.rectangle_sum(0, 0, 3, 4), sep="")
    print("empty=", grid.rectangle_sum(1, 2, 1, 4), sep="")

Output

Output
center=147
full=495
empty=0

Time, space, and tradeoff

For R rows and C columns, construction reads every cell once, taking O(RC) time and O((R + 1)(C + 1)) space. Each rectangle query uses four stored prefix values and constant arithmetic, so O(1) time under a fixed-width arithmetic model. Integer size still matters for very large totals. Recomputing a source cell would affect many prefixes and can take O(RC) in this simple snapshot; a two-dimensional Fenwick tree offers logarithmic updates and rectangle sums with a different memory and implementation cost. If only a few small rectangles are requested, a direct nested scan may be cheaper than building the full table.

Common Mistakes

  • Do not omit the shared top-left term after subtracting top and left strips.
  • Do not mix inclusive bottom-right coordinates with the half-open API.
  • Do not accept ragged rows as one rectangular grid.
  • Do not claim that this static prefix table supports cheap point updates.

Connected lessons

Compare with Coordinate compression: preserve order with dense integer ranks, Fenwick frequency index: select the kth stored key, Mo ordering: count distinct scan codes across an offline query batch, then run the query workload audit and contract quiz.

Two-dimensional range trees: count a static rectangle adds a distinct structure contract to compare.

Two-dimensional segment trees: correct sensors and sum rectangles adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details