⚡Flashcard Drill➔
NeetCode #163LC-308MediumArrays & Hashing
← Back to All Problems

#163 · #308 · Range Sum Query 2D - Mutable(二维区域和检索 - 可变)

📌 Problem Statement & Constraints

Design a class supporting update(row, col, val) and sumRegion(row1, col1, row2, col2) on a 2D matrix. Constraints: 1 <= m, n <= 200; up to 10^4 calls.

💡 Core Algorithmic Approaches

  1. Keep a 2D prefix-sum table so queries are O(1).
  2. On update, write the new value into the matrix and rebuild the prefix table from the updated cell onward.
  3. The rebuild only needs to touch the suffix rectangle starting at (row, col), since earlier prefix entries are unaffected.
  4. A 2D Fenwick tree (BIT) gives O(log m * log n) per operation; the suffix rebuild is O(m * n) worst case but far simpler and fast enough at these limits.

💻 Benchmark Python3 Implementation

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self.matrix = matrix
        self.m = len(matrix)
        self.n = len(matrix[0])
        self.P = [[0] * (self.n + 1) for _ in range(self.m + 1)]
        for i in range(self.m):
            for j in range(self.n):
                self.P[i + 1][j + 1] = (self.P[i][j + 1] + self.P[i + 1][j]
                                        - self.P[i][j] + matrix[i][j])

    def update(self, row: int, col: int, val: int) -> None:
        self.matrix[row][col] = val
        # rebuild only the suffix rectangle affected by this cell
        for i in range(row, self.m):
            for j in range(col, self.n):
                self.P[i + 1][j + 1] = (self.P[i][j + 1] + self.P[i + 1][j]
                                        - self.P[i][j] + self.matrix[i][j])

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (self.P[row2 + 1][col2 + 1]
                - self.P[row1][col2 + 1]
                - self.P[row2 + 1][col1]
                + self.P[row1][col1])

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n) to build, O(m * n) worst case per update, O(1) per query. A 2D Fenwick tree would give O(log m * log n) for both operations.
💾 Space Complexity
O(m * n) for the prefix table plus the matrix copy.

⚠️ Interview Pitfalls & Follow-ups

  • Rebuilding the whole prefix table on every update: correct but wasteful; only the suffix rectangle changes.
  • Getting the inclusion-exclusion signs wrong in sumRegion: the final term is + P[row1][col1].
  • Forgetting to store the matrix: the rebuild reads from it, so the updated value must be written there first.
  • Using a 1D prefix sum per row: queries spanning multiple rows would still need a row loop, giving O(m) per query.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems