Range Sum Query 2D - Immutable

Range Sum Query 2D - Immutable asks you to sum any rectangular block of a fixed matrix — over and over. The trick is to pay an upfront cost once so each query becomes four lookups. This is the 2-D prefix sum, and the move that makes it work is inclusion-exclusion.

3 0 1
5 6 3
1 2 0

The slow way first

The obvious idea: for each query, loop over every cell inside the rectangle and add it up. One query is O(R x C) in the worst case (the whole matrix). With q queries that is O(q x R x C) — fine for one lookup, far too slow when queries pour in.

The question to ask: the matrix never changes, so what can I precompute once and reuse forever? If I knew, for every position, the sum of the rectangle from the top-left corner down to it, then any block could be assembled from a few of those totals.

The idea: a prefix table plus inclusion-exclusion

Build a table pre where pre[i+1][j+1] is the sum of every matrix cell in rows 0..i and columns 0..j — the whole top-left rectangle ending at (i, j). We give pre one extra row and one extra column of zeros (the border) so the recurrence below never reads off the edge.

Each table cell is built from three already-computed neighbors:

pre[i+1][j+1] = matrix[i][j] + pre[i][j+1] + pre[i+1][j] - pre[i][j]

We add the cell above and the cell to the left, then subtract the top-left overlap that both of those rectangles counted — that subtraction is inclusion-exclusion in miniature.

To answer a query, take the big rectangle that ends at the block, then peel off the band above and the band to the left, and finally add back the top-left corner that got removed twice:

sumRegion = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]

Walk through it

Step through the animation. First we fill the prefix table left to right, top to bottom — watch pre[2][2] = 6 + 3 + 8 - 3 = 14 show the recurrence with all four neighbors in play. Then we pose sumRegion(1, 1, 2, 2) and light up the four corners: start with pre[3][3] = 21, subtract the band above (pre[1][3] = 4) and the band to the left (pre[3][1] = 9), then add the corner back (pre[1][1] = 3). The result is 21 - 4 - 9 + 3 = 11.

Pseudocode

build (once):
  make pre with one extra row and column of zeros
  for each matrix cell (i, j):
    pre[i+1][j+1] = matrix[i][j]
                  + pre[i][j+1]        # rectangle directly above
                  + pre[i+1][j]        # rectangle directly to the left
                  - pre[i][j]          # overlap, counted twice -> remove once
 
query sumRegion(r1, c1, r2, c2):
  return pre[r2+1][c2+1]               # big rectangle ending at the block
       - pre[r1][c2+1]                 # remove the band above
       - pre[r2+1][c1]                 # remove the band to the left
       + pre[r1][c1]                   # add the corner back (removed twice)

The Python solution

class NumMatrix:
    def __init__(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        self.pre = [[0] * (cols + 1) for _ in range(rows + 1)]
        for i in range(rows):
            for j in range(cols):
                self.pre[i + 1][j + 1] = (matrix[i][j]
                    + self.pre[i][j + 1]
                    + self.pre[i + 1][j]
                    - self.pre[i][j])
 
    def sumRegion(self, r1, c1, r2, c2):
        p = self.pre
        return (p[r2 + 1][c2 + 1]
                - p[r1][c2 + 1]
                - p[r2 + 1][c1]
                + p[r1][c1])

• The table pre is (rows + 1) x (cols + 1); its first row and first column stay 0 and act as the border, so the recurrence has no edge cases.
• pre[i+1][j+1] is the sum of the whole top-left rectangle ending at matrix[i][j].
• The build recurrence adds the rectangle above and the rectangle to the left, then subtracts pre[i][j] because that smaller top-left rectangle was included by both of them.
• sumRegion is the same idea in reverse: one big rectangle, minus two over-counted bands, plus the corner that the two subtractions removed twice.
• Every query is exactly four array reads — O(1) — no matter how large the block is.

Complexity

We trade O(R x C) extra space for the table, and in return every one of possibly millions of queries collapses from a full scan to four reads. The upfront build pays for itself the moment a second query arrives.

When this pattern shows up

Practice