Problem statement

https://leetcode.com/problems/range-sum-query-2d-immutable/

Solution

The idea of this problem is similar to what we have in Sum Query 1D. Let us define by self.dp[r+1][c+1] sum of all numbers in rectangle [0,r] x [0,c]. We need +1 here to deal with corner cases of empty rectangles. Then we can calculate all elements in dp table efficiently, using adjacent values. Also we can efficiently calculate sum in region now, similarly to 1D case.

Complexity

It is O(MN) time and space for initialization function and O(1) time and space for sumRegion function.

Code

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        M, N = len(matrix), len(matrix[0])
        self.dp = [[0] * (N+1) for _ in range(M+1)] 
        for c, r in product(range(N), range(M)):
            self.dp[r+1][c+1] = self.dp[r+1][c] + self.dp[r][c+1] - self.dp[r][c] + matrix[r][c]
    
    @lru_cache(None)
    def sumRegion(self, r1, c1, r2, c2):
        return self.dp[r2+1][c2+1] - self.dp[r1][c2+1] - self.dp[r2+1][c1] + self.dp[r1][c1]