Range Sum Query 2D - Immutable

还是prefix sum的做法

class NumMatrix(object):

    def __init__(self, matrix):
        """
        :type matrix: List[List[int]]
        """
        n = len(matrix)
        if not n:
            return 

        m = len(matrix[0])
        if not m:
            return 0

        self.cumSum = [[0] * (m + 1) for _ in xrange(n)]

        for i in xrange(n):
            for j in xrange(m):
                self.cumSum[i][j + 1] = self.cumSum[i][j] + matrix[i][j]

    def sumRegion(self, row1, col1, row2, col2):
        """
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        result = 0
        for i in xrange(row1, row2 + 1):
            result += (self.cumSum[i][col2 + 1] - self.cumSum[i][col1])
        return result


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

上面这种思路空间是O(mn)，时间是O(m)，取决于求和的query有几行，这道题在构建上和存储上已经无法再优了，但是在query函数上，我们还可以通过一个不同的方法达到O(1)时间复杂度，即我们建立一个矩阵，矩阵的元素是它对应下标相对于0，0坐标的累积和，这样的数组在查找某个范围的值时，我们可以通过对应的矩形面积之间的几个加减法完成O(1)操作，具体的话看LC的答案

class NumMatrix(object):

    def __init__(self, matrix):
        """
        :type matrix: List[List[int]]
        """
        n = len(matrix)
        if not n:
            return

        m = len(matrix[0])
        if not m:
            return 

        self.cumSum = [[0] * (m + 1) for _ in xrange(n + 1)]
        for i in xrange(1, n + 1):
            for j in xrange(1, m + 1):
                self.cumSum[i][j] = self.cumSum[i - 1][j] + self.cumSum[i][j - 1] + matrix[i - 1][j - 1] - self.cumSum[i - 1][j - 1]

    def sumRegion(self, row1, col1, row2, col2):
        """
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """ 
        return self.cumSum[row2 + 1][col2 + 1] - self.cumSum[row1][col2 + 1] - self.cumSum[row2 + 1][col1] + self.cumSum[row1][col1]


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