题目
给定一个二维矩阵
matrix，以下类型的多个请求：
- 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为
(row1, col1)，右下角 为(row2, col2)。实现
NumMatrix类：
NumMatrix(int[][] matrix)给定整数矩阵matrix进行初始化int sumRegion(int row1, int col1, int row2, int col2)返回 左上角(row1, col1)、右下角(row2, col2)所描述的子矩阵的元素 总和 。
解题
class NumMatrix:def __init__(self, matrix):if not matrix or not matrix[0]:return# 获取矩阵的维度self.rows = len(matrix)self.cols = len(matrix[0])# 构建前缀和矩阵self.prefix_sums = [[0] * (self.cols + 1) for _ in range(self.rows + 1)]for r in range(self.rows):for c in range(self.cols):self.prefix_sums[r + 1][c + 1] = (self.prefix_sums[r + 1][c] +self.prefix_sums[r][c + 1] -self.prefix_sums[r][c] +matrix[r][c])def sumRegion(self, row1, col1, row2, col2):return (self.prefix_sums[row2 + 1][col2 + 1]- self.prefix_sums[row2 + 1][col1]- self.prefix_sums[row1][col2 + 1]+ self.prefix_sums[row1][col1])# 使用示例
matrix = [[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]
]num_matrix = NumMatrix(matrix)
print(num_matrix.sumRegion(2, 1, 4, 3)) # 输出 8
print(num_matrix.sumRegion(1, 1, 2, 2)) # 输出 11
print(num_matrix.sumRegion(1, 2, 2, 4)) # 输出 12
)
