Range Sum Query — Mutable

Range Sum Query — Mutable medium

Description

Implement NumArray:

NumArray(nums) — initialize with the array.
update(index, val) — set nums[index] = val.
sumRange(left, right) — return the sum of nums[left..right] inclusive.

Examples

> nums = [1, 3, 5]
  sumRange(0, 2)  -> 9
  update(1, 2)               # nums = [1, 2, 5]
  sumRange(0, 2)  -> 8

Constraints

1 <= nums.length <= 3 × 10^4
up to 3 × 10^4 calls to update + sumRange.

This is the textbook “prefix sums won’t cut it” problem: with interleaved updates, a prefix-sum array is O(n) per update. We need O(log n) for both.

Try it

Try it — range-sum query and point update, both O(log n)

query [,]

set i=

Intuition

A point-update, range-sum query — the exact sweet spot for both a BIT (shorter) and a segment tree (more general). Below: the BIT, because it’s the leanest correct answer. (For the segment-tree version, see The Template.)

Code (Fenwick tree)

⚠️

update adds the delta, not the value. A BIT accumulates, so to set nums[index] = val you push val − old, then remember the new value. Adding val directly would double-count. Also note the i++ inside the loops: the BIT is 1-indexed, so 0-based input shifts up by one.

Analysis

Time: update and sumRange are O(log n); construction is O(n log n) (or O(n) with a smarter build).
Space: O(n) for the BIT — versus 4n for a segment tree.

Same skin

The Template — the segment-tree solution to this same problem.
Range Minimum Query — same shape, but min isn’t invertible so you must use a segment tree.
Range Sum Query 2D — Mutable — the 2D BIT extension.

Overview Range Minimum Query