The Range Sum Query 2D - Mutable problem asks you to design a data structure that efficiently supports two operations on a 2D matrix of integers:
update(row, col, val): Update the value at position (row, col) to be val.sumRegion(row1, col1, row2, col2): Return the sum of the elements within the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2) (inclusive).Constraints:
update and sumRegion combined.The challenge is to perform both operations faster than a naive approach, which would be too slow for large numbers of queries and updates.
At first glance, you might think to simply update the matrix directly and sum the region by iterating over all relevant cells. However, this brute-force approach would be too slow, especially for large matrices and many queries.
The main challenge is to efficiently support both point updates and range sum queries. For 1D arrays, we can use a Binary Indexed Tree (Fenwick Tree) or a Segment Tree. For 2D matrices, we need to extend these ideas to two dimensions.
The key insight is that precomputing prefix sums can make queries fast, but updating the prefix sums after a change is expensive unless we use a special data structure. Therefore, we need a data structure that allows:
The 2D Binary Indexed Tree (Fenwick Tree) is a perfect fit for this use case, as it supports both operations in logarithmic time with respect to the matrix dimensions.
We solve this problem using a 2D Binary Indexed Tree (Fenwick Tree). Here's how it works step by step:
matrix[row][col] to val, compute the difference delta = val - matrix[row][col].delta through the BIT using the standard 2D BIT update process.(row1, col1) to (row2, col2) is calculated as:
sum(row2, col2) - sum(row1-1, col2) - sum(row2, col1-1) + sum(row1-1, col1-1)O(log m * log n) time, where m and n are the matrix dimensions.
This approach ensures that both update and sumRegion are efficient, even for large matrices and many operations.
Consider the following 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]
]
Suppose we perform the following operations:
sumRegion(2, 1, 4, 3) → Sum of rectangle from (2,1) to (4,3):update(3, 2, 2) → Update cell (3,2) from 0 to 2.sumRegion(2, 1, 4, 3) → Now the sum includes the updated value:With a 2D BIT, both the update and the region sum query are handled efficiently, without iterating through all the relevant cells each time.
Brute-force approach:
update: O(1) (just set the value)sumRegion: O(mn) in the worst case (must sum all cells in the region)This is too slow for large matrices and many queries.
Optimized (2D BIT) approach:update: O(log m * log n)sumRegion: O(log m * log n)Using a 2D Binary Indexed Tree ensures both operations are fast enough for the given constraints.
The Range Sum Query 2D - Mutable problem is efficiently solved by extending the Binary Indexed Tree (Fenwick Tree) to two dimensions. This data structure allows both point updates and region sum queries to be performed in logarithmic time with respect to the matrix dimensions. By maintaining a copy of the matrix and a 2D BIT, we avoid the inefficiencies of brute-force approaches and ensure that our solution can handle large numbers of operations swiftly and elegantly.
class NumMatrix:
def __init__(self, matrix):
if not matrix or not matrix[0]:
return
self.m, self.n = len(matrix), len(matrix[0])
self.tree = [[0] * (self.n + 1) for _ in range(self.m + 1)]
self.nums = [[0] * self.n for _ in range(self.m)]
for i in range(self.m):
for j in range(self.n):
self.update(i, j, matrix[i][j])
def update(self, row, col, val):
if not self.m or not self.n:
return
delta = val - self.nums[row][col]
self.nums[row][col] = val
i = row + 1
while i <= self.m:
j = col + 1
while j <= self.n:
self.tree[i][j] += delta
j += (j & -j)
i += (i & -i)
def _sum(self, row, col):
res = 0
i = row + 1
while i > 0:
j = col + 1
while j > 0:
res += self.tree[i][j]
j -= (j & -j)
i -= (i & -i)
return res
def sumRegion(self, row1, col1, row2, col2):
if not self.m or not self.n:
return 0
return (self._sum(row2, col2)
- self._sum(row1 - 1, col2)
- self._sum(row2, col1 - 1)
+ self._sum(row1 - 1, col1 - 1))
class NumMatrix {
public:
int m, n;
vector<vector<int>> tree, nums;
NumMatrix(vector<vector<int>>& matrix) {
m = matrix.size();
n = m ? matrix[0].size() : 0;
tree = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
nums = vector<vector<int>>(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
update(i, j, matrix[i][j]);
}
void update(int row, int col, int val) {
if (m == 0 || n == 0) return;
int delta = val - nums[row][col];
nums[row][col] = val;
for (int i = row + 1; i <= m; i += (i & -i)) {
for (int j = col + 1; j <= n; j += (j & -j)) {
tree[i][j] += delta;
}
}
}
int _sum(int row, int col) {
int res = 0;
for (int i = row + 1; i > 0; i -= (i & -i)) {
for (int j = col + 1; j > 0; j -= (j & -j)) {
res += tree[i][j];
}
}
return res;
}
int sumRegion(int row1, int col1, int row2, int col2) {
if (m == 0 || n == 0) return 0;
return _sum(row2, col2) - _sum(row1 - 1, col2)
- _sum(row2, col1 - 1) + _sum(row1 - 1, col1 - 1);
}
};
class NumMatrix {
int m, n;
int[][] tree, nums;
public NumMatrix(int[][] matrix) {
m = matrix.length;
n = m > 0 ? matrix[0].length : 0;
tree = new int[m + 1][n + 1];
nums = new int[m][n];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
update(i, j, matrix[i][j]);
}
public void update(int row, int col, int val) {
if (m == 0 || n == 0) return;
int delta = val - nums[row][col];
nums[row][col] = val;
for (int i = row + 1; i <= m; i += (i & -i)) {
for (int j = col + 1; j <= n; j += (j & -j)) {
tree[i][j] += delta;
}
}
}
private int sum(int row, int col) {
int res = 0;
for (int i = row + 1; i > 0; i -= (i & -i)) {
for (int j = col + 1; j > 0; j -= (j & -j)) {
res += tree[i][j];
}
}
return res;
}
public int sumRegion(int row1, int col1, int row2, int col2) {
if (m == 0 || n == 0) return 0;
return sum(row2, col2) - sum(row1 - 1, col2)
- sum(row2, col1 - 1) + sum(row1 - 1, col1 - 1);
}
}
class NumMatrix {
constructor(matrix) {
this.m = matrix.length;
this.n = this.m ? matrix[0].length : 0;
this.tree = Array(this.m + 1).fill(0).map(() => Array(this.n + 1).fill(0));
this.nums = Array(this.m).fill(0).map(() => Array(this.n).fill(0));
for (let i = 0; i < this.m; ++i)
for (let j = 0; j < this.n; ++j)
this.update(i, j, matrix[i][j]);
}
update(row, col, val) {
if (!this.m || !this.n) return;
let delta = val - this.nums[row][col];
this.nums[row][col] = val;
for (let i = row + 1; i <= this.m; i += (i & -i)) {
for (let j = col + 1; j <= this.n; j += (j & -j)) {
this.tree[i][j] += delta;
}
}
}
_sum(row, col) {
let res = 0;
for (let i = row + 1; i > 0; i -= (i & -i)) {
for (let j = col + 1; j > 0; j -= (j & -j)) {
res += this.tree[i][j];
}
}
return res;
}
sumRegion(row1, col1, row2, col2) {
if (!this.m || !this.n) return 0;
return this._sum(row2, col2)
- this._sum(row1 - 1, col2)
- this._sum(row2, col1 - 1)
+ this._sum(row1 - 1, col1 - 1);
}
}