Range Sum Query 2D - Immutable
Description
You are given a 2D integer matrix and need to handle multiple queries efficiently. Each query asks you to compute the sum of all elements inside a rectangular sub-region of the matrix, defined by an upper-left corner (row1, col1) and a lower-right corner (row2, col2).
You must implement a class with two methods:
- Constructor
NumMatrix(int[][] matrix)— Takes the 2D matrix as input and performs any necessary preprocessing. - Query
sumRegion(int row1, int col1, int row2, int col2)— Returns the sum of all elements within the rectangle from (row1, col1) to (row2, col2), inclusive.
The key challenge is that sumRegion must run in O(1) time complexity, meaning you cannot iterate over the sub-region for each query.
Examples
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]
]
sumRegion(2, 1, 4, 3)
Output: 8
Explanation: The rectangle from row 2 to row 4, column 1 to column 3 contains the values:
- Row 2: 2, 0, 1
- Row 3: 1, 0, 1
- Row 4: 0, 3, 0
Their sum is 2 + 0 + 1 + 1 + 0 + 1 + 0 + 3 + 0 = 8.
Example 2
Input:
sumRegion(1, 1, 2, 2)
Output: 11
Explanation: The rectangle from row 1 to row 2, column 1 to column 2 contains:
- Row 1: 6, 3
- Row 2: 2, 0
Their sum is 6 + 3 + 2 + 0 = 11.
Example 3
Input:
sumRegion(1, 2, 2, 4)
Output: 12
Explanation: The rectangle from row 1 to row 2, column 2 to column 4 contains:
- Row 1: 3, 2, 1
- Row 2: 0, 1, 5
Their sum is 3 + 2 + 1 + 0 + 1 + 5 = 12.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 ≤ m, n ≤ 200
- -10^4 ≤ matrix[i][j] ≤ 10^4
- 0 ≤ row1 ≤ row2 < m
- 0 ≤ col1 ≤ col2 < n
- At most 10^4 calls will be made to sumRegion
Editorial
Brute Force
Intuition
The most straightforward way to answer a region sum query is to simply iterate over every cell inside the rectangle and add up the values. When someone asks "what is the total of all numbers in this box?", you go cell by cell, row by row, and accumulate the sum.
Imagine you have a spreadsheet full of numbers and your boss asks "what is the total for this highlighted area?" Without any formulas, you would manually add each cell — that is exactly what this brute force approach does.
For the constructor, we just store the matrix. For each sumRegion call, we loop from row1 to row2 and col1 to col2, summing every element.
Step-by-Step Explanation
Let's trace through sumRegion(2, 1, 4, 3) on our matrix:
Step 1: Initialize sum = 0. We need to visit every cell in the rectangle from (2,1) to (4,3).
Step 2: Row 2, Col 1: matrix[2][1] = 2. sum = 0 + 2 = 2.
Step 3: Row 2, Col 2: matrix[2][2] = 0. sum = 2 + 0 = 2.
Step 4: Row 2, Col 3: matrix[2][3] = 1. sum = 2 + 1 = 3. Done with row 2.
Step 5: Row 3, Col 1: matrix[3][1] = 1. sum = 3 + 1 = 4.
Step 6: Row 3, Col 2: matrix[3][2] = 0. sum = 4 + 0 = 4.
Step 7: Row 3, Col 3: matrix[3][3] = 1. sum = 4 + 1 = 5. Done with row 3.
Step 8: Row 4, Col 1: matrix[4][1] = 0. sum = 5 + 0 = 5.
Step 9: Row 4, Col 2: matrix[4][2] = 3. sum = 5 + 3 = 8.
Step 10: Row 4, Col 3: matrix[4][3] = 0. sum = 8 + 0 = 8. Done with row 4.
Result: Return 8.
Brute Force — Iterating Over Every Cell in the Region — Watch how we visit each cell in the queried rectangle one by one, accumulating the sum as we go row by row.
Algorithm
- Constructor: Store the matrix as-is. No preprocessing needed.
- sumRegion(row1, col1, row2, col2):
- Initialize sum = 0
- For each row r from row1 to row2:
- For each column c from col1 to col2:
- Add matrix[r][c] to sum
- For each column c from col1 to col2:
- Return sum
Code
class NumMatrix {
private:
vector<vector<int>> matrix;
public:
NumMatrix(vector<vector<int>>& matrix) {
this->matrix = matrix;
}
int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int r = row1; r <= row2; r++) {
for (int c = col1; c <= col2; c++) {
sum += matrix[r][c];
}
}
return sum;
}
};class NumMatrix:
def __init__(self, matrix: list[list[int]]):
self.matrix = matrix
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
total = 0
for r in range(row1, row2 + 1):
for c in range(col1, col2 + 1):
total += self.matrix[r][c]
return totalclass NumMatrix {
private int[][] matrix;
public NumMatrix(int[][] matrix) {
this.matrix = matrix;
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int r = row1; r <= row2; r++) {
for (int c = col1; c <= col2; c++) {
sum += matrix[r][c];
}
}
return sum;
}
}Complexity Analysis
Time Complexity:
- Constructor: O(1) — we simply store a reference to the matrix.
- sumRegion: O(m × n) per query — in the worst case, the query covers the entire matrix, so we visit all m × n cells.
- Total for q queries: O(q × m × n).
Space Complexity: O(1) extra space beyond the input matrix itself (we just store a reference/copy).
Why This Approach Is Not Efficient
The brute force approach iterates over every cell in the queried rectangle for each call to sumRegion. With a matrix of size 200 × 200 and up to 10^4 queries, the worst case involves 200 × 200 × 10^4 = 4 × 10^8 operations. This is far too slow for typical time limits.
The fundamental problem is that we are recomputing the sum from scratch every single time. We don't remember anything from previous work. If two queries overlap, we re-add the same cells again.
The key insight is: since the matrix is immutable (it never changes), we can precompute some auxiliary data in the constructor that allows each query to be answered in constant time. This is the essence of the prefix sum technique.
Better Approach - Row Prefix Sums
Intuition
Before jumping to the full 2D prefix sum, there is an intermediate improvement: precompute a 1D prefix sum for each row.
Imagine each row of your spreadsheet already has a running total. If someone asks for the sum of columns 2 through 5 in row 3, you don't add the four cells — you just subtract two precomputed totals: total-up-to-column-5 minus total-up-to-column-1.
With row prefix sums, each query still needs to loop over the rows in the rectangle, but the column sum within each row becomes O(1). So instead of O(m × n) per query, we get O(m) per query — the height of the rectangle.
Step-by-Step Explanation
Preprocessing: Build prefix[r][c] = sum of matrix[r][0..c] for each row r.
For our matrix:
Row 0 prefix: [3, 3, 4, 8, 10]
Row 1 prefix: [5, 11, 14, 16, 17]
Row 2 prefix: [1, 3, 3, 4, 9]
Row 3 prefix: [4, 5, 5, 6, 13]
Row 4 prefix: [1, 1, 4, 4, 9]
Now for sumRegion(2, 1, 4, 3):
Step 1: Initialize sum = 0.
Step 2: Row 2: sum of columns 1 to 3 = prefix[2][3] - prefix[2][0] = 4 - 1 = 3. sum = 0 + 3 = 3.
Step 3: Row 3: sum of columns 1 to 3 = prefix[3][3] - prefix[3][0] = 6 - 4 = 2. sum = 3 + 2 = 5.
Step 4: Row 4: sum of columns 1 to 3 = prefix[4][3] - prefix[4][0] = 4 - 1 = 3. sum = 5 + 3 = 8.
Result: Return 8.
Row Prefix Sums — O(m) Per Query — Watch how row-wise prefix sums let us compute each row's contribution in O(1), reducing per-query work to just looping over the rows.
Algorithm
- Constructor: Build a prefix sum array for each row.
- For each row r, prefix[r][c] = matrix[r][0] + matrix[r][1] + ... + matrix[r][c]
- sumRegion(row1, col1, row2, col2):
- Initialize sum = 0
- For each row r from row1 to row2:
- row_sum = prefix[r][col2] - (col1 > 0 ? prefix[r][col1 - 1] : 0)
- sum += row_sum
- Return sum
Code
class NumMatrix {
private:
vector<vector<int>> prefix;
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
prefix.assign(m, vector<int>(n, 0));
for (int r = 0; r < m; r++) {
prefix[r][0] = matrix[r][0];
for (int c = 1; c < n; c++) {
prefix[r][c] = prefix[r][c - 1] + matrix[r][c];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int r = row1; r <= row2; r++) {
sum += prefix[r][col2];
if (col1 > 0) sum -= prefix[r][col1 - 1];
}
return sum;
}
};class NumMatrix:
def __init__(self, matrix: list[list[int]]):
m, n = len(matrix), len(matrix[0])
self.prefix = [[0] * n for _ in range(m)]
for r in range(m):
self.prefix[r][0] = matrix[r][0]
for c in range(1, n):
self.prefix[r][c] = self.prefix[r][c - 1] + matrix[r][c]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
total = 0
for r in range(row1, row2 + 1):
total += self.prefix[r][col2]
if col1 > 0:
total -= self.prefix[r][col1 - 1]
return totalclass NumMatrix {
private int[][] prefix;
public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
prefix = new int[m][n];
for (int r = 0; r < m; r++) {
prefix[r][0] = matrix[r][0];
for (int c = 1; c < n; c++) {
prefix[r][c] = prefix[r][c - 1] + matrix[r][c];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int r = row1; r <= row2; r++) {
sum += prefix[r][col2];
if (col1 > 0) sum -= prefix[r][col1 - 1];
}
return sum;
}
}Complexity Analysis
Time Complexity:
- Constructor: O(m × n) — we compute prefix sums for each of the m rows, each taking O(n) work.
- sumRegion: O(m) per query — we loop over at most m rows, but each row's contribution is computed in O(1) via prefix subtraction.
Space Complexity: O(m × n) — we store the prefix sum array, which has the same dimensions as the input matrix.
Why This Approach Is Not Efficient
Although the row prefix sum approach reduces per-query cost from O(m × n) to O(m), it still requires looping over every row in the rectangle. With m up to 200 and 10^4 queries, that is 2 × 10^6 operations — acceptable in practice, but the problem explicitly asks for O(1) query time.
The issue is that we only precomputed prefix sums in one dimension (horizontal). We still need to sum across rows vertically. The fix is to extend the prefix sum idea to two dimensions: precompute a 2D prefix sum table where each cell stores the cumulative sum of the entire rectangle from (0, 0) to (r, c). This way, any rectangular sub-region sum can be derived from just four lookups using the inclusion-exclusion principle.
Optimal Approach - 2D Prefix Sum
Intuition
The optimal approach extends the prefix sum concept to two dimensions. We build a 2D prefix sum matrix where each cell prefix[r][c] holds the sum of all elements in the rectangle from (0, 0) to (r-1, c-1) in the original matrix (using 1-based indexing for the prefix matrix to handle edge cases cleanly).
Think of it like a map showing the total rainfall from the top-left corner of a region down to any point. If you want the rainfall in a specific rectangular patch, you don't need to measure each square — you use the rainfall totals at the four corners of your patch and apply an inclusion-exclusion formula.
The formula to query any rectangle from (row1, col1) to (row2, col2) is:
sum = prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]
We subtract the region above and the region to the left, but since the top-left corner gets subtracted twice, we add it back once. This gives us the exact sum of the target rectangle in O(1) time.
Step-by-Step Explanation
Preprocessing — Building the 2D prefix sum matrix:
We use a (m+1) × (n+1) matrix with an extra row and column of zeros to avoid boundary checks.
Formula: prefix[r+1][c+1] = matrix[r][c] + prefix[r][c+1] + prefix[r+1][c] - prefix[r][c]
For our 5×5 matrix, the resulting prefix matrix (6×6, 1-indexed) is:
c0 c1 c2 c3 c4 c5
r0: [ 0, 0, 0, 0, 0, 0]
r1: [ 0, 3, 3, 4, 8, 10]
r2: [ 0, 8, 14, 18, 24, 27]
r3: [ 0, 9, 17, 21, 28, 36]
r4: [ 0, 13, 22, 26, 34, 49]
r5: [ 0, 14, 23, 30, 38, 58]
Querying sumRegion(2, 1, 4, 3):
Step 1: Identify the four corner values in the prefix matrix:
- Total rectangle: prefix[5][4] = 38
- Top strip to remove: prefix[2][4] = 24
- Left strip to remove: prefix[5][1] = 14
- Over-subtracted corner: prefix[2][1] = 8
Step 2: Apply the inclusion-exclusion formula:
- sum = 38 - 24 - 14 + 8 = 8
Step 3: Return 8. Just four lookups and three arithmetic operations — O(1)!
2D Prefix Sum — O(1) Query via Inclusion-Exclusion — Watch how we build the 2D prefix sum table during preprocessing, then answer any rectangle sum query with just four lookups.
Algorithm
-
Constructor — Build 2D Prefix Sum Table:
- Create a (m+1) × (n+1) matrix
prefixinitialized to zeros (extra row/column for boundary handling) - For each cell (r, c) in the original matrix:
- prefix[r+1][c+1] = matrix[r][c] + prefix[r][c+1] + prefix[r+1][c] - prefix[r][c]
- Create a (m+1) × (n+1) matrix
-
sumRegion(row1, col1, row2, col2) — O(1) Query:
- Return prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]
Code
class NumMatrix {
private:
vector<vector<int>> prefix;
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
prefix.assign(m + 1, 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];
}
};class NumMatrix:
def __init__(self, matrix: list[list[int]]):
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]
)class NumMatrix {
private int[][] prefix;
public NumMatrix(int[][] matrix) {
int m = matrix.length, 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];
}
}Complexity Analysis
Time Complexity:
- Constructor: O(m × n) — we iterate over every cell once to build the prefix sum table. Each cell computation involves three lookups and three additions, all O(1).
- sumRegion: O(1) — every query uses exactly four lookups and three arithmetic operations, regardless of the rectangle size.
With q queries, the total time is O(m × n + q), which is optimal.
Space Complexity: O(m × n) — the prefix sum table has dimensions (m+1) × (n+1). In practice this is the same order as the input matrix.