307. Range Sum Query – Mutable

307

MediumAdvanced Range Data StructuresFenwick tree (Binary Indexed Tree)Point update, prefix-sum query

Range Sum Query – Mutable

Design a data structure over an integer array that supports two operations efficiently: update(index, val) sets the element at index to val, and sumRange(left, right) returns the sum of elements from index left to right inclusive. Both may be called many times interleaved.

Open official problem prompt ↗

In plain English

Support fast range sums on an array whose values keep changing, without paying O(n) for either operation.

Picture it like this

Think of nested measuring cups where each cup already holds the total of a run of smaller cups. To read a total you stack a few cups; to change one value you top up only the cups that contain it — never all of them.

Example

Input: NumArray([1,3,5]); sumRange(0,2); update(1,2); sumRange(0,2)
Output: 9, then 8
Why: Initial sum 1+3+5 = 9; after setting index 1 to 2 the array is [1,2,5], so 1+2+5 = 8.

Constraints

1 <= nums.length <= 3 * 10^4-100 <= nums[i] <= 1000 <= index < nums.length0 <= left <= right < nums.lengthAt most 3 * 10^4 calls to update and sumRange

Pattern lesson

See the pattern, then code

Point update, prefix-sum query

↗

Advanced Range Data Structures

Online prefix or range queries with updates, inversions, or coordinate compression.. A plain prefix-sum array answers ranges in O(1) but costs O(n) per update. A Fenwick tree stores partial sums over power-of-two-sized blocks so both update and prefix query touch only O(log n) nodes.

New words, made simpleKnow these before the algorithm

Fenwick tree: An array where index i stores the sum of a block of size equal to the lowest set bit of i.
Lowest set bit: i & (-i) isolates the rightmost 1-bit, giving the size of the block index i covers.
Delta update: Applying only the difference (new - old) so the tree stays consistent without a rebuild.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Prefix-sum array

Any update forces recomputing every later prefix, too slow under many updates.

Precompute cumulative sums; range = prefix[r]-prefix[l-1].

Time O(1) query, O(n) updateSpace O(n)

Segment tree

Correct and general but more code and memory than needed for plain sums.

Binary tree of range sums supporting both operations in log time.

Time O(log n) bothSpace O(n)

Best choiceFenwick tree

Minimal, cache-friendly, and exactly matches point-update range-sum.

Store block partial sums; walk log n nodes for update and prefix query.

Time O(log n) bothSpace O(n)

The rule we keep true

Invariant

tree[i] always equals the sum of the array elements in the range (i - lowbit(i), i], so composing the right set of nodes reconstructs any prefix sum.

Why this is correct

Reasoning

The indices visited by i += i & (-i) during update are exactly those whose covered block contains the updated position, and the indices visited by i -= i & (-i) during a prefix query partition [1, i] into disjoint blocks. Adding a delta to the former keeps every block sum correct, so prefix queries remain accurate.

The algorithm in three movesSay these aloud before coding

1Build a 1-indexed tree array of size n+1

tree after build = [_,1,4,5]

2For update, compute the delta versus the stored value and add it along indices i += i & (-i)

sumRange(0,2)=prefix(2)=9

3For a prefix sum up to i, accumulate along i -= i & (-i)

update(1,2): delta=-1

4Answer sumRange(l, r) as prefix(r) - prefix(l-1)

sumRange(0,2)=8

5Keep a copy of current values so update can derive the delta

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readnums = [1,3,5]

2 · AskWhere does each value flow?

3 · Update statetree = [_,1,4,5]

4 · ResultIndex sums assembled via repeated _add

Key takeaway

The Fenwick tree stores overlapping block sums so a prefix query jumps across log n nodes.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5-10Initialize and seed
Keep a zeroed values copy and feed each element through update so the tree is built with correct deltas.
2
Lines 12-16_add walks upward
Adding i & (-i) moves to the next block that contains this position, updating each partial sum.
3
Lines 18-20update via delta
Only the difference from the stored value is propagated, and the copy is refreshed.
4
Lines 22-28_prefix walks downward
Subtracting the lowest set bit jumps across disjoint blocks that tile [0, i].
5
Lines 30-31Range from two prefixes
sumRange subtracts the prefix just before left from the prefix at right.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

left == right returns a single element
left == 0 makes prefix(left-1) = prefix(-1) = 0 by the +1 indexing
Updating with the same value produces a zero delta and is a no-op on totals
Negative values are handled naturally since only sums are tracked

Common beginner mistakes

Confusing set-to-val with add-val: LeetCode 307 sets the value, so you must apply new-old, not val
Off-by-one from mixing 0-indexed input with the 1-indexed tree
Calling update inside __init__ before self.nums exists, or forgetting to update the copy
Building with O(n log n) individual updates is fine here, but recomputing prefix arrays each update is the trap to avoid

Check your understanding

What does i & (-i) compute, and why does it make both operations O(log n)?

PyPython 3 · solution.py

Optimal

1from typing import List23class NumArray:4    def __init__(self, nums: List[int]):5        self.n = len(nums)6        self.nums = [0] * self.n7        self.tree = [0] * (self.n + 1)8        for i, v in enumerate(nums):9            self.update(i, v)1011    def _add(self, i: int, delta: int) -> None:12        i += 113        while i <= self.n:14            self.tree[i] += delta15            i += i & (-i)1617    def update(self, index: int, val: int) -> None:18        self._add(index, val - self.nums[index])19        self.nums[index] = val2021    def _prefix(self, i: int) -> int:22        s = 023        i += 124        while i > 0:25            s += self.tree[i]26            i -= i & (-i)27        return s2829    def sumRange(self, left: int, right: int) -> int:30        return self._prefix(right) - self._prefix(left - 1)

Time complexityO(log n) per update and query, O(n log n) to buildOptimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonMicrosoft

Range Sum Query – Mutable

Range Sum Query – Mutable

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Advanced Range Data Structures