Range Sum Query 2D - Immutable — Editorial

Opening the reading…

Intuitionturning a rectangle into four overlapping regions

A query asks for every value inside one rectangle, but neighbouring queries usually overlap heavily. Recomputing those cells for every call repeats the same additions. Instead, store the sum of the rectangle from the matrix's top-left corner to each possible bottom-right corner. Once those sums exist, a query can recover its rectangle by subtracting away the parts above and to the left.

The prefix table uses one extra row and one extra column of zeroes. Prefix[i][j] then means the sum of matrix rows 0 to i - 1 and columns 0 to j - 1, so its coordinates describe an exclusive bottom and right boundary. For a query, the large top-left rectangle contains the answer plus an upper strip and a left strip. Subtract both strips, then add their overlap back because it was subtracted twice.

Approach

Create a prefix table with dimensions m + 1 by n + 1 and fill it with zeroes, because the extra boundaries let every query use the same formula even when row1 or col1 is zero.

For each matrix cell at row i - 1 and column j - 1, compute prefix[i][j] from the prefix above, the prefix to the left, and the diagonally shared prefix, then add the current value; subtracting the diagonal prevents that overlap from being counted twice.

Translate the inclusive query corners into padded exclusive boundaries, using row2 + 1 and col2 + 1 for the lower and right edges; without this shift, the bottom row or rightmost column is omitted.

Start with prefix[row2+1][col2+1], the sum from the matrix origin through the query's bottom-right corner, because it contains the target plus the two unwanted strips.

Subtract prefix[row1][col2+1] and prefix[row2+1][col1], removing the rows above the target and the columns to its left; these are exactly the regions outside the target but inside the large prefix rectangle.

Add prefix[row1][col1] once, because the upper-left overlap belongs to both removed strips and was therefore subtracted twice; return the resulting value without scanning any matrix cells.

Complexitythe preprocessing cost is paid once

MEASURE	BOUND	WHY
Time	O(mn) preprocessing and O(1) per query	The table visits each of the m x n matrix cells once, and each query performs four indexed reads and constant arithmetic. No cell is revisited during preprocessing, and the query does not scan the rectangle, so its cost does not grow with the rectangle's area. In the largest allowed shape, 200 x 200, preprocessing still visits only 40,000 cells.
Space	O(mn) extra space	The prefix table stores one number for each of the (m + 1) x (n + 1) padded positions. The returned sum is required output and is excluded from the extra-space bound. This remains O(mn) for every rectangular shape; the worst allowed shape is 200 x 200, where the table has 40,401 entries.

Here m is the number of matrix rows and n is the number of matrix columns.

Annotated solutionC++ · padded prefix table · reusable across calls

CPPBuild the padded prefix table on the first call, then answer each rectangle with inclusion-exclusion.

#include <vector>
using namespace std;

class Solution {
private:
    vector<vector<int>> pref;

public:
    int sumRegion(vector<vector<int>>& matrix, int row1, int col1, int row2, int col2) {
        if (pref.empty()) {
            int m = static_cast<int>(matrix.size());
            int n = static_cast<int>(matrix[0].size());
            pref.assign(m + 1, vector<int>(n + 1, 0));

            for (int i = 1; i <= m; ++i) {
                for (int j = 1; j <= n; ++j) {
                    pref[i][j] = pref[i - 1][j]
                               + pref[i][j - 1]
                               - pref[i - 1][j - 1]
                               + matrix[i - 1][j - 1];
                }
            }
        }

        return pref[row2 + 1][col2 + 1]
             - pref[row1][col2 + 1]
             - pref[row2 + 1][col1]
             + pref[row1][col1];
    }
};

The two index shifts are the part worth memorising. A query's bottom-right cell is at matrix[row2][col2], but the prefix table boundary after that cell is row2 + 1 and col2 + 1. The upper and left boundaries are row1 and col1. Because the table is padded, those boundaries can be zero without a special case, which keeps the return expression identical for every valid query.