Problem statement

https://binarysearch.com/problems/Range-Query-on-Two-Dimensional-List/

Solution

Equal to Leetcode 0304. Range Sum Query 2D - Immutable.

Complexity

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

Code

class RangeSumMatrix:
    def __init__(self, matrix):
        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 total(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]