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
- Keep a 2D prefix-sum table so queries are O(1).
- On update, write the new value into the matrix and rebuild the prefix table from the updated cell onward.
- The rebuild only needs to touch the suffix rectangle starting at
(row, col), since earlier prefix entries are unaffected. - 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.