資料結構
網路
關係型資料庫管理系統 (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
