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

题目链接：304. 二维区域和检索 - 矩阵不可变
参考思路：labuladong 前缀和数组

题目描述

给定一个二维矩阵 matrix，多次查询其中某个子矩阵范围内所有元素的总和。该矩阵不会被修改。

实现 NumMatrix 类：

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

核心思考：二维前缀和

这道题是 303. 区域和检索 - 数组不可变 从一维到二维的扩展。

在一维中，前缀和数组 s[i] 记录的是前 i 个元素的总和，区间和通过一次减法得到。

在二维中，我们构造一个前缀和矩阵 preSum，其中 preSum[i][j] 表示从矩阵左上角 (0, 0) 到 (i-1, j-1) 这个子矩阵内所有元素的和。同样多开一行一列、初始值为 0，用于简化边界处理。

初始化：构建前缀和矩阵

preSum[i][j] 可以通过容斥原理从相邻的三个已知前缀和推导而来：

$$preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]$$

其中减去 preSum[i-1][j-1] 是因为它在上方和左方的前缀和中被重复加了两次。

查询：利用容斥原理求子矩阵和

要计算子矩阵 (x1, y1) 到 (x2, y2) 的元素总和，同样使用容斥原理：

$$sumRegion = preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]$$

即：目标区域 = 整块 - 上方多余 - 左方多余 + 左上角重复减去的部分。

解题思路 (Python)

class NumMatrix:
    # preSum[i][j] 记录矩阵 [0, 0, i-1, j-1] 的元素和
    def __init__(self, matrix: List[List[int]]):
        m = len(matrix)
        n = len(matrix[0])
        if m == 0 or n == 0:
            return
        # 构造前缀和矩阵
        self.preSum = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # 计算每个矩阵 [0, 0, i, j] 的元素和
                self.preSum[i][j] = (self.preSum[i - 1][j] + self.preSum[i][j - 1] +
                                     matrix[i - 1][j - 1] - self.preSum[i - 1][j - 1])

    # 计算子矩阵 [x1, y1, x2, y2] 的元素和
    def sumRegion(self, x1: int, y1: int, x2: int, y2: int) -> int:
        # 目标矩阵之和由四个相邻矩阵运算获得
        return (self.preSum[x2 + 1][y2 + 1] - self.preSum[x1][y2 + 1] -
                self.preSum[x2 + 1][y1] + self.preSum[x1][y1])

复杂度分析

• 时间复杂度：
  • 初始化：$O(m \times n)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。需要遍历整个矩阵来构建二维前缀和。
  • 单次查询：$O(1)$。每次调用 sumRegion 只需要做常数次加减运算。
• 空间复杂度：$O(m \times n)$。需要额外存储一个大小为 $(m+1) \times (n+1)$ 的二维前缀和矩阵。