Range Sum Query Mutable LeetCode 307

LeetCode 307 — Range Sum Query - Mutable — asks you to implement a NumArray class that supports two operations: update(index, val) to set nums[index] = val, and sumRange(left, right) to return the sum of nums[left..right] inclusive.

A naive approach uses a plain array: update is O(1) but sumRange is O(n). A prefix sum array makes sumRange O(1) but update becomes O(n) since all subsequent prefix sums must be recomputed. Neither achieves O(log n) for both operations.

The solution requires a tree-based data structure: either a segment tree (divide-and-conquer on ranges) or a Binary Indexed Tree / Fenwick tree (clever use of binary representation for prefix sums). Both achieve O(log n) for both operations.

A segment tree is a full binary tree where each node stores the sum of a range. The root stores the sum of the entire array. Its left child stores the sum of the left half, right child the right half. Leaves store individual elements.

To build, allocate an array of size 4n (or 2n for a compact representation). Recursively build: each node = sum of its two children. Leaves are the original array values. Build runs in O(n).

To update index i: start at the root, recurse to the leaf at position i, update its value, then propagate the change upward by recomputing parent sums. Each level is visited once, so update is O(log n). To query sum(left, right): recursively split the range, combining results from nodes that overlap with [left, right]. Query is also O(log n).

A Fenwick tree (BIT) stores partial sums in an array where each index i is responsible for a range of elements determined by the lowest set bit of i. The tree supports prefix sum queries and point updates in O(log n) each.

To get sumRange(left, right), compute prefix(right) - prefix(left - 1). The prefix sum at index i is obtained by summing BIT[i], BIT[i - lowbit(i)], BIT[i - lowbit(i) - lowbit(...)], etc., where lowbit(i) = i & (-i). This traverses O(log n) nodes.

To update index i by a delta, add the delta to BIT[i], BIT[i + lowbit(i)], BIT[i + lowbit(i) + lowbit(...)], etc. This propagates the change to all ranges that include index i. Again O(log n) nodes are visited.

Consider nums = [1, 3, 5]. Fenwick tree (1-indexed): BIT[1]=1, BIT[2]=1+3=4, BIT[3]=5. To query prefix(3): BIT[3] + BIT[2] = 5 + 4 = 9. To query sumRange(1, 2): prefix(3) is wrong — let me use 0-indexed to 1-indexed mapping. prefix(3) = BIT[3] + BIT[2] = 5 + 4 = 9. prefix(0) = BIT[0] — but BIT is 1-indexed, so prefix(1) = BIT[1] = 1. sumRange(0, 2) = prefix(3) - prefix(0) = 9 - 0 = 9.

Update index 1 to value 2 (was 3, delta = -1): add -1 to BIT[2] and BIT[4] (if exists). BIT[2] = 4 + (-1) = 3. Now prefix(3) = BIT[3] + BIT[2] = 5 + 3 = 8. sumRange(0, 2) = 8 = 1 + 2 + 5. Correct!

Segment tree version: tree = [_, 9, 4, 5, 1, 3, 5, _] (compact 2n layout). Update index 1: leaf at tree[n+1] = 2. Parent tree[(n+1)/2] = tree[n] + tree[n+1] = 1 + 2 = 3. Root tree[1] = 3 + 5 = 8. Query(0,2) = 8.

Python Fenwick tree: self.n = len(nums), self.bit = [0] * (n + 1), self.nums = [0] * n. Build by calling update for each index. Update computes delta = val - self.nums[i], stores new value, then propagates. Query sums prefix using i & (-i) trick.

Java iterative segment tree: int[] tree = new int[2 * n]. Build: copy nums to tree[n..2n-1], then for i = n-1 down to 1: tree[i] = tree[2i] + tree[2i+1]. Update: set tree[n+i] = val, walk up. Query: initialize left = n+l, right = n+r+1, accumulate sum while left < right.

The iterative segment tree is particularly elegant in Java — about 25 lines total for the entire class. The Fenwick tree is even shorter at about 20 lines. Both are worth memorizing for competitive programming and interviews.

Build time: O(n) for both segment tree and Fenwick tree. The segment tree fills 2n nodes bottom-up. The Fenwick tree processes n updates during initialization, but can be optimized to O(n) with a linear build.

Update and query: O(log n) each for both data structures. The segment tree traverses the tree height (log n). The Fenwick tree follows the bit pattern of the index (at most log n steps).

Space: O(n) for both. The segment tree uses 2n or 4n array entries. The Fenwick tree uses n+1 entries. In practice, the Fenwick tree uses less memory and has better cache performance due to sequential access patterns.

Range Sum Query - Immutable (LeetCode 303) is the simpler version without updates, solvable with prefix sums. Range Sum Query 2D - Mutable (LeetCode 308) extends to two dimensions, requiring a 2D segment tree or 2D Fenwick tree.

Count of Smaller Numbers After Self (LeetCode 315) and Reverse Pairs (LeetCode 493) use Fenwick trees or segment trees for order-statistic queries during merge sort. These are harder applications of the same data structures.

My Calendar I/II/III (LeetCode 729, 731, 732) can be solved with segment trees with lazy propagation. These problems demonstrate the flexibility of segment trees beyond simple sum queries — they handle interval scheduling and overlap counting.