Range Sum Query2D-C++では不変

matrixと呼ばれる2D行列があるとすると、（row1、col1）を使用して左上隅で定義され、（row1、col1）を使用して右下隅で定義される長方形内の要素の合計を見つける必要があります。 row2、col2）。

したがって、行列が-

上記の長方形で、（2,1）と（4,3）で定義された青色で、合計8が含まれています。

したがって、sumRegion（2、1、4、3）、sumRegion（1、1、2、2）、sumRegion（1、2、2、4）などのクエリを実行すると、それぞれ8、11、12が返されます。

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

• dpと呼ばれる行列を定義します。

• 次のようにタスクを初期化します

• n：=行数。 nが0の場合は、戻ります

• m：=列数

• dp：=サイズnxmの別の行列

• 0からnの範囲のiの場合

  • 0からmの範囲のjの場合

    • j – 1 <0の場合、dp [i、j]をmatrix [i、j]として設定します。それ以外の場合は、これを（dp [i、j --1] + matrix [i、j]）

      として設定します。

• 1からnの範囲のiの場合

  • 0からmの範囲のjの場合

    • dp [i、j]をdp [i – 1、j]

      だけ増やします。

• queryメソッドの場合、これにはrow1、col1、row2、col2が必要です

• ret：=dp [row2、col2]

• sub1：=0（row1 – 1 <0の場合）それ以外の場合はdp [row1 – 1、col2]

• sub2：=0 col1 – 1 <0の場合、それ以外の場合はdp [row2、col1 --1]

• row1 – 1<0またはcol1– 1 <0の場合、

  • 追加：=0

• それ以外の場合は、：=dp [row1 – 1、col1 – 1]

  を追加します

• return ret – sub1 – sub2 + add

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class NumMatrix {
   public:
   vector < vector <int>> dp;
   NumMatrix(vector<vector<int>>& matrix) {
      int n = matrix.size();
      if(!n) return;
      int m = matrix[0].size();
      dp = vector < vector <int>>(n, vector <int> (m));
      for(int i = 0; i < n; i++){
         for(int j = 0 ;j < m; j++){
            dp[i][j] = j - 1 < 0 ? matrix[i][j] : dp[i][j - 1] + matrix[i][j];
         }
      }
      for(int i = 1; i < n; i++){
         for(int j = 0; j < m; j++){
            dp[i][j] += dp[i - 1][j];
         }
      }
   }
   int sumRegion(int row1, int col1, int row2, int col2) {
      int ret = dp[row2][col2];
      int sub1 = row1 - 1 < 0 ? 0 : dp[row1 - 1][col2];
      int sub2 = col1 - 1 < 0 ? 0 : dp[row2][col1 - 1];
      int add = row1 - 1 < 0 || col1 - 1 < 0 ? 0 : dp[row1 - 1][col1 - 1];
      return ret - sub1 - sub2 + add;
   }
};
main(){
   vector<vector<int>> mat = {{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(mat);
   cout << ob.sumRegion(2,1,4,3) << endl;
   cout << ob.sumRegion(1,1,2,2) << endl;
   cout << ob.sumRegion(1,2,2,4) << endl;
}

入力

[[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)
sumRegion(1,1,2,2)
sumRegion(1,2,2,4)

出力

8
11
12