LeetCode 307: Range Sum Query - Mutable

Problem Restatement

We are given an integer array nums.

We need to implement a class called NumArray that supports two operations:

Unlike LeetCode 303, the array is mutable. Values can change after initialization.

The official problem expects many updates and many range queries, so recomputing sums from scratch every time is too slow. (github.com)

Input and Output

Class shape:

class NumArray:

    def __init__(self, nums: list[int]):
        ...

    def update(self, index: int, val: int) -> None:
        ...

    def sumRange(self, left: int, right: int) -> int:
        ...

Examples

Example:

nums = [1, 3, 5]
obj = NumArray(nums)

Query:

obj.sumRange(0, 2)

This computes:

1 + 3 + 5 = 9

Output:

9

Now update:

obj.update(1, 2)

The array becomes:

[1, 2, 5]

Now query again:

obj.sumRange(0, 2)

Result:

1 + 2 + 5 = 8

Output:

8

First Thought: Direct Updates and Direct Queries

We could store the array normally.

For update, simply overwrite the value.

nums[index] = val

For sumRange, loop from left to right.

total = 0

for i in range(left, right + 1):
    total += nums[i]

This works.

But one query may scan many elements.

If there are many operations, total runtime becomes large.

Prefix Sums No Longer Work Well

In LeetCode 303, prefix sums solved the immutable version.

But now updates change the array.

Suppose:

nums = [1, 3, 5]

Prefix sums are:

[0, 1, 4, 9]

If we update:

nums[1] = 2

then every later prefix value changes.

We would need to rebuild many entries.

That makes updates expensive.

We need a structure supporting:

Key Insight

We need a data structure that stores partial sums efficiently.

A Fenwick Tree, also called a Binary Indexed Tree (BIT), does exactly this.

It supports:

The idea is:

1. Store sums of carefully chosen ranges.
2. Use binary properties of indices to move through those ranges efficiently.

Lowest Set Bit

Fenwick Tree navigation depends on the lowest set bit.

For any positive integer:

Examples:

This value tells us the size of the range represented by a tree node.

Fenwick Tree Structure

Fenwick Tree uses 1-based indexing internally.

Suppose:

nums = [1, 3, 5, 7]

Internally:

Each node stores a partial prefix sum.

Prefix Sum Query

To compute prefix sum up to index i:

1. Add tree[i]
2. Move left by removing the lowest set bit

i -= i & -i

Repeat until i == 0.

This jumps through logarithmically many ranges.

Point Update

When updating one element:

1. Compute the difference:

delta = new_value - old_value

2. Add delta to all Fenwick nodes covering that position.

Move upward using:

i += i & -i

Range Sum Formula

A range sum can be written as:

So if we can compute prefix sums efficiently, range sums are also efficient.

Algorithm

Initialization:

1. Store a copy of the original array.
2. Create a Fenwick tree array.
3. Insert each value using point updates.

Update:

1. Compute the change from old value.
2. Update the original array.
3. Propagate the difference through the Fenwick tree.

Range Query:

1. Compute prefix sum up to right.
2. Compute prefix sum up to left - 1.
3. Return the difference.

Correctness

Each Fenwick tree node stores the sum of a specific contiguous range determined by its lowest set bit.

When performing an update at index i, every Fenwick node whose represented range contains i is updated by the same difference. Therefore, all stored partial sums remain correct after the update.

The prefix sum procedure repeatedly jumps to parent ranges using:

i -= i & -i

These ranges are disjoint and together exactly cover all elements from index 1 through the requested position. Therefore, their sum equals the correct prefix sum.

A range sum from left to right equals:

prefix(right) - prefix(left - 1)

because the elements before left cancel out.

Since both prefix sums are correct, the computed range sum is also correct.

Therefore, the algorithm always returns correct answers after any sequence of updates.

Complexity

The tree contains n + 1 elements because of 1-based indexing.

Implementation

class FenwickTree:

    def __init__(self, size: int):
        self.n = size
        self.tree = [0] * (size + 1)

    def update(self, index: int, delta: int) -> None:
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index

    def query(self, index: int) -> int:
        total = 0

        while index > 0:
            total += self.tree[index]
            index -= index & -index

        return total

class NumArray:

    def __init__(self, nums: list[int]):
        self.nums = nums[:]
        self.bit = FenwickTree(len(nums))

        for i, num in enumerate(nums):
            self.bit.update(i + 1, num)

    def update(self, index: int, val: int) -> None:
        delta = val - self.nums[index]

        self.nums[index] = val

        self.bit.update(index + 1, delta)

    def sumRange(self, left: int, right: int) -> int:
        return (
            self.bit.query(right + 1)
            - self.bit.query(left)
        )

Code Explanation

The Fenwick tree constructor creates:

self.tree = [0] * (size + 1)

Index 0 is unused.

The update operation propagates changes upward.

while index <= self.n:
    self.tree[index] += delta
    index += index & -index

Each jump moves to the next node covering a larger range.

The query operation computes a prefix sum.

while index > 0:
    total += self.tree[index]
    index -= index & -index

Each jump removes the current lowest set bit, moving toward smaller prefix ranges.

In NumArray, we store a copy of the array:

self.nums = nums[:]

We need this to compute update differences later.

During initialization:

for i, num in enumerate(nums):
    self.bit.update(i + 1, num)

We insert every number into the Fenwick tree.

The tree uses 1-based indexing, so we use i + 1.

For updates:

delta = val - self.nums[index]

Only the difference matters.

Then propagate that difference through the tree.

self.bit.update(index + 1, delta)

Range sums use two prefix sums:

return (
    self.bit.query(right + 1)
    - self.bit.query(left)
)

Testing

def run_tests():
    arr = NumArray([1, 3, 5])

    assert arr.sumRange(0, 2) == 9

    arr.update(1, 2)

    assert arr.sumRange(0, 2) == 8

    arr.update(0, 4)

    assert arr.sumRange(0, 1) == 6

    single = NumArray([7])

    assert single.sumRange(0, 0) == 7

    single.update(0, 10)

    assert single.sumRange(0, 0) == 10

    negatives = NumArray([-1, -2, -3, -4])

    assert negatives.sumRange(0, 3) == -10
    assert negatives.sumRange(1, 2) == -5

    negatives.update(2, 5)

    assert negatives.sumRange(0, 3) == -2

    zeros = NumArray([0, 0, 0])

    assert zeros.sumRange(0, 2) == 0

    zeros.update(1, 7)

    assert zeros.sumRange(0, 2) == 7

    print("all tests passed")

run_tests()

Test meaning: