Giả sử chúng ta có một ma trận 2D được gọi là ma trận, chúng ta phải tính tổng các phần tử bên trong hình chữ nhật được xác định bởi góc trên bên trái và góc dưới bên phải của nó.
Vì vậy, nếu đầu vào giống như
| 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 |
Vì vậy, sẽ là các phương thức để tìm tổng, cập nhật giá trị, nếu chúng ta gọi chúng như
sumRegion (2, 1, 4, 3)
cập nhật (3, 2, 2)
sumRegion (2, 1, 4, 3),
thì đầu ra sẽ là 8 và 10, vì hình chữ nhật trên (với màu xanh lá cây) được xác định bởi (2,1) và (4, 3), chứa tổng =8.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một cây mảng 2D
-
Xác định một giá trị mảng 2D
-
Xác định bộ khởi tạo nhận ma trận làm đầu vào
-
n:=kích thước hàng của ma trận
-
m:=(nếu không n là khác 0 thì 0, ngược lại là kích thước col của ma trận)
-
value:=Xác định một mảng 2D có kích thước n x m
-
tree:=Xác định một mảng 2D có thứ tự (n + 1) x (m + 1)
-
để khởi tạo i:=0, khi i - n, cập nhật (tăng i lên 1), thực hiện -
-
để khởi tạo j:=0, khi j
-
cập nhật (i, j, ma trận [i, j])
-
-
-
Xác định một bản cập nhật hàm (), điều này sẽ lấy hàng, col, val,
-
nếu n giống 0 hoặc m giống 0 thì -
-
trở lại
-
-
delta:=val - value [row, col]
-
value [row, col]:=val
-
để khởi tạo i:=row + 1, khi i <=n, hãy cập nhật i:=i + i &(-i), do -
-
để khởi tạo j:=col + 1, khi j <=m, cập nhật j:=j + j &(-j), do -
-
tree [i, j]:=tree [i, j] + delta
-
-
-
Xác định một hàm sum (), điều này sẽ lấy hàng, col,
-
ret:=0
-
để khởi tạo i:=row, khi i> 0, hãy cập nhật i:=i - i &(-i), do -
-
để khởi tạo j:=col, khi j> 0, hãy cập nhật j:=j - j &(-j), do -
-
ret:=ret + cây [i, j]
-
-
-
trả lại ret
-
Xác định một hàm sumRegion (), điều này sẽ lấy row1, col1, row2, col2,
-
nếu m giống 0 hoặc n giống 0 thì -
-
trả về 0
-
-
(tăng hàng 2 lên 1)
-
(tăng hàng 1 lên 1)
-
(tăng col1 lên 1)
-
(tăng col2 lên 1)
-
trả về sum (row2, col2) + sum (row1 - 1, col1 - 1) - sum (row1 - 1, col2) - sum (row2, col1 - 1)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
} Đầu vào
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; Đầu ra
8 10