266. Range Sum Query - Mutable
Design a class NumArray over an integer array nums that supports both point updates and range sums, interleaved in any order.
- The constructor receives
nums. update(index, val)replaces the element atindexwithval(it does not add to it).sum_range(left, right)returns the sum of the elements from indexleftthrough indexright, both ends included, reflecting every update made so far.
A plain prefix-sum table makes queries fast but falls apart when the array changes — one update invalidates every total after it. The interesting part of this problem is picking a structure where both operations stay cheap.
Example 1:
Input: NumArray([2, 4, 6, 8]); sum_range(1, 3), update(2, 1), sum_range(1, 3), sum_range(0, 0)
Output: [18, 13, 2]
Explanation: sum_range(1, 3) = 4 + 6 + 8 = 18. After update(2, 1) the array is [2, 4, 1, 8], so the same range now sums to 13, and sum_range(0, 0) returns the untouched 2.
Example 2:
Input: NumArray([5]); update(0, -3), sum_range(0, 0)
Output: [-3]
Explanation: update replaces the value outright: the 5 becomes -3, and the query reads the new value.
Constraints:
- 1 ≤ nums.length ≤ 3 * 10⁴
- -100 ≤ nums[i], val ≤ 100
- 0 ≤ index < nums.length and 0 ≤ left ≤ right < nums.length
- At most 3 * 10⁴ calls in total to update and sum_range, interleaved
Hints:
Two easy extremes both have a slow side: a plain array gives O(1) update but O(n) sum, and a prefix-sum table gives O(1) sum but O(n) rebuild per update. When both operations happen often, you want a structure that is merely 'pretty fast' at both.
A Fenwick tree (binary indexed tree) stores partial sums where node i is responsible for the last (i & -i) elements ending at i. Walking i += i & -i or i -= i & -i visits only O(log n) nodes for an update or a prefix sum.
update gives you a new value, not a delta — keep a copy of the current array so you can feed the tree val - vals[index], then record the new value.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: NumArray([2, 4, 6, 8]); sum_range(1, 3), update(2, 1), sum_range(1, 3), sum_range(0, 0)
Expected output: [18, 13, 2]