Skip to main content

304 - Range Sum Query 2D - Immutable

Difficulty: Medium | Pattern: 2D Prefix Sum | Company tags: Amazon, Google, Microsoft

Problem Statement​

Given a 2D matrix matrix, handle multiple queries of the following type:

  • sumRegion(row1, col1, row2, col2) — return the sum of elements in the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class with __init__ and sumRegion.

Example:

Input: ["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
       [[matrix], [2,1,4,3], [1,1,2,2], [1,2,2,4]]
Output: [null, 8, 11, 12]

Approach: 2D Prefix Sum — O(mn) build, O(1) query​

Key insight: Build a prefix sum table where prefix[i][j] = sum of all elements in the rectangle from (0,0) to (i-1, j-1). Then use inclusion-exclusion to answer any rectangular query in O(1).

Algorithm Flow​

class NumMatrix:
    def __init__(self, matrix: list[list[int]]):
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.prefix[i][j] = (matrix[i-1][j-1]
                    + self.prefix[i-1][j]
                    + self.prefix[i][j-1]
                    - self.prefix[i-1][j-1])
    
    def sumRegion(self, row1, col1, row2, col2) -> int:
        r1, c1, r2, c2 = row1+1, col1+1, row2+1, col2+1
        return (self.prefix[r2][c2]
                - self.prefix[r1-1][c2]
                - self.prefix[r2][c1-1]
                + self.prefix[r1-1][c1-1])

Inclusion-Exclusion Formula​

sumRegion(r1,c1,r2,c2) = prefix[r2][c2]
                        - prefix[r1-1][c2]   (remove rows above)
                        - prefix[r2][c1-1]   (remove cols to left)
                        + prefix[r1-1][c1-1] (add back double-subtracted corner)

Dry Run​

matrix = [[3,0,1,4,2],
          [5,6,3,2,1],
          [1,2,0,1,5],
          [4,1,0,1,7],
          [1,0,3,0,5]]

sumRegion(2,1,4,3): r1=3,c1=2,r2=5,c3=4 (1-indexed) = prefix[5][4] - prefix[2][4] - prefix[5][1] + prefix[2][1] = 8

Complexity​

  • Build: O(m×n)
  • Query: O(1)
  • Space: O(m×n)

Key Terms​

TermDefinition
2D Prefix SumA table where prefix[i][j] holds the sum of all elements in the rectangle from (0,0) to (i-1,j-1).
Inclusion-ExclusionTechnique to compute a sub-rectangle's sum by combining and canceling overlapping prefix sums.
Immutable inputMatrix values never change after construction, so precomputing prefix sums once is safe and optimal.
Amortized query costCost is paid once at build time so each sumRegion call afterward is O(1).

FAQ​

  1. Why pad the prefix array with an extra row and column? It avoids special-casing row1 == 0 or col1 == 0 — prefix[0][*] and prefix[*][0] are always 0, so the same formula works for edge rectangles.
  2. Can this be solved without extra space? Not while keeping O(1) queries; you could compute row-wise prefix sums in-place and still need O(m×n) work per query, defeating the purpose. The prefix table trade-off is intentional.
  3. What if the matrix is empty or has zero rows/columns? __init__ should guard against len(matrix) == 0 before indexing matrix[0], returning an empty prefix table.
  4. How would this change if the matrix were mutable (values can be updated)? You'd need LC 308's 2D BIT (Binary Indexed Tree) or block decomposition to support O(log m · log n) updates instead of only O(1) queries.
  5. What's the follow-up interviewers usually ask? "What if there are many more updates than queries?" — this pushes toward a 2D Fenwick Tree, trading O(1) query for O(log m · log n) update and query.

Quick Revision​

  • Pattern: 2D prefix sum with inclusion-exclusion.
  • Build a (m+1) x (n+1) prefix table so boundary rows/cols are 0 by default.
  • prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1].
  • Query: sumRegion = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1].
  • Convert 0-indexed query coordinates to 1-indexed before looking up the prefix table.
  • Build cost O(m×n), query cost O(1) — ideal when queries vastly outnumber updates.
  • If updates were required, switch to a 2D BIT or segment tree (see LC 308).
  • Always verify with a small hand-traced matrix before trusting the formula.
  • 307-RangeSumQuery-Mutable — 1D analogue that supports updates via BIT.
  • LC 308 - Range Sum Query 2D - Mutable (2D BIT extension of this problem; not in this directory).
  • 1D prefix sum problems (e.g. subarray sum equals K) share the same inclusion-exclusion idea in one dimension.