# 308. Range Sum Query 2D - Mutable

Given a 2D matrix matrix , find the sum of the elements inside the rectangle defined by its upper left corner ( row 1, col 1) and lower right corner ( row 2, col 2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3) , which contains sum = 8.

Example:

``````Given 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]
]

sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10
``````

Note:

1. The matrix is only modifiable by the update function.
2. You may assume the number of calls to update and sumRegion function is distributed evenly.
3. You may assume that row 1 ≤ row 2 and col 1 ≤ col 2.

``````// Binary Indexed Tree
class NumMatrix {
public:
NumMatrix(vector<vector<int>> &matrix) {
if (matrix.empty() || matrix[0].empty()) return;
mat.resize(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
bit.resize(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[i].size(); ++j) {
update(i, j, matrix[i][j]);
}
}
}

void update(int row, int col, int val) {
int diff = val - mat[row + 1][col + 1];
for (int i = row + 1; i < mat.size(); i += i&-i) {
for (int j = col + 1; j < mat[i].size(); j += j&-j) {
bit[i][j] += diff;
}
}
mat[row + 1][col + 1] = val;
}

int sumRegion(int row1, int col1, int row2, int col2) {
return getSum(row2 + 1, col2 + 1) - getSum(row1, col2 + 1) - getSum(row2 + 1, col1) + getSum(row1, col1);
}

int getSum(int row, int col) {
int res = 0;
for (int i = row; i > 0; i -= i&-i) {
for (int j = col; j > 0; j -= j&-j) {
res += bit[i][j];
}
}
return res;
}

private:
vector<vector<int>> mat;
vector<vector<int>> bit;
};
``````

``````// Column Sum
class NumMatrix {
public:
NumMatrix(vector<vector<int>> &matrix) {
if (matrix.empty() || matrix[0].empty()) return;
mat = matrix;
colSum.resize(matrix.size() + 1, vector<int>(matrix[0].size(), 0));
for (int i = 1; i < colSum.size(); ++i) {
for (int j = 0; j < colSum[0].size(); ++j) {
colSum[i][j] = colSum[i - 1][j] + matrix[i - 1][j];
}
}
}

void update(int row, int col, int val) {
for (int i = row + 1; i < colSum.size(); ++i) {
colSum[i][col] += val - mat[row][col];
}
mat[row][col] = val;
}

int sumRegion(int row1, int col1, int row2, int col2) {
int res = 0;
for (int j = col1; j <= col2; ++j) {
res += colSum[row2 + 1][j] - colSum[row1][j];
}
return res;
}

private:
vector<vector<int>> mat;
vector<vector<int>> colSum;
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/308

Range Sum Query 2D - Immutable

Range Sum Query - Mutable

Range Sum Query - Immutable

https://leetcode.com/problems/range-sum-query-2d-mutable/

https://leetcode.com/problems/range-sum-query-2d-mutable/discuss/75852/15ms-easy-to-understand-java-solution

https://leetcode.com/problems/range-sum-query-2d-mutable/discuss/75870/Java-2D-Binary-Indexed-Tree-Solution-clean-and-short-17ms

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation