Range Sum Query 2D - Mutable

Range Sum Query 2D - Mutable

What is this problem about?

The Range Sum Query 2D - Mutable problem extends the immutable version by supporting point updates: after changing a matrix cell value, subsequent range sum queries should reflect the change. This requires a dynamic data structure beyond static prefix sums. The array, matrix, design, binary indexed tree, and segment tree interview pattern is the core.

Why is this asked in interviews?

Amazon, Google, and Bloomberg ask this because it tests dynamic 2D range query structures. The 2D Binary Indexed Tree (2D Fenwick Tree) supports O(log m × log n) both for point updates and range sum queries — significantly better than O(mn) prefix sum recomputation.

Algorithmic pattern used

2D Binary Indexed Tree (2D BIT). Maintain a 2D BIT. update(r, c, delta): propagate delta through the 2D BIT at position (r,c). query(r1,c1,r2,c2): use inclusion-exclusion with 4 BIT prefix queries. The BIT update propagates over multiple rows and columns using i += i & (-i).

Example explanation

Matrix initialized, BIT built. update(1,1,5): add 5 to position (1,1) in BIT. sumRegion(0,0,2,2) after update: uses 4 BIT queries: query(2,2) - query(-1,2) - query(2,-1) + query(-1,-1). Result reflects updated value.

Common mistakes candidates make

• Using immutable prefix sum (doesn't support updates efficiently).
• 2D BIT indexing errors (must be 1-indexed internally).
• Not updating the diff correctly (update(r,c,delta) where delta = new - old).
• Off-by-one in the 4-corner query.

Interview preparation tip

Range Sum Query 2D - Mutable demonstrates when static prefix sums fail and dynamic structures are needed. 2D BIT extends 1D BIT with an extra dimension: outer loop updates rows, inner loop updates columns. Practice 1D BIT thoroughly first, then extend to 2D. This structure also generalizes to segment trees — essential for competitive programming and systems design interviews.