算法1

(2d前缀和 Y总大法好)

时间复杂度 $O(n^2)$

python3 代码

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        if len(matrix) != 0:
            self.s = [[0 for i in range(len(matrix[0]) + 3)] for i in range(len(matrix) + 3)]
            for i in range(len(matrix)):
                for j in range(len(matrix[0])):
                    self.s[i+1][j+1] = self.s[i][j+1] + self.s[i+1][j] - self.s[i][j] + matrix[i][j]


    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.s[row2+1][col2+1] + self.s[row1][col1] - self.s[row1][col2+1] - self.s[row2+1][col1]