Range Sum Query 2D - Mutable - Video Solutions

Problem Overview: You need to design a data structure for a 2D matrix that supports two operations: updating a cell value and returning the sum of elements inside any rectangular submatrix. The challenge is handling frequent updates without recomputing sums for the entire region every time.

Approach 1: Brute Force Recalculation (Update O(1), Query O(m*n))

Store the matrix as-is. For every sumRegion(row1, col1, row2, col2) call, iterate through all cells inside the rectangle and accumulate the sum. Updates are trivial because you simply replace the value in the matrix. The downside is query performance: each query scans up to the entire matrix, giving O(m*n) time and O(1) extra space. This approach works for small matrices or when queries are rare.

Approach 2: 2D Prefix Sum with Rebuild (Update O(m*n), Query O(1))

Precompute a prefix sum matrix where each cell stores the sum of the rectangle from (0,0) to that position. A submatrix sum can then be computed using inclusion–exclusion in constant time. However, when a value changes, every affected prefix cell must be recomputed, which costs O(m*n). This approach favors scenarios with many queries but very few updates. It relies heavily on concepts from array traversal and matrix prefix sums.

Approach 3: 2D Binary Indexed Tree (Fenwick Tree) (Update O(log m * log n), Query O(log m * log n))

A 2D Binary Indexed Tree maintains cumulative sums in a hierarchical structure. Each update propagates changes to logarithmically many nodes, while queries aggregate prefix sums efficiently. To compute a rectangular region sum, query four prefix regions and combine them using inclusion–exclusion. Both updates and queries run in O(log m * log n) time with O(m*n) space. This structure handles frequent updates and queries efficiently, making it the practical optimal solution.

Approach 4: 2D Segment Tree (Update O(log m * log n), Query O(log m * log n))

A 2D Segment Tree organizes the matrix into nested segment trees across rows and columns. Each node represents the sum of a sub-rectangle. Updates propagate through both tree dimensions, and queries traverse only relevant nodes. Performance matches the Binary Indexed Tree with O(log m * log n) operations, but implementation complexity and memory overhead are higher. This approach is useful when you need flexible range operations beyond simple sums.

Recommended for interviews: Interviewers expect the 2D Binary Indexed Tree solution. The brute force version shows you understand the problem baseline, but the Fenwick Tree demonstrates strong data structure skills and the ability to optimize both updates and queries to logarithmic time.