import collections
class NumMatrix(object):

    def __init__(self, matrix):

        if not matrix or not matrix[0]:
            return

        m, n = len(matrix), len(matrix[0])
        self.cumsum2D = collections.defaultdict(int)
        for i in range(m):
            for j in range(n):
                self.cumsum2D[i, j] = matrix[i][j] + self.cumsum2D[i - 1, j] + self.cumsum2D[i, j - 1] - self.cumsum2D[
                    i - 1, j - 1]

    def sumRegion(self, row1, col1, row2, col2):

        return self.cumsum2D[row2, col2] + self.cumsum2D[row1 - 1, col1 - 1] \
               - self.cumsum2D[row2, col1 - 1] - self.cumsum2D[row1 - 1, col2]


"""
class NumMatrix(object):

    def __init__(self, matrix):
        :type matrix: List[List[int]]
        self.mat=matrix

    def sumRegion(self, row1, col1, row2, col2):
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        sum=0
        for i in range(row1,row2+1):
            for j in range(col1,col2+1):
                sum+=self.mat[i][j]
        return sum
"""

mat=[[[4,5]]]
solution=NumMatrix(mat)
print(solution.sumRegion(0,0,1,1))
