Given an integer matrix that is never modified, answer a batch of 2D range-sum queries. Each query is [r1, c1, r2, c2] (0-based) and asks for the sum of every element inside the rectangle whose top-left corner is (r1, c1) and bottom-right corner is (r2, c2), inclusive of all four edges.
Return an array whose k-th entry is the answer to the k-th query. Because the matrix is immutable, precompute a 2D prefix-sum table once and answer every query in constant time.
Example
Rectangle (2,1)-(4,3) sums to 8; rectangle (1,1)-(2,2) sums to 6+3+2+0 = 11.
Constraints
- 0 <= matrix.length, matrix[0].length <= 200
- -10^5 <= matrix[r][c] <= 10^5
- 0 <= queries.length <= 10^4
- 0 <= r1 <= r2 < matrix.length and 0 <= c1 <= c2 < matrix[0].length
Intuition
The most direct approach answers each rectangle query by scanning it: loop over every row from r1 to r2 and every column from c1 to c2, summing the cells inside. Correct, but a large rectangle is re-summed in full for every query.
function rangeSum2D(matrix, queries) {
// For each query, add up every cell inside its rectangle.
return queries.map(([r1, c1, r2, c2]) => {
let total = 0;
for (let r = r1; r <= r2; r++) {
for (let c = c1; c <= c2; c++) {
total += matrix[r][c]; // inclusive of all four edges
}
}
return total;
});
}Each query is O(m·n); with many queries this re-sums the same overlapping regions. Can we do better?
Lift the 1D Prefix sums idea one dimension. Build a table pre where pre[r+1][c+1] is the sum of the whole rectangle from the origin (0, 0) to (r, c). Each entry folds in the cell, the rectangle above, and the rectangle to the left, then subtracts their doubly-counted overlap: pre[r+1][c+1] = matrix[r][c] + pre[r][c+1] + pre[r+1][c] − pre[r][c].
Once that O(m·n) table exists, any sub-rectangle is read off its four corners by inclusion–exclusion: the big rectangle to the bottom-right corner, minus the strip above it, minus the strip to its left, plus the top-left corner added back (it was subtracted twice). The padding row and column of zeros remove every boundary check.
Walking the table build, then a query, over the board:
Build starts top-left. With the zero padding row/column, the first cell just copies its value.
Each cell = its value + rectangle above (sum 3) + rectangle left (sum 8) − the overlap counted twice (3).
Bottom-right of the table holds the whole grid's sum, 21. The full O(m·n) table is now built.
Read the 2×2 bottom-right rectangle by four corners: whole(21) − above strip(4) − left strip(9) + top-left(3) = 11 = 6+3+2+0.
Optimization
2D prefix-sum table
Build a prefix-sum table pre with an extra zero row and column, where pre[r + 1][c + 1] is the sum of every cell in the rectangle from (0, 0) to (r, c). Each entry is the cell plus the rectangle above plus the rectangle to the left, minus the rectangle counted twice in their overlap:
pre[r+1][c+1] = matrix[r][c] + pre[r][c+1] + pre[r+1][c] - pre[r][c].
A query (r1, c1, r2, c2) then reads off four corners by inclusion–exclusion: the big rectangle, minus the strip above, minus the strip to the left, plus the top-left corner added back once:
pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1].
Building the table is O(m·n); every query is O(1), so the batch is O(m·n + q).
function rangeSum2D(matrix, queries) {
const rows = matrix.length;
const cols = rows ? matrix[0].length : 0;
// pre[r+1][c+1] = sum of the rectangle from (0,0) to (r,c); the extra
// zero row/column removes the boundary checks when subtracting strips.
const pre = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
// cell + rectangle above + rectangle left - the overlap counted twice.
pre[r + 1][c + 1] = matrix[r][c] + pre[r][c + 1] + pre[r + 1][c] - pre[r][c];
}
}
// Inclusion-exclusion off the four corners of each query rectangle.
return queries.map(([r1, c1, r2, c2]) =>
pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1]);
}Complexity analysis
Time complexity: O(m·n + q). Here's why:
- Building the 2D prefix table touches every cell once — O(m·n).
- Each of the
qqueries reads four table entries and combines them — O(1) apiece, O(q) total.
So the batch is O(m·n) + O(q) = O(m·n + q), versus the brute force's O(m·n) per query. The table build is amortized across every query.
Space complexity: O(m·n). Here's why:
- The prefix table is
(m + 1) × (n + 1)— one extra padding row and column — so O(m·n).
Not counting the per-query output array, the dominant extra space is the table itself, O(m·n).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| matrix = 7 0000 | [7] | Single cell — the only rectangle is that cell. |
| matrix = 23 45 0011 | [14] | Whole 2×2 matrix — the full sum (2+3+4+5). |
| matrix = 123 456 0112 | [16] | A 2×2 sub-rectangle: 2+3+5+6. |
| matrix = -1-2 -3-4 0011 1111 | [-10,-4] | All-negative; whole matrix then a single cell. |
| matrix = 20 02 0001 0111 | [2,2] | Row strip then column strip off the same table. |
Try it yourself
Write your solution against the real judge before checking the reference.