LeetCode上二维区域和检索 - 矩阵不可变，与昨天相比，是将数组变为二维数组来求范围内的和

同样可以用暴力求法来遍历范围内的所有数相加得到结果，和昨天的题目一样，这样做能够通过提交但是时间和内存消耗都比较大

var NumMatrix = function(matrix) {
  this.matrix = matrix
};
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
  // 暴力循环
  let res = 0
  for(let i = row1; i <= row2; i++) {
    for(let j = col1;j <= col2;j++) {
      res += this.matrix[i][j]
    }
  }
  return res
};

所以还是会通过前缀和来优化程序，这里使用了二维数组下的前缀和
通过2021/03/01 每日一题 区域和检索 - 数组不可变这篇文章，知道了前缀和是前i项数组的和即presum[i] = nums[i] + nums[i -1] + ....+ nums[0]，那么怎么用这个前缀和对应到二维数组上？
求取前缀和数组
假设传入一个二维数组matrix = [[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]]排列成表格如下图所示

求取结果
如果计算matrix[1][1] - matrix[3][3]之间所有数的和通过我们前面求取的二维数组前缀和又要怎么计算？

所以整个过程可以表示如下：

1. 在创建类的时候使用
   presum[i][j] = presum[i-1][j] + presum[i][j-1] - presum[i-1][j-1] + matrix[i][j]
   计算出前缀和数组
2. 在求范围和的时候使用
   rangeSum(r1,c1,r2,c2) = presum[r2+1][c2+1] - presum[r1][c2+1] - presum[r2 + 1][c1] + presum[r1][c1]
   通过前缀和数组来计算求和

最终代码如下

var NumMatrix = function(matrix) {
    let rows, cols
    if (!matrix.length) {
        rows = cols = 1
    } else {
        // 要扩展一行一列
        rows = matrix.length + 1
        cols = matrix[0].length + 1
    }
    // 快速定义二维数组，并且填充0
    let preSum = Array.from({ length: rows }, () => new Array(cols).fill(0))
    // 计算前缀和，从1开始跳过扩展的地方
    for (i = 1; i < rows; i++) {
        for (j = 1; j < cols; j++) {
            preSum[i][j] =preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1]
        }
    }
    this.preSum = preSum
};

NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    let preSum = this.preSum
    return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1]
};

可以发现用时下降了50%+，内存消耗也减少了

总结下前缀和

1. 前缀和可以减少重复计算，因为不会每次都遍历求和
2. 生成前缀和数组的时候还是需要计算的
3. 如果只计算少量次数前缀和看不出太多优势，优势在于多次计算的时候，只需要查表就能求值，一次求前缀和数组的计算，后面就能多次使用，从而减少时间消耗