304. 二维区域和检索 - 矩阵不可变.md

304. 二维区域和检索 - 矩阵不可变

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = **(4, 3)，**该子矩形内元素的总和为 8。

示例：

给定 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]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

提示：

• 你可以假设矩阵不可变。
• 会多次调用 sumRegion 方法*。*
• 你可以假设 row1 ≤ row2 且 col1 ≤ col2 。

思路

找规律：

1、当前的前缀和prefixSum[row][col] = prefix[row-1][col] + prefix[row][col-1] - prefix[row-1][col-1] + matrix[row][col]

2、当前矩阵块的前缀和sum[row2][col2] - sum[row1-1][col2] - sum[row2][col1-1] + sum[row1-1][col1-1]

3、需要注意取值边界，越界取 0

代码

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function(matrix) {
  const rowLen = matrix.length, colLen = matrix[0] && matrix[0].length;
  const prefixSum = Array(rowLen).fill(0).map(item => Array(colLen));

  for(let row = 0; row < rowLen; row ++) {
    for(let col = 0; col < colLen; col ++) {
      let prevSumRow = prefixSum[row][col-1] || 0;
      let prevSumCol = (prefixSum[row-1] && prefixSum[row-1][col]) || 0;
      let prevSumRowCol = (prefixSum[row-1] && prefixSum[row-1][col-1]) || 0;
      prefixSum[row][col] = prevSumRow + prevSumCol - prevSumRowCol +matrix[row][col]
    }
  }
  // console.log(prefixSum)
  this.prefixSum = prefixSum;
};

/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
  const sum = this.prefixSum;
  return sum[row2][col2] - ((sum[row1-1] && sum[row1-1][col2]) || 0) - (sum[row2][col1-1] || 0) + ((sum[row1-1] && sum[row1-1][col1-1]) || 0)
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * var obj = new NumMatrix(matrix)
 * var param_1 = obj.sumRegion(row1,col1,row2,col2)
 */

复杂度分析

时间复杂度 初始化 $O(N^2)$ sumRegion $O(1)$

空间复杂度 $O(N^2)$