原题地址（中等）

方法1—前缀和

思路

和303题类似的思路，不难。
官解：https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/er-wei-qu-yu-he-jian-suo-ju-zhen-bu-ke-b-2z5n/

代码

  1. class NumMatrix {
  2. public:
  3.     vector<vector<int>> sumV;
  4.     NumMatrix(vector<vector<int>>& matrix) {
  5.         sumV = matrix;
  6.         int row = sumV.size(), col;
  7.         if(row == 0)    col = 0;
  8.         else    col = sumV[0].size();
  9.         for(int i = 0; i < row; i++) {
  10.             for(int j = 0; j < col; j++) {
  11.                 if(j > 0)   sumV[i][j] += sumV[i][j-1];
  12.                 if(i > 0)   sumV[i][j] += sumV[i-1][j];
  13.                 if(i > 0 && j > 0)  sumV[i][j] -= sumV[i-1][j-1];
  14.             }
  15.         }
  16.     }
  18.     int sumRegion(int row1, int col1, int row2, int col2) {
  19.         int ans = sumV[row2][col2];
  20.         if(row1 > 0)    ans -= sumV[row1-1][col2];
  21.         if(col1 > 0)    ans -= sumV[row2][col1-1];
  22.         if(row1 > 0 && col1 > 0)    ans += sumV[row1-1][col1-1];
  23.         return ans;
  24.     }
  25. };

时空复杂度

时间：初始化O(mn) 检索O(1) 空间：O(mn)