MediumArrayBinary Indexed TreeSegment TreeDesign

Range Sum Query - Mutable

1 approach, code in every language

Design a structure over an integer array that supports two operations run in any order and any number of times. The first operation overwrites the value stored at a single position. The second operation reports the total of every value that sits between two indices, inclusive of both ends.

Because updates and range totals can be interleaved thousands of times, a naive re-scan on each query is too slow. The goal is to keep both the point update and the inclusive range total fast, so a Fenwick tree (binary indexed tree) that tracks partial sums is a natural fit.

Example 1

Input: ["NumArray","sumRange","update","sumRange"] [[[1,3,5]],[0,2],[1,2],[0,2]]

Output: [null,9,null,8]

Build over [1,3,5]. sumRange(0,2) adds 1+3+5 = 9. update(1,2) turns the array into [1,2,5]. sumRange(0,2) now adds 1+2+5 = 8.

Example 2

Input: ["NumArray","sumRange","update","update","sumRange"] [[[2,4]],[0,1],[0,3],[1,1],[0,1]]

Output: [null,6,null,null,4]

Build over [2,4]. sumRange(0,1) = 6. update(0,3) gives [3,4], update(1,1) gives [3,1], so sumRange(0,1) = 3+1 = 4.

Constraints

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

Fenwick Tree (Binary Indexed Tree)

Store cumulative partial sums in a Fenwick tree so both a point update and a prefix sum finish in logarithmic time; an inclusive range total is the difference of two prefix sums.

Loading animation…

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

1Keep the raw array plus a tree array of length n+1 (the tree is 1-indexed).
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.
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.
4Answer sumRange(left, right) as prefix(right+1) - prefix(left).
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)

Time

O(log n) per update and per sumRange, O(n log n) to build

Space

O(n)

The tree and the value copy each use n+1 and n slots.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free