रेंज सम क्वेरी 2D - C++ में परिवर्तनशील

मान लीजिए कि हमारे पास मैट्रिक्स नामक एक 2D मैट्रिक्स है, हमें आयत के अंदर के तत्वों के योग की गणना इसके ऊपरी बाएँ कोने और निचले दाएँ कोने से परिभाषित करनी होगी।

तो, अगर इनपुट पसंद है

तो योग, अद्यतन मूल्य खोजने के तरीके होंगे, अगर हम उन्हें पसंद करते हैं

समक्षेत्र(2, 1, 4, 3)

अपडेट(3, 2, 2)

sumRegion(2, 1, 4, 3) ,

तो आउटपुट 8 और 10 होगा, जैसा कि उपरोक्त आयत (हरे रंग के साथ) (2,1) और (4, 3) द्वारा परिभाषित किया गया है, जिसमें योग =8 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक 2D सरणी ट्री परिभाषित करें

• एक 2डी सरणी मान परिभाषित करें

• मैट्रिक्स को इनपुट के रूप में लेने वाले प्रारंभकर्ता को परिभाषित करें

• n :=मैट्रिक्स की पंक्ति का आकार

• m :=(यदि नहीं n गैर-शून्य है, तो 0, अन्यथा मैट्रिक्स का col आकार)

• मान :=n x m आकार के एक 2D सरणी को परिभाषित करें

• पेड़ :=क्रम की एक 2D सरणी परिभाषित करें (n + 1) x (m + 1)

• इनिशियलाइज़ i :=0 के लिए, जब i - n, अपडेट करें (i को 1 से बढ़ाएँ), करें -

  • इनिशियलाइज़ j :=0 के लिए, जब j

    • अपडेट (i, j, मैट्रिक्स [i, j])

• फ़ंक्शन अपडेट () को परिभाषित करें, इसमें पंक्ति, कॉल, वैल,

  . लगेगा

• यदि n, 0 के समान है या m, 0 के समान है, तो -

  • वापसी

• डेल्टा:=वैल - मान [पंक्ति, कर्नल]

• value[row, col] :=वैल

• इनिशियलाइज़ करने के लिए i :=row + 1, जब i <=n, अपडेट i :=i + i &(-i), do -

  • j :=col + 1 को इनिशियलाइज़ करने के लिए, जब j <=m, अपडेट j :=j + j &(-j), करें -

    • पेड़ [i, j] :=पेड़[i, j] + डेल्टा

• फ़ंक्शन योग को परिभाषित करें (), इसमें पंक्ति, कॉलम,

  लगेगा

• रिट:=0

• प्रारंभ करने के लिए मैं:=पंक्ति, जब i> 0, अद्यतन i:=i - i और (-i), करते हैं -

  • प्रारंभ करने के लिए j :=col, जब j> 0, अद्यतन j :=j - j &(-j), करें -

    • रिट :=रिट + ट्री [i, j]

• वापसी रिट

• फ़ंक्शन को परिभाषित करें sumRegion(), इसमें row1, col1, row2, col2,

  लगेगा

• यदि m, 0 के समान है या n, 0 के समान है, तो -

  • वापसी 0

• (पंक्ति2 को 1 से बढ़ाएं)

• (पंक्ति1 को 1 से बढ़ाएं)

• (col1 को 1 से बढ़ाएं)

• (col2 को 1 से बढ़ाएं)

• वापसी राशि (पंक्ति 2, कॉलम 2) + योग (पंक्ति 1 - 1, कॉलम 1 - 1) - योग (पंक्ति 1 - 1, कॉलम 2) - योग (पंक्ति 2, कॉलम 1 - 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