Problem 36.1 · Advanced Data StructuresMedium

Range Sum Query - Mutable

PatternRange Queries (Fenwick & Segment Trees)Combine Structures to Design

What it teaches: A Fenwick tree behind a class: point updates and range sums in O(log n).

Practise it on judges as “Range Sum Query - Mutable”.

In plain words

You keep a list of numbers that keeps changing, and people keep asking for the total of a stretch of it. Adding everything up each time is slow. A Fenwick tree stores sums of blocks of different sizes, so both a change and a total only touch a few blocks.

Return the answers to each sumRange call. Example: NumArray([1, 3, 5]); sumRange(0, 2); update(1, 2); sumRange(0, 2) → 9, 8.

The problem

Design NumArray(int[] nums) with update(index, val) (set nums[index] = val) and sumRange(left, right) (inclusive).

Example 1

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

Constraints

1 ≤ n ≤ 3 × 10⁴
Up to 3 × 10⁴ calls

Pattern clues in the wording

→ Sums with updates interleaved

These clues point to Range Queries (Fenwick & Segment Trees): Answer sums, minimums or counts over any range while the array keeps changing, in O(log n) per query and update.

Stuck? Take one hint at a time

NumArray · starter

class NumArray {
    public NumArray(int[] nums) {}
    public void update(int index, int val) {}
    public int sumRange(int left, int right) { return 0; }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["NumArray","sumRange","update","sumRange"] args = [[[1,3,5]],[0,2],[1,2],[0,2]]	[null,9,null,8]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Fenwick tree · O(log n) per call, O(n log n) build

Fenwick tree

Time O(log n) per call, O(n log n) build Space O(n)

Build by adding each value; update adds (val − old); sumRange = prefix(right) − prefix(left − 1).

▶ Dry run: Fenwick tree (bit) blocksnums = [1, 3, 5]; sumRange(0, 2); update(1, 2); sumRange(0, 2)

bit(map)

bit[1]: 1 (nums[0])bit[2]: 4 (nums[0..1])bit[3]: 5 (nums[2])

Step 1/4Building adds each number into the blocks that cover it. bit[2] covers two numbers, the others cover one.

Approach 1

class NumArray {
    private final int[] nums, bit;

    public NumArray(int[] nums) {
        this.nums = new int[nums.length];
        this.bit = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) update(i, nums[i]);
    }

    public void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        for (int i = index + 1; i < bit.length; i += i & -i) bit[i] += delta;
    }

    public int sumRange(int left, int right) {
        return prefix(right + 1) - prefix(left);
    }

    private int prefix(int i) {                   // sum of the first i elements
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
}

Verdict: Short and fast.

Before you submit

Edge cases and common mistakes

Test these inputs

Single element
Update to the same value

Mistakes people make

Adding val instead of the difference.

Interview

Follow-up questions

What if the queries were range minimum instead of sum?

Command Palette

The problem

Approaches

Fenwick tree

Edge cases and common mistakes

Follow-up questions