各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 37 天。今天力扣上的每日一题是「304. 二维区域和检索 - 矩阵不可变」。

解题思路

• 做这种初始化一次、检索多次的题目的秘诀：在初始化的时候做预处理。比如 preSum。

今天的每日一题让求二维数组中某个子矩形区域的和。很容易看出，今天的题目是 303. 区域和检索 - 数组不可变 的升级版。

本题是二维空间的 preSum。

步骤一：求 preSum
我们先从如何求出二维空间的 preSum。

我们定义 $preSum[i][j]$ 表示 从 $[0,0]$ 位置到 $[i,j]$ 位置的子矩形所有元素之和。
可以用下图帮助理解： S(O, D) = S(O, C) + S(O, B) - S(O, A) + D

减去 S(O, A) 的原因是 S(O, C) 和 S(O, B) 中都有 S(O, A)，即加了两次 S(O, A)，所以需要减去一次S(O, A)。

即，对应了以下的递推公式：

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

步骤二：根据 preSum 求子矩形面积

前面已经求出了数组中从 $[0,0]$ 位置到 $[i,j]$ 位置的 preSum。下面要利用 preSum[i][j] 来快速求出任意子矩形的面积。

同样利用一张图来说明：

S(A, D) = S(O, D) - S(O, E) - S(O, F) + S(O, G)

加上子矩形 S(O, G) 面积的原因是S(O, E) 和 S(O, F) 中都有 S(O, G)，即减了两次 S(O, G)，所以需要加上一次S(O, G)。

对应的递推公式是：

preSum[row2 + 1][col2 + 1] - preSum[row2 + 1][col1] - preSum[row1][col2 + 1] + preSum[row1][col1]

代码

下面代码实现的时候，使用的preSum 比原矩阵 matrix多了一行一列，是为了让第0行与第0列的元素也能使用上面的递推公式。如果preSum矩阵大小和martix大小相等，则需要对第0行与第0列特殊判断。

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            M, N = 0, 0
        else:
            M, N = len(matrix), len(matrix[0])
        self.preSum = [[0] * (N + 1) for _ in range(M + 1)]
        for i in range(M):
            for j in range(N):
                self.preSum[i + 1][j + 1] = self.preSum[i][j + 1] + self.preSum[i + 1][j]  - self.preSum[i][j] + matrix[i][j]
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.preSum[row2 + 1][col2 + 1] - self.preSum[row2 + 1][col1] - self.preSum[row1][col2 + 1] + self.preSum[row1][col1]

• 时间复杂度：构造函数的时间复杂度是 $O(M * N)$； sumRegion 函数的时间复杂度是 $O(1)$
• 空间复杂度：利用了preSum 矩阵，空间是 O(M * N)。

刷题心得

一维的preSum 拓展成二维 preSum 已经学会了，那如果是 N 维的应该怎么处理呢？

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！