Problem statement

Given an integer array nums, support two kinds of operation, mixed in any order: changing one element, and asking for the sum of a range. Write the class NumArray:

• NumArray(int[] nums) initialises the object with nums.
• void update(int index, int value) sets nums[index] to value.
• int sumRange(int left, int right) returns nums[left] + nums[left + 1] + … + nums[right].

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input: ["NumArray","sumRange","update","sumRange","sumRange"]
[[[1,3,5]],[0,2],[1,2],[0,2],[1,1]]
Output: [null,9,null,8,2]
Explanation: Initially 1 + 3 + 5 = 9. After `nums[1]` becomes 2 the array is [1,2,5]: the whole sum is 8 and the range [1,1] is 2.

Example 2

Input: ["NumArray","sumRange","update","update","sumRange","sumRange"]
[[[-2,0,3,-5,2]],[1,3],[3,4],[0,100],[0,4],[2,3]]
Output: [null,-2,null,null,109,7]
Explanation: 0 + 3 + (-5) = -2. After the updates the array is [100,0,3,4,2]: it sums to 109, and indices 2–3 to 7.

Constraints

• 1 <= nums.length <= 3 * 10^4
• -100 <= nums[i], value <= 100
• 0 <= index < nums.length
• 0 <= left <= right < nums.length
• At most 3 * 10^4 calls are made to update and sumRange

Hints for Range Sum Query - Mutable

1. Hint 1

   A plain prefix-sum array answers a query in O(1) but an update forces O(n) prefixes to change; a plain array is the other way round. You need both in O(log n).

2. Hint 2

   A Fenwick tree (binary indexed tree) stores partial sums over ranges whose lengths are powers of two, chosen by the lowest set bit of the index.

3. Hint 3

   Keep the current array too: update adds the difference value - nums[index] along i += i & -i, and a prefix sum adds tree[i] along i -= i & -i. Then sumRange(l, r) = prefix(r + 1) - prefix(l).

How to solve Range Sum Query - Mutable

A Fenwick tree keeps, at 1-based position i, the sum of the i & -i elements ending at i. Every prefix splits into O(log n) such blocks, and every element lies in O(log n) of them, so both a point update and a prefix sum take O(log n).

Approach

1. Keep a copy of nums and a tree array of size n + 1, all zero; add every nums[i] at position i + 1.
2. add(i, delta): while i <= n, tree[i] += delta and i += i & -i.
3. prefix(i) (sum of the first i elements): while i > 0, add tree[i] and i -= i & -i.
4. update(index, value): add(index + 1, value - nums[index]), then store nums[index] = value.
5. sumRange(left, right) returns prefix(right + 1) - prefix(left).

Why it works

Stripping the lowest set bit from i repeatedly walks through disjoint blocks that together cover exactly positions 1..i, so prefix adds each element once. Adding the lowest set bit walks upward through exactly the blocks that contain position i, so add changes every stored sum that includes that element and no other.

Complexity

• Time — O(n log n) to build, O(log n) per update and query
• Space — O(n)

Pitfalls

• update sets a value; the tree needs the difference from the old value, so keep the array.
• The tree is 1-based; position 0 would loop forever (0 & -0 = 0).
• A segment tree solves it equally well — the Fenwick tree is just shorter.

Reference solution

Python

from typing import List

class NumArray:

    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.nums = [0] * self.n
        self.tree = [0] * (self.n + 1)
        for i, x in enumerate(nums):
            self.update(i, x)

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

    def _prefix(self, i: int) -> int:
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

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

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

Java

class NumArray {
    private int n;
    private int[] nums, tree;

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

    private void add(int i, int delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }

    private int prefix(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += tree[i];
        return s;
    }

    public void update(int index, int value) {
        add(index + 1, value - nums[index]);
        nums[index] = value;
    }

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

C++

class NumArray {
    int n;
    vector<int> a, tree;

    void add(int i, int delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }

    int prefix(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += tree[i];
        return s;
    }
public:
    NumArray(vector<int>& nums) : n(nums.size()), a(nums.size(), 0), tree(nums.size() + 1, 0) {
        for (int i = 0; i < n; i++) update(i, nums[i]);
    }

    void update(int index, int value) {
        add(index + 1, value - a[index]);
        a[index] = value;
    }

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

JavaScript

var NumArray = function(nums) {
    this.n = nums.length;
    this.nums = [];
    this.tree = [0];
    for (var i = 0; i < this.n; i++) { this.nums.push(0); this.tree.push(0); }
    for (var j = 0; j < this.n; j++) this.update(j, nums[j]);
};

NumArray.prototype.add = function(i, delta) {
    for (; i <= this.n; i += i & -i) this.tree[i] += delta;
};

NumArray.prototype.prefix = function(i) {
    var s = 0;
    for (; i > 0; i -= i & -i) s += this.tree[i];
    return s;
};

NumArray.prototype.update = function(index, value) {
    this.add(index + 1, value - this.nums[index]);
    this.nums[index] = value;
};

NumArray.prototype.sumRange = function(left, right) {
    return this.prefix(right + 1) - this.prefix(left);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium