Range Sum Query - Mutable

Intuition

A binary indexed tree lets every position be reached by peeling off the lowest set bit of its index, so each node quietly owns a contiguous block of the array. When one value changes we only bump the O(log n) nodes whose blocks cover it, and when we want a prefix total we only add up the O(log n) nodes that tile the range from the front. Keeping a separate copy of the raw values lets us compute the delta (new minus old) on an update, which is exactly what the tree needs to stay consistent.

Algorithm walkthrough

1. 1Keep the raw array plus a tree array of length n+1 (the tree is 1-indexed).
2. 2To update position i, compute delta = val - old value, save the new value, then walk i+1, i+1 + lowbit, ... up to n, adding delta to each node.
3. 3To get the prefix sum up to a 1-based index, start there and repeatedly subtract the lowest set bit, accumulating tree values until you reach 0.
4. 4Answer sumRange(left, right) as prefix(right+1) - prefix(left).
5. 5Seed the tree during construction by calling update on every original element starting from zeros.

Implementation

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, v in enumerate(nums):
            self.update(i, v)

    def update(self, index: int, val: int) -> None:
        delta = val - self.nums[index]
        self.nums[index] = val
        i = index + 1
        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 sumRange(self, left: int, right: int) -> int:
        return self._prefix(right + 1) - self._prefix(left)