Range Sum Query 2D – Immutable

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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];
}
}