สมมติว่าเรามีเมทริกซ์ 2 มิติที่เรียกว่าเมทริกซ์ เราต้องคำนวณผลรวมขององค์ประกอบภายในสี่เหลี่ยมผืนผ้าที่กำหนดโดยมุมซ้ายบนและมุมขวาล่าง
ดังนั้นหากอินพุตเป็นแบบ
| 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)
อัปเดต(3, 2, 2)
sumRegion(2, 1, 4, 3) ,
จากนั้นผลลัพธ์จะเป็น 8 และ 10 เนื่องจากสี่เหลี่ยมผืนผ้าด้านบน (ที่มีสีเขียว) ถูกกำหนดโดย (2,1) และ (4, 3) ซึ่งมีผลรวม =8
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดแผนผังอาร์เรย์ 2 มิติหนึ่งรายการ
-
กำหนดค่าอาร์เรย์ 2 มิติหนึ่งค่า
-
กำหนดตัวเริ่มต้นที่ใช้เมทริกซ์เป็นอินพุต
-
n :=ขนาดแถวของเมทริกซ์
-
m :=(ถ้าไม่ใช่ n ไม่เป็นศูนย์ แสดงว่าเป็น 0 มิฉะนั้น ขนาด col ของเมทริกซ์)
-
ค่า :=กำหนดอาร์เรย์ 2 มิติหนึ่งขนาด n x m
-
tree :=กำหนดอาร์เรย์ 2 มิติของคำสั่ง (n + 1) x (m + 1)
-
สำหรับการเริ่มต้น i :=0 เมื่อ i − n อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
-
สำหรับการเริ่มต้น j :=0 เมื่อ j
-
อัปเดต (i, j, matrix[i, j])
-
-
-
กำหนดฟังก์ชัน update() จะใช้ row, col, val,
-
ถ้า n เท่ากับ 0 หรือ m เท่ากับ 0 แล้ว −
-
กลับ
-
-
delta :=val - ค่า[แถว, col]
-
value[row, col] :=val
-
สำหรับการเริ่มต้น i :=แถว + 1 เมื่อ i <=n อัปเดต i :=i + i &(-i) ทำ -
-
สำหรับการเริ่มต้น j :=col + 1 เมื่อ j <=m อัปเดต j :=j + j &(-j) do -
-
tree[i, j] :=tree[i, j] + เดลต้า
-
-
-
กำหนดฟังก์ชัน sum() ซึ่งจะใช้แถว col
-
ยกเลิก :=0
-
สำหรับการเริ่มต้น i :=row เมื่อ i> 0, update i :=i - i &(-i), do −
-
สำหรับการเริ่มต้น j :=col เมื่อ j> 0, อัปเดต j :=j - j &(-j) ทำ −
-
ret :=ret + tree[i, j]
-
-
-
รีเทิร์น
-
กำหนดฟังก์ชัน sumRegion() ซึ่งจะใช้ row1, col1, row2, col2,
-
ถ้า m เท่ากับ 0 หรือ n เท่ากับ 0 แล้ว −
-
คืนค่า 0
-
-
(เพิ่มแถวที่ 2 ขึ้น 1)
-
(เพิ่มแถวที่ 1 ขึ้น 1)
-
(เพิ่ม col1 โดย 1)
-
(เพิ่ม col2 ขึ้น 1)
-
ผลตอบแทนรวม(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
