class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.matrix = matrix
        n, m = len(self.matrix), len(self.matrix[0])
        dp = [[0]*(m+1) for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1]

        self.dp = dp

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