Range Sum Query 2D - Immutable

Problem: Range Sum Query 2D - Immutable

Since in this problem, we have a lot of sum queries, we'd better store information of sum so that we don't need to do much calculation. My idea is that we can store sum of range from upper-left corner to each node at first so that we can achieve any range sum query in no more than 4 calculation.

Code in Python:

class NumMatrix(object):
    def __init__(self, matrix):
        """
        initialize your data structure here.
        :type matrix: List[List[int]]
        """
        for i in xrange(len(matrix)):
            for j in xrange(len(matrix[0])):
                if i > 0: matrix[i][j] += matrix[i-1][j]
                if j > 0: matrix[i][j] += matrix[i][j-1]
                if i > 0 and j > 0: matrix[i][j] -= matrix[i-1][j-1]
        self.matrix = matrix


    def sumRegion(self, row1, col1, row2, col2):
        """
        sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        ans = self.matrix[row2][col2]
        if row1 > 0: ans -= self.matrix[row1-1][col2]
        if col1 > 0: ans -= self.matrix[row2][col1-1]
        if row1 > 0 and col1 > 0: ans += self.matrix[row1-1][col1-1]
        return ans