LeetCode刷题实战308：二维区域和检索 - 可变
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 二维区域和检索 - 可变，我们先来看题面：
https://leetcode-cn.com/problems/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 (row1, col1) and lower right corner (row2, col2).
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
给你一个 2D 矩阵 matrix，请计算出从左上角 (row1, col1) 到右下角 (row2, col2) 组成的矩形中所有元素的和。
上述红色矩形框内的，该矩形由左上角 (row1, col1) = (2, 1) 和右下角 (row2, col2) = (4, 3) 确定。其中，所包括的元素总和 sum = 8。
示例
示例：
给定 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
注意:
矩阵 matrix 的值只能通过 update 函数来进行修改
你可以默认 update 函数和 sumRegion 函数的调用次数是均匀分布的
你可以默认 row1 ≤ row2，col1 ≤ col2解题
按照直接的求前n项和的思路来做这道题也可以过, 但是显然这道题期望的并不是这样的答案. 期望的应该是二叉索引树,。
class NumMatrix {
public:
void add(int val, int x, int y)
{
while(y < sum[x].size())
{
sum[x][y] += val;
y += (y&-y);
}
}
int getSum(int x, int y)
{
int ans = 0;
while(y > 0)
{
ans += sum[x][y];
y -= (y&-y);
}
return ans;
}
NumMatrix(vector<vector<int>> &matrix):vec(matrix) {
if(matrix.size()==0) return;
int m = matrix.size(), n = matrix[0].size();
sum.resize(m, vector<int>(n+1, 0));
for(int i =0; i < m; i++)
for(int j =1; j <= n; j++)
add(matrix[i][j-1], i, j);
}
void update(int row, int col, int val) {
int d = val - vec[row][col];
vec[row][col] = val;
add(d, row, col+1);
}
int sumRegion(int row1, int col1, int row2, int col2) {
int ans = 0;
for(int i = row1; i <= row2; i++)
ans += (getSum(i, col2+1) - getSum(i, col1));
return ans;
}
private:
vector<vector<int>> sum;
vector<vector<int>> &vec;
};好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-06-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录