রেঞ্জ সমষ্টি কোয়েরি 2D - C++ এ পরিবর্তনযোগ্য

ধরুন আমাদের ম্যাট্রিক্স নামে একটি 2D ম্যাট্রিক্স আছে, আমাদের আয়তক্ষেত্রের ভিতরের উপাদানগুলির যোগফল তার উপরের বাম কোণ এবং নীচের ডান কোণ দ্বারা সংজ্ঞায়িত করতে হবে৷

সুতরাং, যদি ইনপুট মত হয়

তাই যোগফল, আপডেট মান খুঁজে বের করার পদ্ধতি হবে, যদি আমরা সেগুলিকে

sumRegion(2, 1, 4, 3)

আপডেট (3, 2, 2)

sumRegion(2, 1, 4, 3),

তাহলে আউটপুট হবে 8 এবং 10, কারণ উপরের আয়তক্ষেত্রটি (সবুজ রঙের সাথে) (2,1) এবং (4, 3) দ্বারা সংজ্ঞায়িত করা হয়েছে, যাতে যোগফল =8 থাকে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি 2D অ্যারে ট্রি সংজ্ঞায়িত করুন

• একটি 2D অ্যারে মান নির্ধারণ করুন

• ইনপুট হিসাবে ম্যাট্রিক্স গ্রহণকারী ইনিশিয়ালাইজারকে সংজ্ঞায়িত করুন

• n :=ম্যাট্রিক্সের সারির আকার

• m :=(যদি n অ-শূন্য হয়, তাহলে 0, অন্যথায় ম্যাট্রিক্সের কলের আকার)

• মান :=n x m

  আকারের একটি 2D অ্যারে নির্ধারণ করুন

• ট্রি :=অর্ডারের একটি 2D অ্যারে নির্ধারণ করুন (n + 1) x (m + 1)

• আরম্ভ করার জন্য i :=0, যখন i − n, আপডেট করুন (i 1 দ্বারা বাড়ান), করুন −

  • j শুরু করার জন্য :=0, যখন j করুন

    • আপডেট(i, j, matrix[i, j])

• একটি ফাংশন আপডেট(), এটি সারি, কোল, ভ্যাল,

  লাগবে

• যদি n 0 এর সমান হয় বা m 0 এর সমান হয়, তাহলে −

  • ফেরত

• ডেল্টা :=ভ্যাল - মান[সারি, কল]

• মান [সারি, কল] :=ভ্যাল

• আরম্ভ করার জন্য i :=সারি + 1, যখন i <=n, আপডেট i :=i + i &(-i), do −

  • আরম্ভ করার জন্য j :=col + 1, যখন j <=m, আপডেট j :=j + j &(-j), do −

    • গাছ[i, j] :=গাছ[i, j] + ডেল্টা

• একটি ফাংশন sum() সংজ্ঞায়িত করুন, এটি সারি, কল,

  লাগবে

• ret :=0

• আরম্ভ করার জন্য i :=সারি, যখন i> 0, আপডেট i :=i - i &(-i), do −

  • আরম্ভ করার জন্য j :=col, যখন j> 0, j আপডেট করুন :=j - j &(-j), −

    • ret :=ret + গাছ[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