Range Sum Query 2D Immutable

Problem Description

Given a 2D matrix matrix, handle multiple queries of the following type:

• Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

• NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
• int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

You must design an algorithm where sumRegion works in O(1) time complexity.

Examples

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -10⁴ <= matrix[i][j] <= 10⁴
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• At most 10⁴ calls will be made to sumRegion.

2D Prefix Sum Precomputation

To answer region sum queries in O(1) time, we precompute a 2D prefix sum array where prefix[i][j] represents the sum of the submatrix from (0,0) to (i-1, j-1). We can populate this using DP: prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]. When querying a region from (row1, col1) to (row2, col2), we use inclusion-exclusion principle: Sum = prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1].

Solution 1: 2D Prefix Sum Cache

Precompute submatrix accumulations to resolve region queries in O(1) time.

class NumMatrix {
    private int[][] prefix;

    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
        int m = matrix.length;
        int n = matrix[0].length;
        prefix = new int[m + 1][n + 1];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                prefix[r + 1][c + 1] = matrix[r][c] 
                                     + prefix[r][c + 1] 
                                     + prefix[r + 1][c] 
                                     - prefix[r][c];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return prefix[row2 + 1][col2 + 1] 
             - prefix[row1][col2 + 1] 
             - prefix[row2 + 1][col1] 
             + prefix[row1][col1];
    }
}

class NumMatrix:
    def __init__(self, matrix: list[list[int]]):
        if not matrix or not matrix[0]:
            return
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
        for r in range(m):
            for c in range(n):
                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])

#include <vector>

class NumMatrix {
private:
    std::vector<std::vector<int>> prefix;

public:
    NumMatrix(std::vector<std::vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int m = matrix.size();
        int n = matrix[0].size();
        prefix.assign(m + 1, std::vector<int>(n + 1, 0));
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                prefix[r + 1][c + 1] = matrix[r][c] 
                                     + prefix[r][c + 1] 
                                     + prefix[r + 1][c] 
                                     - prefix[r][c];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return prefix[row2 + 1][col2 + 1] 
             - prefix[row1][col2 + 1] 
             - prefix[row2 + 1][col1] 
             + prefix[row1][col1];
    }
};

Complexity Analysis

• Time Complexity: Constructor takes O(m * n) to compute prefix sums. Query sumRegion takes O(1) time.
• Space Complexity: O(m * n) auxiliary space to store the prefix sum matrix.

Where It Breaks

This solution is designed for immutable matrices. If elements can be updated dynamically (e.g. Range Sum Query 2D Mutable), updating the prefix sum array takes O(m * n) in the worst case. Under those conditions, a 2D Segment Tree or 2D Binary Indexed Tree (Fenwick Tree) is required.

Common Mistakes

• Incorrect indices in inclusion-exclusion formula: Off-by-one errors when subtracting adjacent cells. Offset rows and columns by using + 1 consistently to simplify index logic.
• Integer overflow: Adding large values inside the matrix could overflow standard 32-bit integers, though bounded by constraints in this problem.

Frequently Asked Questions

Why does the prefix sum matrix have size (m + 1) x (n + 1)? An extra row and column of zeros removes the need to write boundary check conditions for row1 == 0 or col1 == 0.

Can this algorithm be optimized for space? No. Since we need to represent all regions starting from (0,0), we must store the full prefix grid to enable O(1) queries.

← All Problems