Range Sum Query 2D - Immutable

How it works

We can extend prefix sums to two dimensions. The idea is to precompute sumMat[r][c] as the sum of all elements in the rectangle from (0, 0) to (r - 1, c - 1). To find the sum of any rectangular region, we use the inclusion-exclusion principle: take the sum up to the bottom-right corner, subtract the regions above and to the left, then add back the top-left corner (which was subtracted twice).

Steps

1. Create a prefix sum matrix sumMat of size (ROWS + 1) x (COLS + 1) initialized to zero.
2. Build the prefix sum matrix:
   • For each row r, maintain a running prefix sum across columns.
   • Set sumMat[r + 1][c + 1] = prefix + sumMat[r][c + 1].
3. For each sumRegion(row1, col1, row2, col2) query:
   • Compute bottomRight = sumMat[row2 + 1][col2 + 1].
   • Subtract above = sumMat[row1][col2 + 1].
   • Subtract left = sumMat[row2 + 1][col1].
   • Add back topLeft = sumMat[row1][col1].
4. Return bottomRight - above - left + topLeft.

Complexity

• Time complexity: O(1) for each query.
• Space complexity: O(m * n)

Where m is the number of rows and n is the number of columns in the matrix.

Things to watch for

Forgetting the Inclusion-Exclusion Principle

When computing the sum of a rectangular region using 2D prefix sums, you must subtract the regions above and to the left, then add back the top-left corner that was subtracted twice. The formula is bottomRight - above - left + topLeft. Forgetting to add back the top-left corner results in under-counting, while forgetting to subtract either the above or left region causes over-counting.

Off-by-One Errors with Prefix Sum Indices

The prefix sum matrix is typically sized (rows + 1) x (cols + 1) to handle edge cases where the query starts at row 0 or column 0. Mixing up whether indices are 0-based or 1-based leads to accessing wrong cells or out-of-bounds errors. When querying sumRegion(row1, col1, row2, col2), remember to shift indices appropriately when accessing the prefix sum matrix.

Building Prefix Sum Matrix Incorrectly

The 2D prefix sum at position (r, c) should represent the sum of all elements from (0, 0) to (r-1, c-1). A common mistake is computing prefix sums row by row without properly incorporating the contribution from previous rows. The correct formula is prefix[r+1][c+1] = matrix[r][c] + prefix[r][c+1] + prefix[r+1][c] - prefix[r][c], or equivalently, accumulate row prefix and add the cell directly above.

class NumMatrix:

    def __init__(self, matrix: list[list[int]]):
        ROWS, COLS = len(matrix), len(matrix[0])
        self.sumMat = [[0] * (COLS + 1) for _ in range(ROWS + 1)]

        for r in range(ROWS):
            prefix = 0
            for c in range(COLS):
                prefix += matrix[r][c]
                above = self.sumMat[r][c + 1]
                self.sumMat[r + 1][c + 1] = prefix + above

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        row1, col1, row2, col2 = row1 + 1, col1 + 1, row2 + 1, col2 + 1
        bottomRight = self.sumMat[row2][col2]
        above = self.sumMat[row1 - 1][col2]
        left = self.sumMat[row2][col1 - 1]
        topLeft = self.sumMat[row1 - 1][col1 - 1]
        return bottomRight - above - left + topLeft

class NumMatrix {
private:
    vector<vector<int>> sumMat;

public:
    NumMatrix(vector<vector<int>>& matrix) {
        int ROWS = matrix.size(), COLS = matrix[0].size();
        sumMat = vector<vector<int>>(ROWS + 1, vector<int>(COLS + 1, 0));

        for (int r = 0; r < ROWS; r++) {
            int prefix = 0;
            for (int c = 0; c < COLS; c++) {
                prefix += matrix[r][c];
                int above = sumMat[r][c + 1];
                sumMat[r + 1][c + 1] = prefix + above;
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        row1++; col1++; row2++; col2++;
        int bottomRight = sumMat[row2][col2];
        int above = sumMat[row1 - 1][col2];
        int left = sumMat[row2][col1 - 1];
        int topLeft = sumMat[row1 - 1][col1 - 1];
        return bottomRight - above - left + topLeft;
    }
};