数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++二维可变范围求和查询
假设我们有一个名为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)
update(3, 2, 2)
sumRegion(2, 1, 4, 3) ,
则输出将为8和10，因为上面的矩形（绿色部分）由(2,1)和(4, 3)定义，其总和为8。
为了解决这个问题，我们将遵循以下步骤：
定义一个二维数组tree
定义一个二维数组value
定义一个初始化函数，该函数以matrix作为输入
n := matrix的行大小
m := (如果n不为零，则为matrix的列大小，否则为0)
value := 定义一个大小为n x m的二维数组
tree := 定义一个大小为(n + 1) x (m + 1)的二维数组
for i := 0 to n-1 do −
for j := 0 to m-1 do −
update(i, j, matrix[i, j])
定义一个函数update()，它将接收row, col, val作为参数，
如果n等于0或m等于0，则：
返回
delta := val - value[row, col]
value[row, col] := val
for i := row + 1 to n, i := i + (i & (-i)) do −
for j := col + 1 to m, j := j + (j & (-j)) do −
tree[i, j] := tree[i, j] + delta
定义一个函数sum()，它将接收row, col作为参数，
ret := 0
for i := row downto 1, i := i - (i & (-i)) do −
for j := col downto 1, j := j - (j & (-j)) do −
ret := ret + tree[i, j]
返回ret
定义一个函数sumRegion()，它将接收row1, col1, row2, col2作为参数，
如果m等于0或n等于0，则：
返回0
row2 := row2 + 1
row1 := row1 + 1
col1 := col1 + 1
col2 := 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
浏览量：354
