Fenwick and segment trees

Use a range-query structure when values change and you still need fast totals, minima, or other summaries over intervals.

Start with a changing total

Index:   0  1  2  3  4
Value:   2  1  4  3  5

sum [1, 4) = 1 + 4 + 3 = 8
set index 2 to 7
sum [1, 4) = 1 + 7 + 3 = 11

The notation [left, right) includes left and excludes right. Its length is right − left. Empty intervals have length zero.

With no updates, prefix sums give O(1) range totals after O(n) construction. But changing index 2 changes every later prefix. Fenwick and segment trees store overlapping summaries so each update repairs only O(log n) entries.

Fenwick tree: store selected prefix blocks

A Fenwick tree, also called a binary indexed tree, uses one-based internal indices. Entry i stores the block ending at i whose length is the lowest set bit of i.

Internal entry: 1     2       3     4             5
Block:          [1]   [1..2]  [3]   [1..4]        [5]
Stored sum:      2     3       4     10            5

prefix of first 5 values: entry 5 + entry 4 = 15
add 3 at array index 2: update entries 3, then 4

To query a prefix, repeatedly subtract the lowest set bit. The selected blocks do not overlap. To update, repeatedly add the lowest set bit, visiting every stored block containing that position.

Point additions and prefix queries take O(log n); range sums subtract two prefix sums. Setting a value requires knowing its old value and adding the difference. Storage is O(n). Repeated insertion builds in O(n log n); a specialized build can take O(n).

Subtraction is essential to this range-sum method. You cannot get a range minimum by subtracting two prefix minima.

Segment tree: combine two children

Values:             2  1  4  3
                        10          [0, 4)
                      /    \
                     3      7
                    / \    / \
                   2   1  4   3     leaves

set index 2 to 7:   leaf 4 -> 7, parent 7 -> 10, root 10 -> 13

Each node summarizes an interval. Its invariant is that its summary equals the combination of its children's summaries. A query uses whole covered intervals and splits partially covered intervals. For [1, 3), combine the leaves holding 1 and 4.

The combine operation must be associative: regrouping cannot change the answer. An identity handles empty contributions, such as 0 for sum or infinity for minimum. Commutativity is not required if left-to-right order is preserved.

Construction takes O(n), point updates and range queries take O(log n), and storage is O(n). A segment tree supports sums, minima, maxima, and custom summaries. Updating an entire interval efficiently needs additional techniques such as lazy propagation; the implementation below supports point updates only.

Choose prefix sums for static sums, Fenwick trees for compact changing sums, and segment trees for more general combinations.

Predict and modify

1. Why are padded leaves zero in this segment tree?
2. What changes when supporting range minimum instead of sum?
3. What if combine is string concatenation?

class Fenwick:
    def __init__(self, values):
        self.n = len(values)
        self.tree = [0] * (self.n + 1)
        for index, value in enumerate(values):
            self.add(index, value)

    def add(self, index, delta):
        index += 1
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index

    def prefix(self, end):
        total = 0
        while end > 0:
            total += self.tree[end]
            end -= end & -end
        return total

    def total(self, left, right):
        return self.prefix(right) - self.prefix(left)


class SegmentSum:
    def __init__(self, values):
        self.base = 1
        while self.base < len(values):
            self.base *= 2
        self.tree = [0] * (2 * self.base)
        for index, value in enumerate(values):
            self.tree[self.base + index] = value
        for index in range(self.base - 1, 0, -1):
            self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]

    def set(self, index, value):
        index += self.base
        self.tree[index] = value
        index //= 2
        while index:
            self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]
            index //= 2

    def total(self, left, right):
        left += self.base
        right += self.base
        total = 0
        while left < right:
            if left % 2:
                total += self.tree[left]
                left += 1
            if right % 2:
                right -= 1
                total += self.tree[right]
            left //= 2
            right //= 2
        return total


values = [2, 1, 4, 3, 5]
fenwick = Fenwick(values)
segment = SegmentSum(values)
assert fenwick.total(1, 4) == segment.total(1, 4) == 8
fenwick.add(2, 3)
segment.set(2, 7)
values[2] = 7
for left in range(len(values) + 1):
    for right in range(left, len(values) + 1):
        expected = sum(values[left:right])
        assert fenwick.total(left, right) == expected
        assert segment.total(left, right) == expected

Apply point updates in Range Sum Query — Mutable.

Next: Bitsets, or return to the data structures guide.