Range Sum Query 2D Immutable: 2D Prefix Sums and the Fenwick Tree Upgrade Path

Problem Statement#

Given a 2D matrix, design a data structure that supports many calls to sumRegion(r1, c1, r2, c2), returning the sum of all elements inside the rectangle whose top-left corner is (r1, c1) and bottom-right corner is (r2, c2). The matrix never changes after construction. Constraints typically allow up to 200 by 200 cells with up to 10,000 queries, so an O(area) per query brute force is far too slow.

Why This Problem Matters#

This is the canonical warm-up before any 2D segment tree, 2D Fenwick tree (BIT), or 2D sparse table conversation in an interview. Companies like Google, Amazon, Microsoft, and Bloomberg use it to confirm three things at once: you can reason about inclusion-exclusion, you can pick the right preprocessing trade-off (build cost versus query cost), and you understand how the structure naturally extends when updates are introduced. Range query problems are a foundational pattern, and being fluent in 2D prefix sums means you can recognise and solve a long tail of follow-ups (Maximal Square, Max Sum Submatrix, count submatrices that sum to target, image processing kernels) without panicking.

The immutable variant is solved by 2D prefix sums in O(1) per query. The mutable variant is solved by a 2D Fenwick tree or a 2D segment tree with lazy propagation if range updates are required. Knowing both ends of this spectrum is what separates a junior answer from a senior one.

The Core Insight#

A 1D prefix sum lets you answer sum(l, r) in O(1) using prefix[r+1] - prefix[l]. The 2D analogue is the principle of inclusion-exclusion. Define pre[i][j] as the sum of all cells inside the rectangle from (0, 0) to (i-1, j-1). Then any rectangle sum becomes:

sum(r1, c1, r2, c2) = pre[r2+1][c2+1]
                    - pre[r1][c2+1]
                    - pre[r2+1][c1]
                    + pre[r1][c1]

You subtract the strip above and the strip to the left, but those two strips both contain the upper-left rectangle, so you must add it back once. That add-back is the inclusion-exclusion correction.

Building pre is itself a small DP: pre[i][j] = matrix[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]. Same correction, applied incrementally.

If the matrix were mutable (LeetCode 308 Range Sum Query 2D Mutable), prefix sums fall apart because every update would force an O(m * n) rebuild. That is where a 2D Fenwick tree (BIT) shines: O(log m * log n) per update and per query, with the same inclusion-exclusion idea applied on top of two prefixSum calls.

Visual Dry Run#

Take a 4x5 matrix and look at the prefix table that gets built. Imagine the rectangle query sumRegion(2, 1, 4, 3).

matrix:                   pre (1-indexed, padded with row/col of zeros):
3 0 1 4 2                 0  0  0  0  0  0
5 6 3 2 1                 0  3  3  4  8 10
1 2 0 1 5                 0  8  9 13 19 22
4 1 0 1 7                 0  9 12 16 23 31
                          0 13 17 21 29 44
 
Query rectangle (r1=2,c1=1,r2=4,c2=3):
Big rectangle area  = pre[5][4] = 29
Strip above (rows  0..1, cols 1..3) = pre[2][4] = 8
Strip left  (rows 2..4, cols 0..0)  = pre[5][1] = 13
Double subtracted  = pre[2][1] = 3
Answer = 29 - 8 - 13 + 3 = 11

The four lookups are constant-time, regardless of how big the rectangle is. That is the entire trick.

Solution (Optimal)#

class NumMatrix:
    def __init__(self, matrix):
        if not matrix or not matrix[0]:
            self.pre = [[0]]
            return
        m, n = len(matrix), len(matrix[0])
        # pre[i][j] = sum of cells in rectangle (0,0) to (i-1, j-1)
        self.pre = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.pre[i][j] = (
                    matrix[i - 1][j - 1]
                    + self.pre[i - 1][j]
                    + self.pre[i][j - 1]
                    - self.pre[i - 1][j - 1]
                )
 
    def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
        return (
            self.pre[r2 + 1][c2 + 1]
            - self.pre[r1][c2 + 1]
            - self.pre[r2 + 1][c1]
            + self.pre[r1][c1]
        )

class NumMatrix {
  constructor(matrix) {
    const m = matrix.length;
    const n = m ? matrix[0].length : 0;
    this.pre = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        this.pre[i][j] =
          matrix[i - 1][j - 1] +
          this.pre[i - 1][j] +
          this.pre[i][j - 1] -
          this.pre[i - 1][j - 1];
      }
    }
  }
  sumRegion(r1, c1, r2, c2) {
    return (
      this.pre[r2 + 1][c2 + 1] -
      this.pre[r1][c2 + 1] -
      this.pre[r2 + 1][c1] +
      this.pre[r1][c1]
    );
  }
}

Complexity. Build is O(m * n) time and O(m * n) extra space. Each query is O(1) time and O(1) extra space. For the mutable follow-up with point updates, switch to a 2D Fenwick tree for O(log m * log n) per update and per query, which is the standard interview-grade upgrade path.

Common Mistakes#

• Forgetting the + pre[r1][c1] correction. Without it the upper-left rectangle is subtracted twice and the answer is wrong by exactly that overlap.
• Using a non-padded prefix table. Special-casing r1 == 0 or c1 == 0 leads to off-by-one bugs. Always pad with a leading row and column of zeros.
• Mixing 0-indexed and 1-indexed coordinates inside the same expression. Pick one convention (input is 0-indexed, prefix is 1-indexed) and translate at the boundaries only.
• Rebuilding pre on every query because the matrix "might" change. If updates are not in the API contract, do not pay for them.
• Reaching for a segment tree or Fenwick tree when prefix sums already give you O(1) per query. Use the simpler structure when the problem is immutable.

Interview Tips#

• State the trade-off out loud: "Build is O(m * n), query is O(1). If updates appear, I would switch to a 2D Fenwick tree." Interviewers love seeing you anticipate the next question.
• Draw a 3x3 example and physically point at the four corners of the prefix table you are reading. This convinces both you and the interviewer that the inclusion-exclusion signs are right.
• Be explicit that pre is 1-indexed and the input is 0-indexed; write the translation pre[i][j] gets matrix[i-1][j-1] on the board before coding.
• If the interviewer adds "what about k queries on the same row range," mention that you can collapse to a 1D prefix sum on pre[r2+1] - pre[r1] for blazing speed.
• For the mutable follow-up, sketch the 2D Fenwick tree update and query in pseudocode. Mention that lazy propagation on a 2D segment tree is needed only if range updates are required, otherwise a BIT is simpler and faster in practice.

Follow-up Questions#

• LeetCode 308 Range Sum Query 2D Mutable. Replace the prefix table with a 2D Fenwick tree (BIT). Update and query both become O(log m * log n).
• LeetCode 363 Max Sum of Rectangle No Larger Than K. Fix two row boundaries, compress to a 1D problem, and use prefix sums plus a sorted set.
• Count submatrices that sum to a target. Same row-pair compression plus a hashmap of running 1D prefix sums.
• Maximal square or maximal rectangle of ones. Different DP, but the prefix-sum mindset (precompute once, answer queries cheaply) is the same family.
• 2D range update plus 2D range query. Requires a 2D BIT with four parallel trees, or a 2D segment tree with lazy propagation.

Key Takeaways#

• 2D prefix sums turn rectangle range queries into four O(1) table lookups using inclusion-exclusion.
• Pad the prefix table with a leading row and column of zeros to avoid boundary special cases.
• Build cost O(m * n) is paid once; every subsequent query is O(1), which dominates over even thousands of calls.
• The immutable problem is prefix sums; the mutable problem is a 2D Fenwick tree (BIT). Knowing both is the senior-level answer.
• For range updates with range queries, escalate to a 2D segment tree with lazy propagation; for point updates with range queries, the BIT is almost always the right call.
• This is the foundation pattern behind Max Sum Submatrix, count submatrices summing to target, and many image-processing kernels.