LeetCode 307 - Range Sum Query - Mutable

LeetCode Problem 307

Difficulty: 🟡 Medium
Topics: Array, Divide and Conquer, Design, Binary Indexed Tree, Segment Tree

Solution

Problem Understanding

The problem asks us to design a mutable range sum data structure. We are given an integer array nums, and we must efficiently support two operations:

1. Updating the value at a specific index.
2. Querying the sum of elements within a range [left, right].

The important detail is that updates happen dynamically after initialization. This means the array changes over time, and every future range sum query must reflect the most recent updates.

A naive implementation could simply store the array and recompute sums whenever sumRange() is called. While this works functionally, it becomes inefficient when there are many operations. The constraints allow up to 3 * 10^4 calls to update and sumRange, so repeatedly scanning portions of the array can become too expensive.

The input consists of:

• An initial integer array nums

• Multiple calls to:

• update(index, val)

• sumRange(left, right)

The expected output for sumRange(left, right) is the inclusive sum:

$$nums[left] + nums[left+1] + \dots + nums[right]$$

The constraints reveal several important characteristics:

• The array size can be as large as 30,000
• There can also be up to 30,000 operations
• Values may be negative
• Updates may occur at any position

These constraints strongly suggest that an O(n) query solution is not ideal. In the worst case, 30,000 queries each taking 30,000 operations would lead to roughly 9 * 10^8 operations, which is too slow.

Several edge cases are important:

• Arrays of length 1
• Updating the same index repeatedly
• Querying a single element range where left == right
• Negative values causing sums to decrease
• Full array range queries such as [0, n-1]

The problem guarantees that all indices are valid, so we do not need to handle out-of-bounds accesses.

Approaches

Brute Force Approach

The simplest solution is to store the array directly.

For update(index, val), we simply assign:

nums[index] = val

For sumRange(left, right), we iterate from left to right and compute the sum manually.

This approach is straightforward and always correct because every query directly reads the current values from the array. However, each range sum query takes O(n) time in the worst case.

Since there may be up to 30,000 queries, this solution can become too slow.

Key Insight for the Optimal Solution

The core issue is that we need both:

• Fast updates
• Fast range sum queries

Prefix sums alone are not enough because updates would require rebuilding the prefix array in O(n) time.

The important observation is that we need a data structure capable of efficiently maintaining partial sums while supporting modifications.

A Binary Indexed Tree, also called a Fenwick Tree, solves exactly this problem.

The Fenwick Tree stores cumulative frequency information in a compressed structure. Instead of recalculating entire prefixes after every update, it only updates a logarithmic number of tree nodes.

This gives:

• O(log n) updates
• O(log n) range sum queries

The structure works by storing sums for carefully chosen ranges determined by binary index manipulation.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Update: O(1), Query: O(n)	O(1)	Simple array scan for every query
Optimal	Update: O(log n), Query: O(log n)	O(n)	Uses Binary Indexed Tree for efficient prefix sums

Algorithm Walkthrough

Binary Indexed Tree Structure

A Fenwick Tree maintains prefix sums using a 1-indexed internal array.

Each tree position stores the sum of a specific range of values. The size of that range depends on the least significant set bit of the index.

Step-by-Step Algorithm

1. Initialize two arrays.

We store:

• The original values in nums
• The Fenwick Tree in tree

The tree array is sized n + 1 because index 0 is unused. 2. Build the Fenwick Tree.

For every number in the input array:

• Insert its value into the Fenwick Tree
• Propagate the contribution upward through relevant tree nodes

This prepares the structure for efficient future queries. 3. Handle updates efficiently.

When updating an index:

• Compute the difference:

$$delta = newValue - oldValue$$

• Update the original array
• Add delta to every Fenwick Tree node responsible for that index

We only touch O(log n) nodes because each jump removes one binary contribution. 4. Compute prefix sums.

To calculate the prefix sum up to index i:

• Move upward through Fenwick Tree parents
• Accumulate stored partial sums

Each step removes the least significant set bit. 5. Compute range sums.

Any range sum can be written as:

$$prefix(right) - prefix(left - 1)$$

This converts arbitrary range queries into two prefix queries.

Why it works

The Fenwick Tree maintains the invariant that every node stores the sum of a specific contiguous range of elements.

Binary index manipulation ensures that every array element contributes to exactly the correct collection of tree nodes. Because updates propagate through all affected nodes and queries combine exactly the necessary partial sums, the returned range sum is always correct.

Python Solution

from typing import List

class NumArray:

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

        for i, value in enumerate(nums):
            self._add(i + 1, value)

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

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

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

        return total

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

        self._add(index + 1, delta)

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

The implementation begins by storing a copy of the original array. This is necessary because updates require knowing the old value to compute the difference.

The tree array is the Fenwick Tree structure. It uses 1-based indexing because binary operations become much cleaner and more consistent.

The _add() helper function propagates a value change upward through all affected tree nodes. The expression:

index += index & -index

moves to the next responsible node.

The _prefix_sum() helper computes the cumulative sum from index 1 through index. The expression:

index -= index & -index

moves upward toward the root while collecting contributions.

The update() method computes the delta between old and new values, updates the stored array, and propagates the change through the tree.

The sumRange() method converts the range query into two prefix sums.

Go Solution

type NumArray struct {
	nums []int
	tree []int
	n    int
}

func Constructor(nums []int) NumArray {
	n := len(nums)

	obj := NumArray{
		nums: make([]int, n),
		tree: make([]int, n+1),
		n:    n,
	}

	copy(obj.nums, nums)

	for i, value := range nums {
		obj.add(i+1, value)
	}

	return obj
}

func (this *NumArray) add(index int, delta int) {
	for index <= this.n {
		this.tree[index] += delta
		index += index & -index
	}
}

func (this *NumArray) prefixSum(index int) int {
	total := 0

	for index > 0 {
		total += this.tree[index]
		index -= index & -index
	}

	return total
}

func (this *NumArray) Update(index int, val int) {
	delta := val - this.nums[index]
	this.nums[index] = val

	this.add(index+1, delta)
}

func (this *NumArray) SumRange(left int, right int) int {
	return this.prefixSum(right+1) - this.prefixSum(left)
}

/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * obj.Update(index,val);
 * param_2 := obj.SumRange(left,right);
 */

The Go implementation follows the same logic as the Python version.

One important difference is explicit memory allocation. Go requires initializing slices with make() before use.

The copy() function duplicates the input array so updates do not accidentally modify the original slice reference.

Go integers are sufficient for this problem because the constraints keep sums well within 32-bit range.

Worked Examples

Example 1

Input:

nums = [1, 3, 5]

Initialization

We build the Fenwick Tree step by step.

Step	Action	Tree State
Insert 1	add(1, 1)	[0,1,1,0]
Insert 3	add(2, 3)	[0,1,4,0]
Insert 5	add(3, 5)	[0,1,4,5]

Internal tree representation:

Index	Stored Sum
1	1
2	1 + 3 = 4
3	5

Query sumRange(0, 2)

We compute:

$$prefix(3) - prefix(0)$$

prefix(3)

Current Index	Added Value	Running Total
3	5	5
2	4	9

Result:

9

Update update(1, 2)

Old value:

3

New value:

2

Delta:

-1

We propagate -1 through affected nodes.

Updated Tree Index	New Value
2	3

Updated array:

[1, 2, 5]

Query sumRange(0, 2)

Now:

$$1 + 2 + 5 = 8$$

Returned result:

8

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n) per update and query	Fenwick Tree operations traverse logarithmic tree height
Space	O(n)	Tree array stores cumulative information

The Fenwick Tree uses one auxiliary array of size n + 1.

Both updates and prefix queries repeatedly add or remove the least significant set bit from the index. Since each operation reduces the remaining binary structure, the number of iterations is logarithmic.

Test Cases

from typing import List

class NumArray:

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

        for i, value in enumerate(nums):
            self._add(i + 1, value)

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

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

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

        return total

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

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

# Example case
obj = NumArray([1, 3, 5])
assert obj.sumRange(0, 2) == 9  # initial full range
obj.update(1, 2)
assert obj.sumRange(0, 2) == 8  # after update

# Single element array
obj = NumArray([7])
assert obj.sumRange(0, 0) == 7  # single value query
obj.update(0, 10)
assert obj.sumRange(0, 0) == 10  # updated single value

# Negative numbers
obj = NumArray([-1, -2, -3, -4])
assert obj.sumRange(1, 3) == -9  # negative range sum

# Multiple updates
obj = NumArray([1, 2, 3, 4, 5])
obj.update(0, 10)
obj.update(4, 20)
assert obj.sumRange(0, 4) == 39  # multiple updates applied

# Query middle subarray
obj = NumArray([5, 8, 6, 3, 2, 7])
assert obj.sumRange(2, 4) == 11  # middle section

# Update with same value
obj = NumArray([1, 2, 3])
obj.update(1, 2)
assert obj.sumRange(0, 2) == 6  # unchanged total

# Full range query
obj = NumArray([4, 5, 6, 7])
assert obj.sumRange(0, 3) == 22  # complete array sum

# Repeated updates on same index
obj = NumArray([0, 0, 0])
obj.update(1, 5)
obj.update(1, -3)
obj.update(1, 8)
assert obj.sumRange(0, 2) == 8  # latest value retained

Test Case Summary

Test	Why
[1,3,5] example	Validates standard operations
Single element array	Tests smallest valid input
Negative values	Ensures sums handle negatives correctly
Multiple updates	Confirms cumulative updates work
Middle subarray query	Verifies partial range correctness
Update with same value	Ensures zero delta updates behave correctly
Full range query	Tests prefix subtraction logic
Repeated updates on same index	Validates consistency over many mutations

Edge Cases

Single Element Arrays

When the array contains only one element, every query becomes a single-value range query. Some implementations incorrectly assume ranges contain multiple elements or mishandle prefix subtraction at index zero.

This implementation handles the case naturally because:

_prefix_sum(right + 1) - _prefix_sum(left)

still works correctly when both indices refer to the same element.

Updating an Index to the Same Value

If the new value equals the old value, the computed delta becomes zero.

A buggy implementation might unnecessarily rebuild structures or accidentally double-count values. Here, propagating a delta of zero changes nothing, so correctness is preserved automatically.

Negative Numbers

Negative values are important because sums are not monotonic.

Some incorrect implementations assume cumulative sums always increase. The Fenwick Tree does not rely on positivity. It only stores arithmetic sums, so negative contributions work exactly the same as positive ones.

Full Array Queries

Queries such as:

sumRange(0, n - 1)

are common boundary cases.

Incorrect prefix logic often causes off-by-one errors at the left boundary. This implementation avoids that issue by consistently using:

prefix(right + 1) - prefix(left)

with a 1-indexed Fenwick Tree representation.