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

假设我们有一个称为矩阵的2D矩阵，我们必须计算由矩形的左上角和右下角定义的矩形内元素的总和。

所以，如果输入像

因此，如果我们像这样称呼它们，就会找到求和，更新值的方法

sumRegion(2,1,4,3)

更新(3,2,2)

sumRegion(2,1,4,3)，

那么输出将是8和10，因为上面的矩形（绿色）由(2,1)和(4,3)定义，其中sum和= 8。

为了解决这个问题，我们将遵循以下步骤-

• 定义一棵2D阵列树

• 定义一个2D数组值

• 定义将矩阵作为输入的初始化程序

• n：=矩阵的行大小

• m：=（如果非n为非零，则为0，否则为col的col大小）

• value：=定义一个大小为nxm的2D数组

• 树：=定义一个顺序为（n + 1）x（m + 1）的2D数组

• 对于初始化i：= 0，当i − n时，更新（将i增加1），执行−

• 更新（i，j，matrix [i，j]）

• 对于初始化j：= 0，当j <m时，更新（将j增加1），执行-

• 定义一个函数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)，执行-

• tree [i，j]：= tree [i，j] +增量

• 对于初始化j：= col + 1，当j <= m时，更新j：= j + j＆(-j)，执行-

• 定义一个函数sum()，将使用row，col，

• ret：= 0

• 对于初始化i：=行，当i> 0时，更新i：= i-i＆(-i)，请执行-

• ret：= ret + tree [i，j]

• 对于初始化j：= col，当j> 0时，更新j：= j-j＆(-j)，执行-

• 返回ret

• 定义一个函数sumRegion()，它将使用row1，col1，row2，col2，

• 如果m等于0或n等于0，则-

• 返回0

• （将第2行增加1）

• （将第1行增加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