Practice/Moloco/Leetcode 308. Range Sum Query 2D - Mutable

Leetcode 308. Range Sum Query 2D - Mutable

CodingMust

Problem

Design and implement a data structure that efficiently handles a 2D matrix with two key operations:

1. Update a single cell: Change the value at a specific position in the matrix
2. Query rectangular region sum: Calculate the sum of all elements within a rectangular submatrix defined by its top-left and bottom-right corners

The data structure must handle many interleaved update and query operations efficiently. A naive approach that recalculates sums or stores precomputed prefix sums would be too slow for frequent updates.

Your task is to implement the NumMatrix class with the following methods:

• NumMatrix(matrix): Initializes the object with the integer matrix matrix
• update(row, col, val): Updates the value of the cell at position (row, col) to val
• sumRegion(row1, col1, row2, col2): Returns the sum of the elements in the rectangle defined by its top-left corner (row1, col1) and bottom-right corner (row2, col2) (inclusive)

Requirements

1. Implement the NumMatrix class constructor to initialize with a 2D matrix
2. Implement the update method to modify individual cells efficiently
3. Implement the sumRegion method to calculate rectangular region sums efficiently
4. Both update and query operations should be significantly faster than O(m × n) where m and n are the matrix dimensions
5. The solution should handle many interleaved operations efficiently

Constraints

• 1 ≤ matrix.length, matrix[0].length ≤ 200
• -105 ≤ matrix[i][j] ≤ 105
• 0 ≤ row < matrix.length
• 0 ≤ col < matrix[0].length
• -105 ≤ val ≤ 105
• 0 ≤ row1 ≤ row2 < matrix.length
• 0 ≤ col1 ≤ col2 < matrix[0].length
• At most 5000 calls will be made to update and sumRegion combined

Examples

Example 1:

` Input: ["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]]

Output: [null, 8, null, 10]

Explanation: NumMatrix numMatrix = new NumMatrix([[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]]); numMatrix.sumRegion(2, 1, 4, 3); // returns 8 (sum of region with corners (2,1) and (4,3)) numMatrix.update(3, 2, 2); // matrix[3][2] becomes 2 numMatrix.sumRegion(2, 1, 4, 3); // returns 10 (same region, but value at (3,2) changed from 0 to 2) `

Example 2:

` Input: ["NumMatrix", "sumRegion", "update", "sumRegion"] [[[[1, 2], [3, 4]]], [0, 0, 1, 1], [0, 0, 5], [0, 0, 1, 1]]

Output: [null, 10, null, 14]

Explanation: The initial sum of the entire 2×2 matrix is 1+2+3+4 = 10. After updating position (0,0) from 1 to 5, the sum becomes 5+2+3+4 = 14. `