Range Sum Query 2D - Mutable - Practice Coding Problems

Range Sum Query 2D - Mutable - Problem

You are given a 2D matrix matrix and need to handle multiple queries efficiently:

Update: Change the value of a specific cell in the matrix
Sum Query: Calculate the sum of all elements within a rectangular region

Implement the NumMatrix class with these methods:

NumMatrix(int[][] matrix) - Initialize with the given matrix
void update(int row, int col, int val) - Update matrix[row][col] to val
int sumRegion(int row1, int col1, int row2, int col2) - Return sum of rectangle from (row1,col1) to (row2,col2) inclusive

The rectangle is defined by its upper-left corner (row1, col1) and lower-right corner (row2, col2).

Input & Output

Example 1 — Basic Operations

$ Input: matrix = [[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]]

› Output: sumRegion(2,1,4,3) → 8, update(3,2,2), sumRegion(2,1,4,3) → 10

💡 Note: Initial sum from (2,1) to (4,3): 2+0+1+1+0+1+0+3+0 = 8. After updating (3,2) to 2, sum becomes 10.

Example 2 — Single Cell

$ Input: matrix = [[1,2],[3,4]]

› Output: sumRegion(0,0,0,0) → 1, update(0,0,5), sumRegion(0,0,0,0) → 5

💡 Note: Query single cell (0,0) returns 1. After updating to 5, same query returns 5.

Example 3 — Full Matrix

$ Input: matrix = [[1,2],[3,4]]

› Output: sumRegion(0,0,1,1) → 10, update(1,1,6), sumRegion(0,0,1,1) → 12

💡 Note: Sum of entire 2×2 matrix: 1+2+3+4=10. After changing 4 to 6, sum becomes 1+2+3+6=12.

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 200
-10⁵ ≤ matrix[i][j] ≤ 10⁵
0 ≤ row < m
0 ≤ col < n
-10⁵ ≤ val ≤ 10⁵
0 ≤ row1 ≤ row2 < m
0 ≤ col1 ≤ col2 < n
At most 10⁴ calls to update and sumRegion

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2D matrix with initial values

Operations

Support update(row,col,val) and sumRegion(r1,c1,r2,c2)

Efficient Solution

Use data structure for fast updates and queries

Key Takeaway

🎯 Key Insight: Use Binary Indexed Tree to achieve O(log m × log n) for both updates and range sum queries

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is using a 2D Binary Indexed Tree to balance update and query performance. While brute force has O(1) updates but O(m×n) queries, and prefix sums have O(1) queries but O(m×n) updates, BIT provides O(log m × log n) for both operations. Best approach is Binary Indexed Tree. Time: O(log m × log n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ 2D Prefix Sum with Rebuild	O(m×n)	O(m×n)	Use 2D prefix sum array, rebuild after each update
Brute Force - Direct Calculation	O(m×n)	O(1)	Store matrix directly, sum by iterating through rectangle for each query
Binary Indexed Tree (2D Fenwick Tree)	O(log m × log n)	O(m×n)	Use 2D Binary Indexed Tree for O(log m × log n) updates and queries

2D Prefix Sum with Rebuild — Algorithm Steps

Build 2D prefix sum array
Query: use inclusion-exclusion principle O(1)
Update: modify matrix then rebuild entire prefix array
Trade update time for query speed

Code -

solution.c — C

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Each update requires rebuilding the entire m×n prefix sum array

✓ Linear Growth

Space Complexity

O(m×n)

Additional m×n array to store prefix sums

⚡ Linearithmic Space

89.0K Views

Medium Frequency

~35 min Avg. Time

967 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen