Difficulty: MediumAdvanced Data Structures

Range Sum Query - Mutable

Problem in Plain English

Support point assignments and inclusive range sums on an integer array. Compare direct scanning, a Segment Tree and a Fenwick Tree.

Problem Statement

Implement NumArray(nums), update(index, val) and sumRange(left, right). An update replaces one value; it does not add val to that value. A query returns the sum from left through right inclusive, using zero-based indices. The official exercise interleaves updates and queries on the same object.

Constraints

1 <= nums.length <= 3 × 10^4.
-100 <= nums[i], val <= 100.
0 <= index < nums.length; 0 <= left <= right < nums.length.
At most 3 × 10^4 calls to update and sumRange.

Examples

Example 1

Input: NumArray([1,3,5]); sumRange(0,2); update(1,2); sumRange(0,2)
Output: [null,9,null,8]

Construction and assignment return null in the operation transcript. The first sum is 9; replacing 3 by 2 makes the next sum 8.

Example 2

Input: NumArray([-5]); sumRange(0,0); update(0,0); sumRange(0,0)
Output: [null,-5,null,0]

A singleton inclusive range contains that one value. Assigning zero applies delta +5.

Example 3

Input: NumArray([2,-1,4]); update(1,-1); sumRange(1,2); update(2,-4); sumRange(0,2)
Output: [null,null,3,null,-3]

Assigning the same value has delta zero. The partial sum is -1+4=3; replacing 4 with -4 changes the full sum to 2-1-4=-3.

Intuition

A direct scan repeats work when queries overlap. Store sums of reusable blocks so an update repairs only the blocks containing its index. Example 1 changes 3 to 2, a delta of -1, so the full sum changes from 9 to 8. A Segment Tree combines child sums; a Fenwick Tree organizes prefix blocks with the lowest set bit. Fenwick is selected for this sum-only interface because it needs one compact tree array; Segment Trees generalize to more operations.

Approaches

Direct Scan

Solution Details

Reveal Direct Scan: intuition, complexity, and code

Intuition

Keep a private array, assign the new value directly, and add every entry in the inclusive query interval. Construction copies n elements, updates are constant time, but each query may read n values. This is a useful baseline when updates dominate or the array is tiny.

Step-by-Step Logic

Copy [1,3,5] during construction.
Scan indices 0,1,2: accumulator becomes 1,4,9; report 9.
Assign index 1 to 2, producing [1,2,5].
Scan indices 0,1,2 again: accumulator becomes 1,3,8.
Return transcript [null,9,null,8].

Why It Works

The stored array initially equals nums and each assignment preserves equality with the logical array. The query loop visits each index from left to right exactly once, including both endpoints, so its accumulator is precisely the requested sum.

Dry Run

Direct Scan: variable states at each step
Operation	Array	Accumulator transitions	Result
Construct	[1,3,5]	none	null
sumRange(0,2)	[1,3,5]	0 → 1 → 4 → 9	9
update(1,2)	[1,2,5]	none	null
sumRange(0,2)	[1,2,5]	0 → 1 → 3 → 8	8
Transcript	[1,2,5]	complete	[null,9,null,8]

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Construction and worst-case query each take n work; an update takes constant time. A private n-element array avoids mutating caller storage. Every sum has magnitude at most 3,000,000, safe in Java int and JavaScript Number.

Code

Solution.java

1class NumArray {2    private final int[] values;3    public NumArray(int[] nums) { values = nums.clone(); }4    public void update(int index, int val) { values[index] = val; }5    public int sumRange(int left, int right) {6        int sum = 0;7        for (int i = left; i <= right; i++) sum += values[i];8        return sum;9    }10}

Hints

Hint 1

A point assignment changes every containing sum by the same new-old delta.

Hint 2

Represent a queried interval as reusable tree blocks or a difference of two prefixes.

Hint 3

In a Fenwick Tree convert index to index+1; query prefix(right+1)-prefix(left) and update low-bit ancestors.

Edge Cases

Repeatedly assigning the same value has zero delta, not another addition.
Negative values do not affect the sum-tree invariants.
For left=right, both endpoints refer to the same element.
Non-power-of-two lengths work in both tree layouts.

Common Mistakes and Interview Tips

Adding val rather than val-old corrupts every future Fenwick sum.
Starting a Fenwick update at zero makes its low bit zero and the loop never advances.
Using prefix(right)-prefix(left) omits the inclusive right endpoint.
Recomputing all tree nodes after an update loses the logarithmic guarantee.

Key Takeaway

Mutable aggregates need a representation that limits repair after a point change. Prefix subtraction requires an inverse operation; a Segment Tree can combine blocks even when subtraction is unavailable.