@@ -0,0 +1,1480 @@
+%22%22%22%0AIdea: on instantiation, save a matrix where each cell has the sum%0Aof the rectangle starting at the top left corner and ending at%0Athe equivalent cell in the original matrix.%0AOn query, calculate the arbitrary rectangle sum based on that sum-from-top-left%0Aminus the sum of the rectangle above it and the rectangle to the left,%0Aplus the rectangle above and to the left to account for double subtraction.%0AComplexity: O(m*n) space, O(m*n) initialization and O(1) for subsequent queries%0A%22%22%22%0A%0Aclass NumMatrix:%0A%0A    def __init__(self, matrix: List%5BList%5Bint%5D%5D):%0A        self.sumFromCorner = %5B%5D%0A        m = len(matrix)%0A        n = len(matrix%5B0%5D)%0A        for i in range(m):%0A            row = n*%5B0%5D%0A            runningRowSum = 0%0A            for j in range(n):%0A                runningRowSum += matrix%5Bi%5D%5Bj%5D%0A                row%5Bj%5D = (self.sumFromCorner%5Bi-1%5D%5Bj%5D if i %3E 0 else 0) + runningRowSum%0A            self.sumFromCorner.append(row)%0A%0A    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -%3E int:%0A        topRectSum = self.sumFromCorner%5Brow1 - 1%5D%5Bcol2%5D if row1 %3E 0 else 0%0A        leftRectSum = self.sumFromCorner%5Brow2%5D%5Bcol1 - 1%5D if col1 %3E 0 else 0%0A        topLeftRectSum = self.sumFromCorner%5Brow1 - 1%5D%5Bcol1 - 1%5D if row1 %3E 0 and col1 %3E 0 else 0%0A        return self.sumFromCorner%5Brow2%5D%5Bcol2%5D - leftRectSum - topRectSum + topLeftRectSum%0A%0A%0A# Your NumMatrix object will be instantiated and called as such:%0A# obj = NumMatrix(matrix)%0A# param_1 = obj.sumRegion(row1,col1,row2,col2)%0A

304. Range Sum Query 2D - Immutable