304 range-sum-query-2d-immutable

题目

Given a 2D matrix matrix, handle multiple queries of the following type:

Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). Implement the NumMatrix class:

NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix. int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). You must design an algorithm where sumRegion works on O(1) time complexity.原题

思路

可以使用一维度前缀和解决，但是 rangeSum 的时间复杂度将在 O(N) N = Row2 - Row1, 不符合本题的时间复杂度要求

使用二维前缀和时，需要注意构建二维前缀数组 sum[row][col] 的推导过程

• 当前节点和上是邻边相邻节点和和对角相邻节点和和当前节点组成
• 最终公式为： sum[row][col] = sum[row -1][col] + sum[row][col - 1] - sum[row - 1][col - 1] + matreic[row][col]

同时在计算 rangeSum 时，注意对角线之间的面积推导计算

• 当前子矩形面积和由 上边相邻矩形 和 左边相邻矩形 和 对角相邻矩形 和 当前最大矩形和组成

• 最终公式为： sum[row2][col2] - sum[row2][col1 - 1] - sum[row1][col2 - 1] + sum[row1 - 1][col - 1]

解题

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m = len(matrix)
        n = len(matrix[0])
        # self.sums = [[0] * (n + 1)] * m
        # Error !!! use the same reference 
        self.sums = [[0] * (n + 1) for _ in range(m + 1)]

        for row, arr in enumerate(matrix):
            for col, num in enumerate(arr):
                self.sums[row + 1][col + 1] = self.sums[row][col + 1]  + self.sums[row + 1][col] -  self.sums[row][col] + num
        

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        

        return self.sums[row2 + 1][col2 + 1] - self.sums[row1][col2 + 1 ] - self.sums[row2 + 1][col1] + self.sums[row1][col1]


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

复杂度分析

• 时间复杂度 O(N) / N = right - left + 1 仅遍历部分数组
• 空间复杂度 O(1) 仅用到部分变量，未用到额外存储空间