范围总和查询 2D - C++ 中的不可变

假设我们有一个称为矩阵的二维矩阵，我们必须使用 (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。

示例（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