Range Sum Query 2D – Immutable
Problem
Given a fixed matrix, answer many queries sumRegion(r1, c1, r2, c2) — the sum of the rectangle with top-left (r1, c1) and bottom-right (r2, c2) — each in O(1).
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
Test cases
Case 1
Input: 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]]) .sumRegion(2, 1, 4, 3) .sumRegion(1, 1, 2, 2) .sumRegion(1, 2, 2, 4) Expected: [8,11,12]
Case 2
Input: new NumMatrix([[1,2],[3,4]]) .sumRegion(0, 0, 1, 1) .sumRegion(0, 1, 1, 1) .sumRegion(1, 0, 1, 0) Expected: [10,6,3]
Case 3
Input: new NumMatrix([[7]]) .sumRegion(0, 0, 0, 0) Expected: [7]
View solutionHide solution1 approach
1. 2-D prefix sums (inclusion–exclusion)
Time O(R·C) build, O(1) per querySpace O(R·C)
P[r+1][c+1] = sum of the rectangle (0,0)..(r,c). A query adds the big rectangle, subtracts the strips above and left, and adds back the doubly-removed corner.
class NumMatrix { constructor(m) { const R = m.length, C = m[0].length; this.P = Array.from({ length: R + 1 }, () => new Array(C + 1).fill(0)); for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) this.P[r + 1][c + 1] = m[r][c] + this.P[r][c + 1] + this.P[r + 1][c] - this.P[r][c]; } sumRegion(r1, c1, r2, c2) { const P = this.P; return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]; }}