214. Range Sum Query - Mutable

Prefix sums make queries O(1) but updates O(n). A Fenwick tree balances both to O(log n): it stores partial sums over power-of-two ranges so a point update and a prefix query each touch only O(log n) nodes.

Why not plain prefix sums?

A prefix-sum array gives O(1) queries but an update forces rebuilding O(n) suffix prefixes. With interleaved updates and queries, use a Fenwick tree (BIT) so both operations are O(log n).

The Fenwick tree

Each BIT index i stores the sum of a range ending at i whose length is the lowest set bit of i. Two O(log n) operations:

update(i, delta):  i++; while i <= n: tree[i] += delta; i += i & (-i)
query(i):          # prefix sum of first i elements
    r = 0; while i > 0: r += tree[i]; i -= i & (-i); return r

Wrap them:

• update(index, val): apply delta = val - current[index], then remember current[index] = val.
• sumRange(l, r) = query(r + 1) - query(l).

Worked example

nums = [1, 3, 5].

• sumRange(0, 2) = 1 + 3 + 5 = 9.
• update(1, 2): nums becomes [1, 2, 5].
• sumRange(0, 2) = 1 + 2 + 5 = 8.

Complexity

• Time: O(log n) per update and per query.
• Space: O(n).

import java.util.*;

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

    public NumArray(int[] nums) {
        this.n = nums.length;
        this.nums = new int[n];
        this.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 += 1; i <= n; i += i & (-i)) tree[i] += delta;
    }

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

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

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