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

难度: Medium

给定一个二维矩阵 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⁵ <= matrix[i][j] <= 10⁵
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 10⁴ 次 sumRegion 方法

Submission

运行时间: 333 ms

内存: 27.9 MB

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m,n=len(matrix),len(matrix[0])
        self.regionSum=[[0]*n for _ in range(m)]
        frowSum=0
        for i in range(n):
            frowSum+=matrix[0][i]
            self.regionSum[0][i]+=frowSum
            
        for i in range(1,m):
            rowSum=0
            for j in range(n):
                rowSum+=matrix[i][j]
                self.regionSum[i][j]=rowSum+self.regionSum[i-1][j]
        # print(self.regionSum)
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        if row1==0 and col1==0:
            return self.regionSum[row2][col2]
        elif row1==0:
            return self.regionSum[row2][col2]-self.regionSum[row2][col1-1]
        elif col1==0:
            return self.regionSum[row2][col2]-self.regionSum[row1-1][col2]
        else:
            # print(self.regionSum[row2][col2],self.regionSum[row2][col1-1],self.regionSum[row1-1][col2],self.regionSum[row1-1][col1-1])
            return self.regionSum[row2][col2]-self.regionSum[row2][col1-1]-self.regionSum[row1-1][col2]+self.regionSum[row1-1][col1-1]
            


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

Explain

这个题解使用了二维前缀和的思路。具体来说，通过预处理计算矩阵的二维前缀和，然后利用前缀和数组快速计算任意子矩形的元素和。在预处理阶段，先计算第一行的前缀和，然后逐行计算每一行的前缀和，其中每个位置的前缀和等于当前行到当前位置的元素和加上上一行相同列的前缀和。在查询阶段，对于任意的子矩形，可以利用预处理得到的前缀和数组，使用四个前缀和的加减运算得到子矩形的元素和，需要注意处理边界情况。

时间复杂度: O(mn + q)

空间复杂度: O(mn)

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        # 初始化前缀和数组，大小与原矩阵相同
        self.regionSum = [[0] * n for _ in range(m)]
        
        # 计算第一行的前缀和
        frowSum = 0
        for i in range(n):
            frowSum += matrix[0][i]
            self.regionSum[0][i] = frowSum
        
        # 逐行计算前缀和
        for i in range(1, m):
            rowSum = 0
            for j in range(n):
                rowSum += matrix[i][j]
                self.regionSum[i][j] = rowSum + self.regionSum[i-1][j]
    
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # 处理边界情况
        if row1 == 0 and col1 == 0:
            return self.regionSum[row2][col2]
        elif row1 == 0:
            return self.regionSum[row2][col2] - self.regionSum[row2][col1-1]
        elif col1 == 0:
            return self.regionSum[row2][col2] - self.regionSum[row1-1][col2]
        else:
            # 使用前缀和计算子矩形的元素和
            return self.regionSum[row2][col2] - self.regionSum[row2][col1-1] - self.regionSum[row1-1][col2] + self.regionSum[row1-1][col1-1]

Explore

在计算二维前缀和时，对于第一行，直接逐个累加元素以形成前缀和，因为上面没有其他行可以参考。对于每一行的第一列，前缀和是当前行的第一个元素加上其上方行的第一列前缀和。这样处理是为了在后续查询中能快速得到任何子矩形的元素总和。

计算当前位置的前缀和时加上上一行相同列的前缀和，是为了包含当前位置上方的所有元素的和。这样，每个位置的前缀和实际上代表了从矩阵的左上角开始到当前位置的所有元素的总和，这是通过动态地添加当前行的元素和到上一行的前缀和来实现的。数学逻辑是利用累加和的性质，使得后续的子矩形和能够通过简单的加减运算快速计算出来。

在查询函数`sumRegion`中，使用四个前缀和来计算子矩阵的元素总和的方法基于容斥原理。具体的运算逻辑是：首先获取右下角的前缀和，它包含了从矩阵左上角到右下角的所有元素的和。然后，减去上边界和左边界的相关前缀和（如果存在），因为这部分被重复计算了。最后，如果同时减去了上边界和左边界，那么左上角的交叉部分被减去了两次，所以要加回来。这样就可以准确计算出子矩阵的元素总和。

题解中没有明确提及对查询子矩阵边界超出原始矩阵范围的处理。在实际应用中，应该添加边界检查来确保查询的子矩阵边界不超出原始矩阵的范围。这可以通过限制row1, col1, row2, col2的值在有效范围内（即不小于0，不大于最大行数和列数减一）来实现。如果超出范围，应适当调整或返回错误信息。