Range Sum Query2D-C++で変更可能

行列と呼ばれる2D行列があるとすると、左上隅と右下隅で定義される長方形内の要素の合計を計算する必要があります。

したがって、入力が次のような場合

合計を見つけて値を更新するメソッドもそうなります

sumRegion（2、1、4、3）

update（3、2、2）

sumRegion（2、1、4、3）、

上記の長方形（緑色）は（2,1）と（4、3）で定義され、合計=8であるため、出力は8と10になります。

これを解決するには、次の手順に従います-

• 1つの2D配列ツリーを定義する

• 1つの2D配列値を定義する

• 行列を入力として受け取る初期化子を定義します

• n：=行列の行サイズ

• m：=（nがゼロ以外の場合は0、それ以外の場合は行列の列サイズ）

• value：=サイズnxmの2D配列を1つ定義します

• tree：=次数（n + 1）x（m + 1）の2D配列を1つ定義します

• 初期化i：=0の場合、i − nの場合、更新（iを1増やします）、実行-

  • 初期化j：=0の場合、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：=行+ 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：=行を初期化する場合、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