C++-এ 2D রেঞ্জ সম কোয়েরি - মিউটেবল (Range Sum Query 2D - Mutable)

ধরি আমাদের একটি 2D ম্যাট্রিক্স matrix আছে। আমাদের ম্যাট্রিক্সের একটি রেক্ট্যাঙ্গুলার অঞ্চলের উপাদানগুলোর যোগফল বের করতে হবে, যা এর উপরের-বাম (upper left) এবং নিচের-ডান (lower right) কর্নার দিয়ে সংজ্ঞায়িত।

উদাহরণস্বরূপ, ম্যাট্রিক্স:

মেথডগুলো কল করলে যেন:

• sumRegion(2, 1, 4, 3)
• update(3, 2, 2)
• sumRegion(2, 1, 4, 3)

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

সমাধানের ধাপসমূহ

• দুটি 2D অ্যারে tree এবং value সংজ্ঞায়িত।
• ইনিশিয়ালাইজার যা matrix নিবে:
  • n := matrix.size(), m := matrix[0].size()
  • value := n x m, tree := (n+1) x (m+1)
  • সব i,j জন্য 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):
    • j = col+1; j <= m; j += j & (-j): tree[i][j] += delta
• sum(row, col):
  • ret := 0
  • i = row; i > 0; i -= i & (-i):
    • j = col; j > 0; j -= j & (-j): ret += tree[i][j]
  • ret ফেরত
• sumRegion(row1, col1, row2, col2):
  • যদি m==0 বা n==0: 0 ফেরত
  • row2++, row1++, col1++, col2++
  • ফেরত: 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> tree;
    vector> value;
    NumMatrix(vector>& matrix) {
        n = matrix.size();
        m = !n ? 0 : matrix[0].size();
        value = vector>(n, vector(m));
        tree = vector>(n + 1, vector(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);
    }
};

int main() {
    vector> 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> 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