Range Sum Query 2D

The same trick that answers range sums on a list answers rectangle sums on a grid. The idea carries over directly; what changes is the bookkeeping. A rectangle has four corners, so a query touches four stored values, and getting one sign wrong gives an answer that is off by a whole strip of the grid.

Grid problems like this appear in image processing (the "summed-area table" behind fast blur filters), in game maps, and in interview questions that count or maximise sums over sub-rectangles. Learn the formula by drawing it once; after that it is mechanical.

The problem

You are given a grid of integers that never changes. Build an object that answers many questions of the form "what is the total of the rectangle whose top-left cell is (r1, c1) and bottom-right cell is (r2, c2), both corners included?"

grid = [[3, 0, 1, 4],        [5, 6, 3, 2],        [1, 2, 0, 1]]

• Query (1, 1, 2, 2) → 11: the cells 6, 3, 2, 0.
• Query (0, 2, 1, 3) → 10: the cells 1, 4, 3, 2.
• Query (2, 0, 2, 0) → 1: a single cell.

Constraints: 1 ≤ rows, cols ≤ 500, values between −10⁵ and 10⁵, up to 10⁵ queries, and every query has r1 ≤ r2 and c1 ≤ c2 inside the grid.

Clarifying questions

• Are both corners included? Yes.
• Can the grid change? No. (If it can, see the follow-ups.)
• Negative values? Yes; nothing in the method depends on sign.
• Is the grid ever empty? Assume at least one cell, but make the constructor safe anyway.

Approach 1: the simple way

Add up every cell in the rectangle.

1class NumMatrixBrute:2    """Adds up every cell of the rectangle on each query."""34    def __init__(self, grid: list[list[int]]) -> None:5        self.grid = grid67    def sum_region(self, r1: int, c1: int, r2: int, c2: int) -> int:8        """Sum of the rectangle with corners (r1, c1) and (r2, c2), inclusive."""9        total = 010        for r in range(r1, r2 + 1):11            for c in range(c1, c2 + 1):12                total += self.grid[r][c]13        return total

Each query costs O(rows × cols) in the worst case. On a 500 × 500 grid that is 250,000 cells per query, and 10⁵ queries make 2.5 × 10¹⁰ additions. Far too slow.

Approach 2: one prefix array per row

Apply the 1D pattern to each row. A rectangle is a stack of row segments, and each segment is one subtraction.

1class NumMatrixRows:2    """One prefix array per row: O(rows) per query."""34    def __init__(self, grid: list[list[int]]) -> None:5        self.rows = []6        for row in grid:7            prefix = [0] * (len(row) + 1)8            for c, value in enumerate(row):9                prefix[c + 1] = prefix[c] + value10            self.rows.append(prefix)1112    def sum_region(self, r1: int, c1: int, r2: int, c2: int) -> int:13        """Sum of the rectangle with corners (r1, c1) and (r2, c2), inclusive."""14        return sum(self.rows[r][c2 + 1] - self.rows[r][c1] for r in range(r1, r2 + 1))

For query (1, 1, 2, 2): row 1's prefix is [0, 5, 11, 14, 16], giving 14 − 5 = 9; row 2's is [0, 1, 3, 3, 4], giving 3 − 1 = 2. Total 11.

Each query is now O(rows): 500 × 10⁵ = 5 × 10⁷ subtractions. Much better, and a fine thing to say out loud as a stepping stone. But it still grows with the grid's height, and the next step removes that.

The key insight

Store, for every cell, the sum of the rectangle from the top-left corner (0, 0) to that cell. Call it P, and pad it with an extra zero row and zero column, exactly like the leading zero in 1D: P[r][c] is the sum of the rectangle covering rows 0..r − 1 and columns 0..c − 1.

Query. The rectangle you want is the big rectangle up to (r2, c2), minus the strip above it, minus the strip to its left. But those two strips overlap in the top-left block, which was subtracted twice, so add it back once:

sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]      (big)           (strip above)  (strip left)  (corner, added back)

Build. The same picture in reverse. The rectangle up to cell (r, c) is the cell itself, plus the rectangle above it, plus the rectangle to its left — and those two share the top-left block, which was counted twice, so subtract it once:

P[r+1][c+1] = grid[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]

This is inclusion–exclusion: add the pieces, then correct for the overlap. Draw the four rectangles on paper once and both formulas follow.

Approach 3: 2D prefix sums

1class NumMatrix:2    """2D prefix sums: O(1) per rectangle query."""34    def __init__(self, grid: list[list[int]]) -> None:5        rows, cols = len(grid), len(grid[0]) if grid else 06        # P[r][c] = sum of the rectangle from (0, 0) to (r - 1, c - 1)7        self.P = [[0] * (cols + 1) for _ in range(rows + 1)]8        for r in range(rows):9            for c in range(cols):10                self.P[r + 1][c + 1] = (grid[r][c] + self.P[r][c + 1]11                                        + self.P[r + 1][c] - self.P[r][c])1213    def sum_region(self, r1: int, c1: int, r2: int, c2: int) -> int:14        """Sum of the rectangle with corners (r1, c1) and (r2, c2), inclusive."""15        P = self.P16        return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]

[[0] * (cols + 1) for _ in range(rows + 1)] builds independent rows. Writing [[0] * (cols + 1)] * (rows + 1) would make every row the same list, and every write would appear in all of them.

Dry run: the table

The finished P for our grid (row 0 and column 0 are the padding):

Three of the build steps, in full:

P[3][4] = 28 is the sum of the whole grid, a quick check: 8 + 16 + 4 = 28.

Dry run: the queries

All three match the cells added by hand.

Complexity. Building is O(rows × cols) time — four lookups per cell. Each query is O(1). Space is O((rows + 1) × (cols + 1)). For 500 × 500 and 10⁵ queries, that is about 250,000 build steps plus 10⁵ queries.

Edge cases

• Rectangles touching row 0 or column 0. The padding makes P[0][...] and P[...][0] zero, so the formula needs no branches — see the second query above.
• A single cell. (r, c, r, c) must return grid[r][c]. Use it as your self-test, just like (i, i) in 1D.
• The whole grid. (0, 0, rows − 1, cols − 1) returns P[rows][cols].
• One row or one column. The 2D code reduces to the 1D formula automatically.
• An empty grid. cols is guarded, so the constructor builds a 1 × 1 table of zeros and does not crash.

Saying it in the interview

Follow-ups

• "The grid gets point updates." Use a 2D Fenwick tree: O(log rows × log cols) per update and per query.
• "Count sub-rectangles whose sum equals a target." Fix a pair of rows (O(rows²) pairs), collapse the columns between them into a 1D array of column sums, then run Subarray Sum Equals K on it. Total O(rows² × cols).
• "Largest sum of any sub-rectangle." Same row-pair collapse, then Kadane's algorithm on the 1D array: O(rows² × cols).