Range Sum Query 2D Immutable — 2D Prefix Sum

Problem

Preprocess a 2D matrix for O(1) rectangle sum queries.

Approach — 2D Prefix Sum

pre[i][j] = sum of all cells in top-left rectangle to (i-1,j-1). Query (r1,c1,r2,c2) = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1].

Time: O(mn) build, O(1) query | Space: O(mn)

Solutions

Python

class NumMatrix:
    def __init__(self, matrix: list[list[int]]):
        m,n=len(matrix),len(matrix[0])
        self.pre=[[0]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                self.pre[i][j]=matrix[i-1][j-1]+self.pre[i-1][j]+self.pre[i][j-1]-self.pre[i-1][j-1]
    def sumRegion(self, r1, c1, r2, c2) -> int:
        return self.pre[r2+1][c2+1]-self.pre[r1][c2+1]-self.pre[r2+1][c1]+self.pre[r1][c1]

Complexity

Build: O(m*n) | Query: O(1)