难度: Hard
Submission
运行时间: 55 ms
内存: 19.8 MB
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
self.matrix = matrix
self.P = [list(accumulate([0]+sub)) for sub in matrix]
def update(self, row: int, col: int, val: int) -> None:
self.matrix[row][col] = val
self.P[row] = list(accumulate([0]+self.matrix[row]))
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return sum(self.P[r][col2+1]-self.P[r][col1] for r in range(row1, row2+1))
Explain
该题解使用了前缀和技巧。在构造函数中，通过对每一行计算前缀和，并将结果存储在二维数组 P 中。当需要更新某个元素时，只需要更新对应行的前缀和数组即可。在计算区域和时，可以利用前缀和的性质，对于每一行，用区域右端点的前缀和减去左端点的前缀和，然后将所有行的结果累加起来，即可得到最终的区域和。
时间复杂度: 构造函数: O(mn), update: O(n), sumRegion: O(m)
空间复杂度: O(mn)
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
# 存储原始矩阵
self.matrix = matrix
# 计算每一行的前缀和，并存储在二维数组 P 中
self.P = [list(accumulate([0]+sub)) for sub in matrix]
def update(self, row: int, col: int, val: int) -> None:
# 更新原始矩阵中的元素值
self.matrix[row][col] = val
# 重新计算更新行的前缀和数组
self.P[row] = list(accumulate([0]+self.matrix[row]))
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
# 计算区域和
# 对于每一行，用区域右端点的前缀和减去左端点的前缀和，然后将所有行的结果累加
return sum(self.P[r][col2+1]-self.P[r][col1] for r in range(row1, row2+1))
Explore
在构造函数中，我们首先检查矩阵是否为空，如果为空，则前缀和数组也应该被初始化为空数组。对于只有一行或一列的情况，前缀和的计算方法仍然适用。即使矩阵仅有一个元素，我们同样计算其前缀和，这会是一个由一个元素加上一个初始的0组成的列表。总之，我们的前缀和数组的计算对于任何形状的矩阵都是通用的。
在执行 update 操作时，我们首先在原始矩阵中更新指定位置的元素值。随后，为了确保前缀和数组的正确性，我们会重新计算整个行的前缀和。这种方法确保了即使同一位置进行多次更新，前缀和数组也总是与当前的矩阵状态保持一致，因此不会累积错误的结果。
在 sumRegion 函数中，理论上应该有一步检查来确保输入的索引（row1, col1, row2, col2）都在矩阵的有效边界内。然而，在题解中并未明确这种检查。在实际应用中，应该添加适当的边界检查，如果输入的索引超出矩阵范围，应返回错误或进行适当的处理，以避免运行时错误。
在本题解的前缀和数组设计中，每行的前缀和是独立计算的，不依赖于其他行的数据。因此，更新某个元素时，只需重新计算该元素所在行的前缀和，而不需要考虑列之间的依赖关系。这简化了更新操作，但仍能准确计算任何区域的和，因为区域和的计算是通过逐行计算并累加得到的。