0304. 二维区域和检索 - 矩阵不可变【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 二维前缀和

1. 📝 题目描述

• leetcode

给定一个二维矩阵 matrix，以下类型的多个请求：

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

实现 NumMatrix 类：

• NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
• int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和。

---

示例 1：

输入:
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[
  [
    [
      [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]
    ]
  ],
  [2,1,4,3],
  [1,1,2,2],
  [1,2,2,4]
]
输出:
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([
  [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.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

---

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -10^5 <= matrix[i][j] <= 10^5
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• 最多调用 10^4 次 sumRegion 方法

2. 🎯 s.1 - 二维前缀和

c

typedef struct {
    int** prefix;
    int m, n;
} NumMatrix;

NumMatrix* numMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) {
    NumMatrix* obj = (NumMatrix*)malloc(sizeof(NumMatrix));
    int m = matrixSize, n = matrixColSize[0];
    obj->m = m; obj->n = n;
    obj->prefix = (int**)malloc(sizeof(int*) * (m + 1));
    for (int i = 0; i <= m; i++) {
        obj->prefix[i] = (int*)calloc(n + 1, sizeof(int));
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            obj->prefix[i][j] = matrix[i - 1][j - 1] + obj->prefix[i - 1][j] + obj->prefix[i][j - 1] - obj->prefix[i - 1][j - 1];
        }
    }
    return obj;
}

int numMatrixSumRegion(NumMatrix* obj, int row1, int col1, int row2, int col2) {
    return obj->prefix[row2 + 1][col2 + 1] - obj->prefix[row1][col2 + 1] - obj->prefix[row2 + 1][col1] + obj->prefix[row1][col1];
}

void numMatrixFree(NumMatrix* obj) {
    for (int i = 0; i <= obj->m; i++) free(obj->prefix[i]);
    free(obj->prefix);
    free(obj);
}

js

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function (matrix) {
  const m = matrix.length,
    n = matrix[0].length
  this.prefix = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      this.prefix[i][j] =
        matrix[i - 1][j - 1] +
        this.prefix[i - 1][j] +
        this.prefix[i][j - 1] -
        this.prefix[i - 1][j - 1]
    }
  }
}

/**
 * @param {number} row1
 * @param {number} col1
 * @param {number} row2
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
  return (
    this.prefix[row2 + 1][col2 + 1] -
    this.prefix[row1][col2 + 1] -
    this.prefix[row2 + 1][col1] +
    this.prefix[row1][col1]
  )
}

py

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.prefix[i][j] = matrix[i - 1][j - 1] + self.prefix[i - 1][j] + self.prefix[i][j - 1] - self.prefix[i - 1][j - 1]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.prefix[row2 + 1][col2 + 1] - self.prefix[row1][col2 + 1] - self.prefix[row2 + 1][col1] + self.prefix[row1][col1]

• 时间复杂度：初始化 $O(m\times n)$，查询 $O(1)$
• 空间复杂度：$O(m\times n)$，前缀和数组

算法思路：

• 预处理二维前缀和数组，$prefix[i][j]$ 表示左上角 $(0,0)$ 到 $(i-1,j-1)$ 的元素总和
• 查询时利用容斥原理：$sum=prefix[r2+1][c2+1]-prefix[r1][c2+1]-prefix[r2+1][c1]+prefix[r1][c1]$