Range Sum Query 2D - Immutable

Prefix Sum

20 min

Problem Statement

Given a 2D matrix, handle multiple queries of the following type: Calculate the sum of the elements of the matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example

Example 1:

Input: matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]], queries = [[2,1,4,3],[1,1,2,2],[1,2,2,4]]

matrix: ...

queries: [[2,1,4,3],[1,1,2,2],[1,2,2,4]]

Output: [8, 11, 12]

Solution

We can precompute a 2D prefix sum array (or matrix) to answer each query in O(1) time. The value `prefix[r][c]` will store the sum of all elements in the rectangle from (0,0) to (r,c).

Algorithm Steps

Create a prefix sum matrix of size (rows+1) x (cols+1).
Populate the prefix sum matrix using the formula: `prefix[r][c] = matrix[r-1][c-1] + prefix[r-1][c] + prefix[r][c-1] - prefix[r-1][c-1]`.
For each query, calculate the sum using the prefix sum matrix in O(1) time.

Range Sum Query 2D - Immutable

2D Prefix Sum Approach

Query: []

Sum: 0

Progress1 / 1

Ready to start the visualization

Prefix Sum Matrix

Range Sum Query 2D - Immutable Solution


class NumMatrix:
    def __init__(self, matrix: list[list[int]]):
        if not matrix or not matrix[0]:
            return
        rows, cols = len(matrix), len(matrix[0])
        self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
        for r in range(rows):
            for c in range(cols):
                self.prefix[r+1][c+1] = matrix[r][c] + self.prefix[r][c+1] + self.prefix[r+1][c] - self.prefix[r][c]

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