Range Sum Query — Mutable
Design a structure over an integer array supporting two interleaved operations: update(i, v) sets element i to v, and sumRange(l, r) returns the sum of elements from l to r inclusive. Both must be fast for large numbers of calls.
- 1 ≤ n ≤ 3 · 10^4
- -100 ≤ nums[i] ≤ 100
- At most 3 · 10^4 calls to update and sumRange
- Point updates interleaved with range queries
- Plain prefix sums cost O(n) per update
- Balanced tree of partial sums — O(log n) each
Prefix sums break the moment the array changes, since every prefix after the update shifts. A Fenwick or segment tree stores partial aggregates over power-of-two ranges so both a point update and a range query touch only O(log n) nodes. Use a sparse table instead when the array is static and the operation is idempotent (min, max, gcd).
Build a segment tree where each node stores the sum of a contiguous range and leaves are individual elements. update changes a leaf and recomputes the sums along the path to the root. sumRange descends from the root, returning a node's sum when its range lies inside the query, ignoring nodes outside it and recursing into partially overlapping ones — at most O(log n) nodes are combined.
- A Fenwick tree does the same with less code and memory using prefix sums and the lowest-set-bit trick. Sqrt decomposition gives O(√n) operations with the simplest code.