LeetCode 308 - Range Sum Query 2D - Mutable
The problem asks us to design a mutable 2D range sum data structure. We are given a matrix of integers, and we must support two operations efficiently: 1. Update the value at a specific cell. 2. Compute the sum of all values inside a rectangular submatrix.
Difficulty: 🟡 Medium
Topics: Array, Design, Binary Indexed Tree, Segment Tree, Matrix
Solution
Problem Understanding
The problem asks us to design a mutable 2D range sum data structure. We are given a matrix of integers, and we must support two operations efficiently:
- Update the value at a specific cell.
- Compute the sum of all values inside a rectangular submatrix.
The rectangle is defined by two corners:
- Upper-left corner
(row1, col1) - Lower-right corner
(row2, col2)
The sumRegion query must include every element inside that rectangle, including the boundary cells.
A naive implementation would simply recompute the rectangle sum every time by iterating through all cells in the queried region. While this works functionally, it becomes inefficient when many updates and queries are performed.
The constraints are important:
- Matrix dimensions are at most
200 x 200 - Up to
5000operations will occur - Both positive and negative numbers are allowed
The matrix is not large enough to require extremely advanced optimizations, but it is large enough that repeatedly scanning rectangular regions can become expensive. Since updates also occur, a static prefix sum approach alone is insufficient because updating one value would require rebuilding many prefix sums.
This combination of:
- frequent range sum queries
- point updates
is a classic indicator that we need a dynamic range query data structure.
Several edge cases are important:
- A matrix with only one row or one column
- A matrix with a single cell
- Negative values, which prevent shortcut assumptions
- Queries that cover the entire matrix
- Updates that overwrite existing values with the same value
- Repeated updates to the same cell
The problem guarantees valid indices, so we do not need bounds checking beyond standard implementation correctness.
Approaches
Brute Force Approach
The simplest solution stores the matrix directly.
For an update operation:
- Change the value at
(row, col)directly.
For a sum query:
- Iterate through every cell inside the rectangle.
- Add all values together.
This approach is straightforward and always correct because it explicitly examines every required element.
However, the performance becomes problematic when many large rectangle queries occur. In the worst case, each query may scan the entire matrix.
If the matrix size is 200 x 200, one query could require scanning 40,000 cells. Across thousands of operations, this becomes inefficient.
Key Insight for the Optimal Solution
The key observation is that we need:
- fast point updates
- fast range sum queries
A 2D Binary Indexed Tree, also called a 2D Fenwick Tree, is specifically designed for this situation.
A Fenwick Tree allows:
- point updates in logarithmic time
- prefix sum queries in logarithmic time
In one dimension:
- update is
O(log n) - prefix sum is
O(log n)
In two dimensions:
- update becomes
O(log m * log n) - prefix query becomes
O(log m * log n)
We can compute any rectangle sum using inclusion-exclusion on prefix sums.
The important idea is that the Fenwick Tree stores cumulative partial sums in a structured way so that both updates and queries affect only logarithmically many nodes.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | Update: O(1), Query: O(m × n) | O(1) | Directly scans rectangles |
| Optimal 2D Fenwick Tree | Update: O(log m × log n), Query: O(log m × log n) | O(m × n) | Efficient dynamic range sums |
Algorithm Walkthrough
1. Store the Original Matrix
We keep a copy of the matrix values separately.
This is necessary because during updates we must compute:
delta = new_value - old_value
The Fenwick Tree stores cumulative information, not raw cell values, so we need the original value to determine how much the update changes the sums.
2. Create a 2D Fenwick Tree
We create a 2D array called bit.
The Fenwick Tree uses 1-based indexing because the low-bit traversal logic works naturally with positive indices.
So:
- matrix index
(0, 0)maps to Fenwick index(1, 1)
The tree dimensions become:
(rows + 1) x (cols + 1)
3. Build the Tree
We initialize the structure by inserting every matrix value using the update logic.
For each cell:
- call
update(row, col, value)
This ensures the Fenwick Tree is populated consistently.
4. Point Update Operation
When updating (row, col):
- Compute the difference:
delta = val - current_value
- Store the new value in the matrix.
- Propagate the delta through the Fenwick Tree.
The propagation works by repeatedly adding the lowest set bit:
i += i & -i
j += j & -j
Each Fenwick node represents a rectangular region, so every affected region must receive the delta.
5. Prefix Sum Query
We define a helper function:
prefix_sum(row, col)
This returns the sum of all elements from:
(0,0) to (row,col)
The traversal moves upward through the Fenwick Tree using:
i -= i & -i
j -= j & -j
This efficiently aggregates all contributing regions.
6. Rectangle Sum Query
To compute a rectangle:
(row1,col1) to (row2,col2)
we use inclusion-exclusion:
sum =
prefix(row2,col2)
- prefix(row1-1,col2)
- prefix(row2,col1-1)
+ prefix(row1-1,col1-1)
This removes the overlapping regions correctly.
Why it works
The Fenwick Tree maintains the invariant that each node stores the sum of a specific subrectangle determined by binary index ranges.
Point updates propagate changes to every region that includes the updated cell. Prefix queries collect exactly the regions needed to reconstruct the desired cumulative sum.
Because rectangle sums can be expressed as combinations of prefix sums, the structure always returns correct results.
Python Solution
from typing import List
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
if not matrix or not matrix[0]:
self.rows = 0
self.cols = 0
return
self.rows = len(matrix)
self.cols = len(matrix[0])
self.matrix = [[0] * self.cols for _ in range(self.rows)]
self.bit = [
[0] * (self.cols + 1)
for _ in range(self.rows + 1)
]
for r in range(self.rows):
for c in range(self.cols):
self.update(r, c, matrix[r][c])
def update(self, row: int, col: int, val: int) -> None:
if self.rows == 0 or self.cols == 0:
return
delta = val - self.matrix[row][col]
self.matrix[row][col] = val
i = row + 1
while i <= self.rows:
j = col + 1
while j <= self.cols:
self.bit[i][j] += delta
j += j & -j
i += i & -i
def _prefix_sum(self, row: int, col: int) -> int:
total = 0
i = row + 1
while i > 0:
j = col + 1
while j > 0:
total += self.bit[i][j]
j -= j & -j
i -= i & -i
return total
def sumRegion(
self,
row1: int,
col1: int,
row2: int,
col2: int
) -> int:
return (
self._prefix_sum(row2, col2)
- self._prefix_sum(row1 - 1, col2)
- self._prefix_sum(row2, col1 - 1)
+ self._prefix_sum(row1 - 1, col1 - 1)
)
# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# obj.update(row,col,val)
# param_2 = obj.sumRegion(row1,col1,row2,col2)
The implementation begins by allocating both:
- the original matrix storage
- the Fenwick Tree storage
The constructor initializes the structure by inserting each value through the standard update method. This avoids duplicate tree-building logic.
The update method computes the delta between old and new values, then propagates that delta through all relevant Fenwick nodes.
The _prefix_sum helper calculates cumulative sums from (0,0) to (row,col) using the Fenwick traversal rules.
Finally, sumRegion applies inclusion-exclusion to compute arbitrary rectangle sums efficiently.
Go Solution
type NumMatrix struct {
rows int
cols int
matrix [][]int
bit [][]int
}
func Constructor(matrix [][]int) NumMatrix {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return NumMatrix{}
}
rows := len(matrix)
cols := len(matrix[0])
numMatrix := NumMatrix{
rows: rows,
cols: cols,
matrix: make([][]int, rows),
bit: make([][]int, rows+1),
}
for i := 0; i < rows; i++ {
numMatrix.matrix[i] = make([]int, cols)
}
for i := 0; i <= rows; i++ {
numMatrix.bit[i] = make([]int, cols+1)
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
numMatrix.Update(r, c, matrix[r][c])
}
}
return numMatrix
}
func (this *NumMatrix) Update(row int, col int, val int) {
if this.rows == 0 || this.cols == 0 {
return
}
delta := val - this.matrix[row][col]
this.matrix[row][col] = val
i := row + 1
for i <= this.rows {
j := col + 1
for j <= this.cols {
this.bit[i][j] += delta
j += j & -j
}
i += i & -i
}
}
func (this *NumMatrix) prefixSum(row int, col int) int {
total := 0
i := row + 1
for i > 0 {
j := col + 1
for j > 0 {
total += this.bit[i][j]
j -= j & -j
}
i -= i & -i
}
return total
}
func (this *NumMatrix) SumRegion(
row1 int,
col1 int,
row2 int,
col2 int,
) int {
return (
this.prefixSum(row2, col2) -
this.prefixSum(row1-1, col2) -
this.prefixSum(row2, col1-1) +
this.prefixSum(row1-1, col1-1)
)
}
/**
* Your NumMatrix object will be instantiated and called as such:
* obj := Constructor(matrix);
* obj.Update(row,col,val);
* param_2 := obj.SumRegion(row1,col1,row2,col2);
*/
The Go implementation mirrors the Python logic closely.
A struct is used to store:
- matrix dimensions
- the original matrix
- the Fenwick Tree
Go slices are initialized explicitly using make.
Unlike Python, Go does not have dynamic nested list creation syntax, so every row must be allocated individually.
Integer overflow is not a concern under the given constraints because the maximum possible matrix sum remains well within Go's int range on LeetCode systems.
Worked Examples
Example 1
Initial 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 |
Query 1
sumRegion(2, 1, 4, 3)
Requested rectangle:
| 2 | 0 | 1 | ||
| 1 | 0 | 1 | ||
| 0 | 3 | 0 |
Values included:
2 + 0 + 1 + 1 + 0 + 1 + 0 + 3 + 0 = 8
Result:
8
Update
update(3, 2, 2)
Cell (3,2) changes:
0 -> 2
Delta:
+2
This delta propagates through the Fenwick Tree.
Updated matrix:
| 3 | 0 | 1 | 4 | 2 |
| 5 | 6 | 3 | 2 | 1 |
| 1 | 2 | 0 | 1 | 5 |
| 4 | 1 | 2 | 1 | 7 |
| 1 | 0 | 3 | 0 | 5 |
Query 2
sumRegion(2, 1, 4, 3)
New rectangle values:
2 + 0 + 1 + 1 + 2 + 1 + 0 + 3 + 0 = 10
Result:
10
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | Update: O(log m × log n), Query: O(log m × log n) | Fenwick traversal in both dimensions |
| Space | O(m × n) | Storage for Fenwick Tree and matrix copy |
The Fenwick Tree reduces both updates and prefix queries to logarithmic traversal in each dimension.
For each update:
- we move through at most
log mrow indices - and
log ncolumn indices
The same applies to prefix sum computation.
Rectangle queries require four prefix sums, which still preserves logarithmic complexity.
Test Cases
# Example from problem statement
matrix = NumMatrix([
[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]
])
assert matrix.sumRegion(2, 1, 4, 3) == 8 # original example query
matrix.update(3, 2, 2)
assert matrix.sumRegion(2, 1, 4, 3) == 10 # updated example query
# Single cell matrix
matrix = NumMatrix([[5]])
assert matrix.sumRegion(0, 0, 0, 0) == 5 # single element query
matrix.update(0, 0, 10)
assert matrix.sumRegion(0, 0, 0, 0) == 10 # single element update
# Single row matrix
matrix = NumMatrix([[1, 2, 3, 4]])
assert matrix.sumRegion(0, 1, 0, 3) == 9 # partial row query
matrix.update(0, 2, 10)
assert matrix.sumRegion(0, 0, 0, 3) == 17 # row after update
# Single column matrix
matrix = NumMatrix([
[1],
[2],
[3]
])
assert matrix.sumRegion(0, 0, 2, 0) == 6 # full column query
matrix.update(1, 0, 10)
assert matrix.sumRegion(0, 0, 2, 0) == 14 # column after update
# Negative values
matrix = NumMatrix([
[-1, -2],
[-3, -4]
])
assert matrix.sumRegion(0, 0, 1, 1) == -10 # negative numbers
matrix.update(0, 1, 5)
assert matrix.sumRegion(0, 0, 1, 1) == -3 # mixed positive and negative
# Entire matrix query
matrix = NumMatrix([
[1, 1],
[1, 1]
])
assert matrix.sumRegion(0, 0, 1, 1) == 4 # whole matrix
# Repeated updates on same cell
matrix = NumMatrix([
[0, 0],
[0, 0]
])
matrix.update(1, 1, 5)
matrix.update(1, 1, 7)
matrix.update(1, 1, -2)
assert matrix.sumRegion(0, 0, 1, 1) == -2 # repeated overwrite
# Large rectangle inside matrix
matrix = NumMatrix([
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
])
assert matrix.sumRegion(1, 1, 2, 2) == 28 # bottom-right submatrix
Test Summary
| Test | Why |
|---|---|
| Problem example | Validates standard functionality |
| Single cell matrix | Smallest possible input |
| Single row matrix | Tests degenerate horizontal structure |
| Single column matrix | Tests degenerate vertical structure |
| Negative values | Ensures sums handle negatives correctly |
| Entire matrix query | Validates full-range correctness |
| Repeated updates | Ensures delta logic remains correct |
| Interior submatrix | Tests inclusion-exclusion correctness |
Edge Cases
Single Cell Matrix
A 1 x 1 matrix is the smallest valid input. This case is important because Fenwick Tree implementations often rely on index movement logic that can behave incorrectly near boundaries.
Our implementation handles this naturally because:
- the Fenwick Tree still uses 1-based indexing
- update and query loops terminate correctly
- inclusion-exclusion still works
Negative Numbers
Because matrix values may be negative, we cannot rely on monotonic behavior or shortcut assumptions.
For example:
[-1, -2]
[-3, -4]
must correctly return -10.
The Fenwick Tree stores exact cumulative sums, so negative values are handled identically to positive ones.
Repeated Updates to the Same Cell
A common bug occurs when updates overwrite values multiple times.
For example:
0 -> 5 -> 7 -> -2
If the implementation directly adds new values instead of computing deltas, the tree becomes corrupted.
Our implementation avoids this by storing the current matrix value separately and always computing:
delta = new_value - old_value
Only the difference is propagated through the tree, ensuring consistency after any number of updates.