范围总和查询2D-在C ++中可变
假设我们有一个称为矩阵的2D矩阵，我们必须计算由矩形的左上角和右下角定义的矩形内元素的总和。
所以，如果输入像
因此，如果我们像这样称呼它们，就会找到求和，更新值的方法
sumRegion(2,1,4,3)
更新(3,2,2)
sumRegion(2,1,4,3)，
那么输出将是8和10，因为上面的矩形（绿色）由(2,1)和(4,3)定义，其中sum和=8。
为了解决这个问题，我们将遵循以下步骤-
定义一棵2D阵列树
定义一个2D数组值
定义将矩阵作为输入的初始化程序
n：=矩阵的行大小
m：=（如果非n为非零，则为0，否则为col的col大小）
value：=定义一个大小为nxm的2D数组
树：=定义一个顺序为（n+1）x（m+1）的2D数组
对于初始化i：=0，当i−n时，更新（将i增加1），执行−
更新（i，j，matrix[i，j]）
对于初始化j：=0，当j<m时，更新（将j增加1），执行-
定义一个函数update()，它将使用row，col，val，
如果n等于0或m等于0，则-
返回
delta：=val-value[row，col]
value[row，col]：=val
对于初始化i：=行+1，当i<=n时，更新i：=i+i＆(-i)，执行-
tree[i，j]：=tree[i，j]+增量
对于初始化j：=col+1，当j<=m时，更新j：=j+j＆(-j)，执行-
定义一个函数sum()，将使用row，col，
ret：=0
对于初始化i：=行，当i>0时，更新i：=i-i＆(-i)，请执行-
ret：=ret+tree[i，j]
对于初始化j：=col，当j>0时，更新j：=j-j＆(-j)，执行-
返回ret
定义一个函数sumRegion()，它将使用row1，col1，row2，col2，
如果m等于0或n等于0，则-
返回0
（将第2行增加1）
（将第1行增加1）
（将col1增加1）
（将col2增大1）
返回sum(row2,col2)+sum(row1-1,col1-1)-sum(row1-1,col2)-sum(row2,col1-1)
例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class NumMatrix {
public:
int n, m;
vector<vector<int>> tree;
vector<vector<int>> value;
NumMatrix(vector<vector<int>> &matrix) {
n = matrix.size();
m = !n ? 0 : matrix[0].size();
value = vector<vector<int>>(n, vector<int>(m));
tree = vector<vector<int>>(n + 1, vector<int>(m + 1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
update(i, j, matrix[i][j]);
}
}
}
void update(int row, int col, int val) {
if (n == 0 || m == 0)
return;
int delta = val - value[row][col];
value[row][col] = val;
for (int i = row + 1; i <= n; i += i & (-i)) {
for (int j = col + 1; j <= m; j += j & (-j)) {
tree[i][j] += delta;
}
}
}
int sum(int row, int col) {
int ret = 0;
for (int i = row; i > 0; i -= i & (-i)) {
for (int j = col; j > 0; j -= j & (-j)) {
ret += tree[i][j];
}
}
return ret;
}
int sumRegion(int row1, int col1, int row2, int col2) {
if (m == 0 || n == 0)
return 0;
row2++;
row1++;
col1++;
col2++;
return sum(row2, col2) + sum(row1 - 1, col1 - 1) - sum(row1 - 1, col2) - sum(row2, col1 - 1);
}
};
main() {
vector<vector<int>> v = {
{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}};
NumMatrix ob(v);
cout << (ob.sumRegion(2, 1, 4, 3)) << endl;
ob.update(3, 2, 2);
cout << (ob.sumRegion(2, 1, 4, 3)) << endl;
}输入值
vector<vector<int>> v = {
{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}};
NumMatrix ob(v);
cout << (ob.sumRegion(2, 1, 4, 3)) << endl;
ob.update(3, 2, 2);
cout << (ob.sumRegion(2, 1, 4, 3)) << endl;输出结果
8 10