DSA problem
Range Sum Query 2D - Mutable
Given a 2D matrix matrix, handle queries that update a single cell and queries that return the sum of all elements inside an axis-aligned rectangle. Implement the NumMatrix class with update(row, col, val) and sumRegion(row1, col1, row2, col2) where the rectangle is inclusive on both corners.
The static (immutable) version of this problem precomputes a 2D prefix-sum table once for O(1) queries. That breaks down here because each update would force an O(rows * cols) refresh of the table — far too slow when many updates are interleaved with queries.
The natural generalization is a 2D Binary Indexed Tree. The key observation: a 1D Fenwick tree supports prefix sums; nesting one Fenwick tree per row index inside another Fenwick tree along the column axis yields a structure where any rectangle prefix sum from (0, 0) to (r, c) is computed in O(log m * log n). The bit-manipulation walks are identical to 1D — just performed independently on each axis.
update(r, c, val) translates to a delta point-add on the 2D BIT. sumRegion(r1, c1, r2, c2) is built by inclusion-exclusion of four prefix rectangles: P(r2, c2) - P(r1 - 1, c2) - P(r2, c1 - 1) + P(r1 - 1, c1 - 1). Per call, both run in O(log m * log n) using O(m * n) extra space.
Examples
["NumMatrix","sumRegion","update","sumRegion"]
[[[[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]]],[2,1,4,3],[3,2,2],[2,1,4,3]][null,8,null,10]["NumMatrix","sumRegion","update","update","sumRegion"]
[[[[1,2],[3,4]]],[0,0,1,1],[0,0,5],[1,1,0],[0,0,1,1]][null,10,null,null,10]["NumMatrix","sumRegion"]
[[[[5]]],[0,0,0,0]][null,5]Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- -10^5 <= matrix[i][j] <= 10^5
- 0 <= row < m and 0 <= col < n
- -10^5 <= val <= 10^5
- 0 <= row1 <= row2 < m and 0 <= col1 <= col2 < n
- At most 5000 calls will be made to update and sumRegion.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.