मान लीजिए हमारे पास एक 2D मैट्रिक्स है जिसे 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 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
एक 2D ऐरे tree परिभाषित करें
एक 2D ऐरे value परिभाषित करें
matrix को इनपुट के रूप में लेने वाला इनिशियलाइज़र परिभाषित करें
n := matrix का पंक्ति आकार
m := (यदि n शून्येतर नहीं है, तो 0, अन्यथा matrix का स्तंभ आकार)
value := आकार n x m का एक 2D ऐरे परिभाषित करें
tree := क्रम (n + 1) x (m + 1) का एक 2D ऐरे परिभाषित करें
i := 0 से आरंभ करें, जब i − n, अद्यतन करें (i को 1 से बढ़ाएं), करें −
j := 0 से आरंभ करें, जब j < m, अद्यतन करें (j को 1 से बढ़ाएं), करें −
update(i, j, matrix[i, j])
update() नामक एक फ़ंक्शन परिभाषित करें, जो row, col, val लेगा,
यदि n 0 के समान है या m 0 के समान है, तो −
लौटें
delta := val - value[row, col]
value[row, col] := val
i := row + 1 से आरंभ करें, जब i <= n, अद्यतन करें i := i + i & (-i), करें −
j := col + 1 से आरंभ करें, जब j <= m, अद्यतन करें j := j + j & (-j), करें −
tree[i, j] := tree[i, j] + delta
sum() नामक एक फ़ंक्शन परिभाषित करें, जो row, col लेगा,
ret := 0
i := row से आरंभ करें, जब i > 0, अद्यतन करें i := i - i & (-i), करें −
j := col से आरंभ करें, जब j > 0, अद्यतन करें j := j - j & (-j), करें −
ret := ret + tree[i, j]
ret लौटाएं
sumRegion() नामक एक फ़ंक्शन परिभाषित करें, जो row1, col1, row2, col2 लेगा,
यदि m 0 के समान है या n 0 के समान है, तो −
0 लौटाएं
(row2 को 1 से बढ़ाएं)
(row1 को 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
