Range Sum Query 2D - Immutable

Updated on 03 July, 2025
Range Sum Query 2D - Immutable header image

Problem Statement

In this task, you're given a 2D integer matrix and need to design a class, NumMatrix, capable of handling multiple queries to calculate the sum of a submatrix. The submatrix is defined by two corners: an upper left corner (row1, col1) and a lower right corner (row2, col2). Each query must return the sum of the matrix values within these bounds efficiently.

Key functionalities to implement in the NumMatrix class include:

  • NumMatrix(int[][] matrix) – Initializes the object with the entire matrix, setting up any required pre-computed structures to answer the sum queries efficiently.
  • int sumRegion(int row1, int col1, int row2, int col2) – After initialization, this method should efficiently compute and return the sum of the submatrix defined by the corners.

Examples

Example 1

Input:

["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[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]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]

Output:

[null, 8, 11, 12]

Explanation:

NumMatrix numMatrix = new NumMatrix([
  [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]
]);

numMatrix.sumRegion(2, 1, 4, 3); // return 8
numMatrix.sumRegion(1, 1, 2, 2); // return 11
numMatrix.sumRegion(1, 2, 2, 4); // return 12

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.

Approach and Intuition

To meet the constraint of answering each sumRegion query in O(1) time, we precompute a 2D prefix sum matrix during initialization.

1. Build the Prefix Sum Matrix

Let prefixSum[i][j] be the sum of all values in the submatrix from (0, 0) to (i, j) inclusive. Compute it using:

markdown
prefixSum[i][j] = matrix[i][j]
                + (i > 0 ? prefixSum[i-1][j] : 0)
                + (j > 0 ? prefixSum[i][j-1] : 0)
                - (i > 0 && j > 0 ? prefixSum[i-1][j-1] : 0)

This equation adds the current cell’s value, the row and column contributions, and removes the overlapping region.

2. Answering a sumRegion Query

To get the sum of a submatrix from (row1, col1) to (row2, col2), use:

markdown
sumRegion(row1, col1, row2, col2) = prefixSum[row2][col2]
                                 - (row1 > 0 ? prefixSum[row1-1][col2] : 0)
                                 - (col1 > 0 ? prefixSum[row2][col1-1] : 0)
                                 + (row1 > 0 && col1 > 0 ? prefixSum[row1-1][col1-1] : 0)

This subtracts the areas above and to the left of the desired submatrix and re-adds the overlapping top-left corner that was subtracted twice.

Summary

  • Initialization: O(m × n) – builds the prefix sum matrix.
  • Each sumRegion call: O(1) – constant-time lookup using precomputed values.
  • Space Complexity: O(m × n) – additional memory for the prefix sum matrix.

This ensures maximum efficiency even with a high number of sum queries.

Solutions

  • Java
java
class MatrixSumQuery {
    private int[][] sumMatrix;
    
    public MatrixSumQuery(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        sumMatrix = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                sumMatrix[i + 1][j + 1] = sumMatrix[i + 1][j] + sumMatrix[i][j + 1] + matrix[i][j] - sumMatrix[i][j];
            }
        }
    }
    
    public int computeSum(int r1, int c1, int r2, int c2) {
        return sumMatrix[r2 + 1][c2 + 1] - sumMatrix[r1][c2 + 1] - sumMatrix[r2 + 1][c1] + sumMatrix[r1][c1];
    }
}

This Java solution addresses the problem of efficiently querying the sum of subregions within a 2D matrix. The class MatrixSumQuery uses an advanced data structure to preprocess the input matrix to allow fast sum queries.

  • At initialization (MatrixSumQuery constructor):

    1. Check if the input matrix is non-empty.
    2. Create an auxiliary matrix, sumMatrix, with dimensions larger by one in both directions compared to the input matrix. This extra room facilitates easier calculation of subregion sums, particularly on the borders.
    3. Populate sumMatrix using a dynamic programming approach. Each entry at sumMatrix[i + 1][j + 1] is calculated to store the sum of elements from the top-left corner (0,0) to the current element (i,j) in the original matrix. The formular used is sumMatrix[i + 1][j + 1] = sumMatrix[i + 1][j] + sumMatrix[i][j + 1] + matrix[i][j] - sumMatrix[i][j].
  • To compute the sum of any sub-matrix from (r1, c1) to (r2, c2):

    1. Apply the precomputed results in sumMatrix observing the inclusion-exclusion principle. The formula used here, sumMatrix[r2 + 1][c2 + 1] - sumMatrix[r1][c2 + 1] - sumMatrix[r2 + 1][c1] + sumMatrix[r1][c1], specifically accounts for area overlaps and right, bottom exclusions due to the initial adjustment in matrix size.

This compact solution ensures that after the O(n*m) preprocessing time, where n and m are the dimensions of the matrix, any sum query can be answered in constant time O(1) making it highly efficient for scenarios with many sum queries to the same matrix.

Comments

No comments yet.