Range Sum Query 2D - Immutable Visualizer & Step-by-Step Algorithm Solution

Precompute a 2D prefix sum matrix in O(m · n) time to evaluate any submatrix sum query in O(1) time using the 2D Inclusion-Exclusion Principle.

Category: arrays | Difficulty: Medium

Tags: Prefix Sum, Matrix, Design, Inclusion-Exclusion

Range Sum Query 2D - Immutable

Input Matrix (3x4)
0
1
2
3
0
1
2
3
0
1
4
5
6
3
2
1
2
0
1
Prefix Matrix (4x5) · Initial
0
1
2
3
4
0
1
2
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Active Cell
Active Row / Col / Box
Conflict / Subtracted
Highlighted / Subgrid
100%
state
m3
n4
queriesCount2
Constructor
1/29
Explanation

Constructing NumMatrix instance for 3x4 input matrix. Initializing 2D prefix sum table to enable O(1) submatrix sum queries.

Source Code
1class NumMatrix {
2 private prefixMatrix: number[][];
3 private m: number;
4 private n: number;
5 constructor(matrix: number[][]) {
6 this.m = matrix.length;
7 this.n = matrix[0].length;
8 this.prefixMatrix = Array.from({ length: this.m + 1 }, () =>
9 new Array(this.n + 1).fill(0)
10 );
11 for (let r = 1; r <= this.m; r++) {
12 for (let c = 1; c <= this.n; c++) {
13 this.prefixMatrix[r][c] =
14 matrix[r - 1][c - 1] +
15 this.prefixMatrix[r - 1][c] +
16 this.prefixMatrix[r][c - 1] -
17 this.prefixMatrix[r - 1][c - 1];
18 }
19 }
20 }
21
22 sumRegion(row1: number, col1: number, row2: number, col2: number): number {
23 return (
24 this.prefixMatrix[row2 + 1][col2 + 1] -
25 this.prefixMatrix[row1][col2 + 1] -
26 this.prefixMatrix[row2 + 1][col1] +
27 this.prefixMatrix[row1][col1]
28 );
29 }
30}