Skip to main content

304. Range Sum Query 2D - Immutable

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

Python​

Query in runtime​

from functools import cache

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.matrix = matrix

    @cache
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        total = 0
        for row in range(row1, row2+1):
            total += sum(self.matrix[row][col1:col2+1])
        return total

Cache on built​

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])

        cache = [[0]*(n+1) for i in range(m+1)]
        for row in range(m):
            for col in range(n):
                cache[row+1][col+1] = \
                cache[row+1][col] + cache[row][col+1] + matrix[row][col] - cache[row][col]
        self.cache = cache


    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        cache = self.cache
        return cache[row2+1][col2+1] - cache[row1][col2+1] - cache[row2+1][col1] + cache[row1][col1]