Range Sum Query 2D - Immutable

Range Sum Query 2D - Immutable

What is this problem about?

The Range Sum Query 2D - Immutable problem asks you to design a class for a 2D matrix supporting multiple sum queries: given a rectangle (r1,c1) to (r2,c2), return the sum of all elements in that submatrix. This coding problem uses 2D prefix sums for O(1) query time after O(mn) preprocessing. The array, matrix, design, and prefix sum interview pattern is the core.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, Bloomberg, and many others ask this because 2D prefix sums are the foundation for all 2D range query problems. It validates understanding of 2D inclusion-exclusion for submatrix sum computation.

Algorithmic pattern used

2D prefix sum. Build prefix[i][j] = sum of all elements in the rectangle (0,0) to (i-1,j-1). Recurrence: prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]. Query (r1,c1,r2,c2): prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1].

Example explanation

Matrix:

3 0 1
5 6 3
1 2 0

prefix[2][2] = 3+0+5+6 = 14. Query (0,0,1,1) = prefix[2][2] - prefix[0][2] - prefix[2][0] + prefix[0][0] = 14-0-0+0 = 14 ✓ (3+0+5+6).

Common mistakes candidates make

• Wrong inclusion-exclusion formula (must add back prefix[r1][c1]).
• Off-by-one: prefix is (m+1)×(n+1) sized.
• Using 0-indexed matrix but 1-indexed prefix (or vice versa).
• Not precomputing prefix on initialization.

Interview preparation tip

2D prefix sums are fundamental for grid problems. Memorize the four-corner formula: sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]. Build this prefix array fluently — it appears in dozens of problems including submatrix sum, count submatrices with target sum, and 2D sliding window maximum. Practice deriving the formula from the inclusion-exclusion principle.