Design a data structure that supports efficiently updating elements in a 2D matrix and querying the sum of elements within a given rectangular subregion. Implement the following methods:
1. __init__(grid): Initializes the data structure with a 2D integer matrix grid.
2. update(row_idx, col_idx, new_val): Updates the element at position (row_idx, col_idx) to new_val.
3. sum_region(row1, col1, row2, col2): Returns the sum of the elements within the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2), inclusive.
Example 1
Input: grid = [[2,3,1],[4,5,6],[7,8,9]] obj = NumMatrix(grid) obj.update(1, 2, 10) output1 = obj.sum_region(0, 0, 2, 2) output2 = obj.sum_region(1, 1, 2, 2)
Output: output1 = 2+3+1+4+5+10+7+8+9 = 49 output2 = 5+10+8+9 = 32
Explanation: After updating grid[1][2] to 10, sum_region(0,0,2,2) returns 49, sum_region(1,1,2,2) returns 32.
Example 2
Input: grid = [[0,1],[2,3]] obj = NumMatrix(grid) obj.update(0, 0, 5) output1 = obj.sum_region(0, 0, 1, 1) output2 = obj.sum_region(0, 1, 1, 1)
Output: output1 = 5+1+2+3 = 11 output2 = 1+3 = 4
Explanation: After updating grid[0][0] to 5, sum_region(0,0,1,1) returns 11, sum_region(0,1,1,1) returns 4.
Constraints
Case 1
Input: grid = [[1,2,3],[4,5,6],[7,8,9]] obj = NumMatrix(grid) obj.update(2, 0, 0) result1 = obj.sum_region(0, 0, 1, 2) result2 = obj.sum_region(2, 0, 2, 2)
Expected: result1 = 1+2+3+4+5+6 = 21 result2 = 0+8+9 = 17
Case 2
Input: grid = [[-1,2],[3,-4]] obj = NumMatrix(grid) obj.update(1, 1, 7) result1 = obj.sum_region(0, 0, 1, 1) result2 = obj.sum_region(1, 0, 1, 1)
Expected: result1 = -1+2+3+7 = 11 result2 = 3+7 = 10