Range Sum Query 2D - Mutable
Hard · Matrix · Array · Design · Binary Indexed Tree · Segment Tree · Matrix
Problem
Design a class over a 2D integer matrix that supports point updates and rectangle-sum queries, called in any order.
- NumMatrix(matrix) stores the matrix.
- update(row, col, val) sets matrix[row][col] to val.
- sumRegion(row1, col1, row2, col2) returns the sum of the rectangle with top-left corner (row1, col1) and bottom-right corner (row2, col2), both inclusive, reflecting every update so far.
A plain prefix-sum table makes each update expensive, and summing cells makes each query expensive. Aim for sub-linear time for both operations.
The tests call the class through a list of operation names and a list of their arguments; the expected output lists each call's return value, None for the constructor and update.
Examples
Input: ops = ["NumMatrix","sumRegion","update","sumRegion"], args = [[[[2,0,1],[4,3,5],[1,6,2]]],[0,0,1,1],[1,1,10],[0,0,1,1]] Output: [None, 9, None, 16]
The top-left 2 × 2 block sums to 2 + 0 + 4 + 3 = 9. Setting the 3 to 10 raises it by 7, to 16.
Input: ops = ["NumMatrix","update","update","sumRegion","sumRegion"], args = [[[[1,1],[1,1]]],[0,0,5],[1,1,-2],[0,0,1,1],[0,0,0,1]] Output: [None, None, None, 5, 6]
After the updates the matrix is [[5,1],[1,-2]]: its total is 5 and its top row sums to 6.
Constraints
- 1 <= m, n <= 200
- -1000 <= matrix[i][j], val <= 1000
- 0 <= row < m, 0 <= col < n
- row1 <= row2 and col1 <= col2, all valid indices
- At most 5000 calls in total to update and sumRegion
Approaches
- Baseline: keep the matrix, sum on demand — time O(1) update, O(m · n) query, space O(m · n)
Follow-up
What if updates add to a whole rectangle and queries read single cells? Store a difference grid in the same tree: the use cases cover that and a toggle-and-count grid.
Related problems
Start free on Cariara · Coding problems · System design studio
