Range sums with point updates

easy ~20 min

Implement NumArray over a list of integers:

NumArray(nums): build from the initial values (keep your own copy).
update(index, val): set nums[index] = val (it's an assignment, not an add).
sum_range(left, right): return nums[left] + ... + nums[right], inclusive, 0 <= left <= right < n.

na = NumArray([2, 4, 6])
na.sum_range(0, 2)   # 12
na.update(1, -1)
na.sum_range(0, 2)   # 7
na.sum_range(1, 1)   # -1

Constraints: 1 <= n <= 10^5, up to ~10^5 calls, values in [-10^9, 10^9] (so sums can exceed 32 bits). Summing the slice per query and rebuilding prefix sums per update are both O(n) per call; aim for O(log n) per call.

Show hint

Treat an assignment as adding val - old at one position, and a range sum as the difference of two prefix sums. What you need is a structure that supports "add at a point" and "sum of a prefix" in O(log n) each.

Topic: Fenwick tree (BIT). Point update + prefix sum in O(log n) with i & -i.

Read the visual guide