Range Sum Query 2D Mutable LeetCode 308

LeetCode 308 Range Sum Query 2D Mutable presents a classic data structure design challenge: given an m x n integer matrix, implement a class that supports two operations — update(row, col, val) which sets the value at a specific cell, and sumRegion(row1, col1, row2, col2) which returns the sum of all elements inside the rectangle defined by the top-left corner (row1, col1) and the bottom-right corner (row2, col2). The word "mutable" is the key — values in the matrix can change, so any solution must handle repeated updates efficiently.

The naive approach recomputes the region sum from scratch on every query in O(m*n) time. A static prefix sum array answers queries in O(1) but requires O(m*n) time to rebuild after every update. Neither approach is acceptable when both operations are called many times. The challenge is finding a data structure that keeps both update and query fast — ideally polylogarithmic in both dimensions.

The constraints enforce the need for efficiency: the matrix can be up to 200 x 200, and the number of update and sumRegion calls can each reach 5000. A solution with O(m*n) per operation would perform up to 200 million basic operations — too slow. The 2D Binary Indexed Tree handles both operations in O(log m * log n), making it the standard solution for this problem.

For the immutable version of this problem (LeetCode 304), a precomputed 2D prefix sum array is optimal. The prefix sum prefix[i][j] stores the sum of all elements in the rectangle from (0,0) to (i-1, j-1). Any rectangular region sum is then computable in O(1) using the inclusion-exclusion formula: sumRegion(r1,c1,r2,c2) = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]. This is perfect when no updates occur.

Once updates are allowed, maintaining the prefix sum array becomes expensive. Changing a single cell matrix[r][c] invalidates all prefix entries prefix[i][j] where i > r and j > c — in the worst case that is the entire matrix. Rebuilding the prefix sum table takes O(m*n) time. With 5000 updates each requiring an O(m*n) rebuild, the total cost is O(5000 * m * n) = O(200 million) operations — clearly unacceptable.

What we need is a data structure that supports incremental updates: when one cell changes, only O(log m * log n) entries in the internal structure need updating, not O(m*n). This is precisely what a Binary Indexed Tree provides. The BIT's structure — where each index stores the sum of a carefully chosen range determined by the lowest set bit — enables both point updates and prefix sum queries to propagate through only O(log n) indices in each dimension.

A 1D Binary Indexed Tree is an array-based structure where each index i stores the sum of a range of original values determined by the lowest set bit of i (written lowbit(i) = i & -i). Index i covers the range (i - lowbit(i), i] — that is, lowbit(i) consecutive elements ending at position i. This arrangement allows both prefix sum queries and point updates to traverse only O(log n) indices by repeatedly adding or stripping the lowest set bit.

The update operation for a 1D BIT starts at position i and propagates to all ancestors by repeatedly adding lowbit(i): i += lowbit(i). This visits every BIT node that has i in its covered range. The prefix sum operation starts at position i and walks toward zero by repeatedly subtracting lowbit(i): i -= lowbit(i). This accumulates the sums of all non-overlapping ranges that together cover (0, i]. Both operations touch at most log2(n) indices.

The BIT uses 1-indexed arrays of size n+1, where index 0 is unused. To convert from a 0-indexed matrix interface to the 1-indexed BIT, always add 1 to row and column indices before calling BIT operations. This off-by-one translation is the single most common source of bugs when implementing a BIT from scratch.

A 2D Binary Indexed Tree extends the 1D structure by nesting two BIT traversals. The internal tree array is a 2D array bit[m+1][n+1] initialized to zero. For every row index traversal (outer BIT loop), an independent column BIT traversal is performed (inner BIT loop). Each entry bit[i][j] stores the partial sum for the rectangle (i - lowbit(i), i] x (j - lowbit(j), j] in the original matrix.

The 2D update for position (r, c) with delta propagates through the outer row BIT starting at r: for each row index ri (ri starts at r, ri += lowbit(ri)), run the inner column BIT starting at c: for each column index ci (ci starts at c, ci += lowbit(ci)), add delta to bit[ri][ci]. This touches O(log m) row indices and O(log n) column indices at each row, for O(log m * log n) total operations.

The 2D prefix sum for rectangle (0,0) to (r,c) mirrors the update in reverse: walk the outer row BIT downward from r (ri -= lowbit(ri)) and for each ri walk the inner column BIT downward from c (ci -= lowbit(ci)), accumulating bit[ri][ci]. The result is the sum of all elements in the rectangle (0,0) to (r,c) in the original matrix — the 2D analog of the 1D prefix sum.

The sumRegion(r1, c1, r2, c2) operation on the 2D BIT uses the same inclusion-exclusion formula as 2D prefix sums. Define prefixSum(r, c) as the sum of all elements in the rectangle from (0,0) to (r,c) computed using the 2D BIT query. Then the rectangle sum from (r1,c1) to (r2,c2) equals prefixSum(r2,c2) - prefixSum(r1-1,c2) - prefixSum(r2,c1-1) + prefixSum(r1-1,c1-1).

The subtraction removes the regions above and to the left of the target rectangle, and the addition restores the corner region that was subtracted twice. This is exactly the 2D inclusion-exclusion principle — the same formula works whether the prefix sums come from a static table or a BIT query. When r1 = 0 or c1 = 0, the corresponding prefix sum terms are zero and the formula simplifies, but the general formula handles all edge cases correctly.

Each call to sumRegion makes at most four calls to prefixSum, each costing O(log m * log n). The total cost per sumRegion is therefore O(log m * log n). With both update and sumRegion at the same asymptotic cost, the 2D BIT achieves the optimal balance between the two operations for this problem.

In Python, the NumericMatrix class stores the original matrix (for computing delta on update), the BIT array bit of size (m+1) x (n+1), and m, n dimensions. The __init__ method initializes bit to all zeros then calls update for every (i, j) cell with val = matrix[i][j]. The update method computes delta = val - self.matrix[r][c], updates self.matrix[r][c] = val, then runs the nested BIT loops. The query method runs the nested downward BIT loops to return the prefix sum. sumRegion applies the four-term inclusion-exclusion formula.

In Java, the NumMatrix class mirrors the Python implementation with int[][] bit and int[][] matrix. Java's lack of default-zero-initialized arrays requires explicit initialization in the constructor. The update and query methods use while loops identical in structure to the Python version. Pay careful attention to the 1-indexed BIT convention: all calls to update and query add 1 to the 0-indexed row and column arguments received from the public interface.

Both implementations store O(m*n) space for the BIT and O(m*n) for the original matrix copy, giving O(m*n) total space. The constructor initializes in O(m*n*log m*log n) time by calling update for every cell. Each subsequent update or sumRegion call runs in O(log m * log n). For the given constraints (200x200 matrix, 5000 calls), the constructor does at most 200*200*8*8 ≈ 5 million operations and each query does at most 64 operations — well within time limits.

Range Sum Query 2D Immutable (LeetCode 304) is the direct precursor — it uses a static 2D prefix sum table for O(1) query with no updates. Solving 304 first cements the inclusion-exclusion formula before tackling the mutable variant. Range Sum Query Mutable (LeetCode 307) is the 1D version of this problem — implementing a 1D BIT for 307 is the essential stepping stone to understanding the 2D BIT for 308.

Segment trees offer an alternative approach for range queries with point updates. A 2D segment tree supports the same O(log m * log n) operations as a 2D BIT but with higher constant factors and more complex implementation. For competitive programming and interviews, the BIT is preferred for range sum problems due to its simplicity. Segment trees become necessary when range updates (not just point updates) are required, or when the query is not a prefix-decomposable operation.

Other problems in the BIT family include Count of Smaller Numbers After Self (LeetCode 315), which uses a coordinate-compressed 1D BIT to count inversions. Reverse Pairs (LeetCode 493) and Count of Range Sum (LeetCode 327) are similar merge-sort or BIT problems involving counting rather than summing. Mastering the 2D BIT for LeetCode 308 provides the foundation for all multi-dimensional Fenwick Tree problems that appear at the hard level in competitive programming.