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

题目

解题

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