범위 합계 쿼리 2D - 변경 불가능

2D 행렬matrix이 주어지면 다음 유형의 여러 쿼리를 처리합니다.

왼쪽 위 모서리matrix와 오른쪽 아래 모서리(row1, col1)로 정의된 직사각형 내부의 (row2, col2) 요소의 합을 계산합니다.

NumMatrix 클래스를 구현합니다.

NumMatrix(int[][] matrix) 정수 행렬matrix로 개체를 초기화합니다.

int sumRegion(int row1, int col1, int row2, int col2) 왼쪽 위 모서리matrix와 오른쪽 아래 모서리(row1, col1)로 정의된 사각형 내부의 (row2, col2) 요소의 합계를 반환합니다.

예 1:



입력
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[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]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
산출
[널, 8, 11, 12]

설명
NumMatrix numMatrix = 새 NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3);//8을 반환합니다(즉, 빨간색 사각형의 합).
numMatrix.sumRegion(1, 1, 2, 2);//11을 반환합니다(즉, 녹색 사각형의 합).
numMatrix.sumRegion(1, 2, 2, 4);//12를 반환합니다(즉, 파란색 사각형의 합).

제약:

m == matrix.length

n == matrix[i].length

1 <= m, n <= 200

-104 <= matrix[i][j] <= 104

0 <= row1 <= row2 < m

0 <= col1 <= col2 < n

최대 104 호출이 sumRegion 로 이루어집니다.

해결책:

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m = len(matrix)
        n = len(matrix[0])
        self.matrix = matrix
        self.qsum = [[None for i in range(n)] for j in range(m)]

    def getSum(self, i, j):
        if i < 0 or j < 0:
            return 0
        if self.qsum[i][j] != None:
            return self.qsum[i][j]
        prev = self.getSum(i - 1, j - 1)
        row = self.getSum(i - 1, j)
        col = self.getSum(i, j - 1)
        res = row + col + self.matrix[i][j] - prev
        self.qsum[i][j] = res
        return res

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        c = self.getSum(row2, col2)
        l = self.getSum(row2, col1 - 1)
        t = self.getSum(row1 - 1, col2)
        s = self.getSum(row1 - 1, col1 - 1)
        return c - l - t + s


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