Segment and Fenwick Trees

Suppose these two operations are performed repeatedly on an array of measurements: ask for the sum of the values in a given range, and update a single value. If both happen often, none of the structures covered so far give a good answer.

Two Extreme Solutions

Raw array. An update is a single write: $O(1)$. A range sum, however, walks every element in the range: $O(n)$.

Prefix-sum array. If the running totals from the start are precomputed, the sum of any range is the difference of two values: $O(1)$. In exchange, when a single value changes, every prefix sum after it must be recomputed: $O(n)$.

measurements = [12, 18, 7, 25, 14, 30]

prefix_sums = [0] * (len(measurements) + 1)
for i, value in enumerate(measurements):
    prefix_sums[i + 1] = prefix_sums[i] + value

print(prefix_sums)                # [0, 12, 30, 37, 62, 76, 106]
print(prefix_sums[4] - prefix_sums[1])        # 50   — range 1..3: 18 + 7 + 25

Both solutions make one operation constant and the other linear. If both happen often, neither is sufficient; what is needed is a structure that makes both operations logarithmic.

The Segment Tree

A segment tree divides the array in half, recursively: the root represents the whole array, its children represent its halves, and their children represent quarters. Every node stores a summary of its own range — here, its sum.

                [0..5] = 106
             /                \
        [0..2] = 37        [3..5] = 69
        /      \            /       \
   [0..1]=30  [2..2]=7  [3..4]=39  [5..5]=30
    /    \                 /   \
 [0]=12 [1]=18         [3]=25 [4]=14

A query expresses the requested range as a union of nodes in the tree. Any range can be covered with at most $O(\log n)$ nodes; this is the source of the query cost.

An update changes the relevant leaf and recomputes every summary along the path from the leaf to the root — again $O(\log n)$.

class SegmentTree:
    """Range sum query and point update; both O(log n)."""

    def __init__(self, data: list[int]) -> None:
        self._n = len(data)
        self._tree = [0] * (2 * self._n)          # leaves occupy the second half
        for i, value in enumerate(data):
            self._tree[self._n + i] = value
        for i in range(self._n - 1, 0, -1):       # internal nodes, bottom-up
            self._tree[i] = self._tree[2 * i] + self._tree[2 * i + 1]

    def update(self, index: int, value: int) -> None:
        i = self._n + index
        self._tree[i] = value
        i //= 2
        while i >= 1:                             # refresh summaries up to the root
            self._tree[i] = self._tree[2 * i] + self._tree[2 * i + 1]
            i //= 2

    def range_sum(self, left: int, right: int) -> int:
        """Sum of the half-open range [left, right)."""
        result = 0
        l, r = self._n + left, self._n + right
        while l < r:
            if l % 2 == 1:                        # left bound is a right child: take it
                result += self._tree[l]
                l += 1
            if r % 2 == 1:                        # right bound is a right child: take it
                r -= 1
                result += self._tree[r]
            l //= 2
            r //= 2
        return result


tree = SegmentTree([12, 18, 7, 25, 14, 30])
print(tree.range_sum(0, 6))          # 106  — whole array
print(tree.range_sum(1, 4))          # 50   — 18 + 7 + 25
tree.update(2, 100)                  # 7 becomes 100
print(tree.range_sum(1, 4))          # 143
print(tree.range_sum(0, 6))          # 199

The generality of the structure stands out: the combining operation can be maximum, minimum, greatest common divisor, or any operation with the associative property, instead of sum. Only the summary stored in the nodes and the combining line change.

The Fenwick Tree

A Fenwick tree (binary indexed tree) is a more compact structure concerned only with prefix sums. It does the same job with a single array of $n$ slots; it uses half the memory of a segment tree, and its code is noticeably shorter.

The idea is that each index stores the sum of a specific range, and the length of that range is determined by the lowest set bit in the index’s binary representation. The x & -x idiom from the How Computers Work course is used directly here.

class FenwickTree:
    """Prefix sum and point update; O(log n)."""

    def __init__(self, size: int) -> None:
        self._tree = [0] * (size + 1)            # 1-based index

    def add(self, index: int, increment: int) -> None:
        i = index + 1
        while i < len(self._tree):
            self._tree[i] += increment
            i += i & -i                          # next responsible index

    def prefix_sum(self, index: int) -> int:
        """Sum of the range [0, index)."""
        result, i = 0, index
        while i > 0:
            result += self._tree[i]
            i -= i & -i                          # drop the lowest set bit
        return result

    def range_sum(self, left: int, right: int) -> int:
        return self.prefix_sum(right) - self.prefix_sum(left)


fenwick = FenwickTree(6)
for i, value in enumerate([12, 18, 7, 25, 14, 30]):
    fenwick.add(i, value)

print(fenwick.prefix_sum(6))            # 106
print(fenwick.range_sum(1, 4))          # 50
fenwick.add(2, 93)                      # 7 + 93 = 100
print(fenwick.range_sum(1, 4))          # 143

The Fenwick tree takes updates as an increment; to set a value directly, the difference from the old value is added. This follows from the structure’s prefix-sum-oriented design.

Which Structure, When

Structure	Range query	Point update	Memory	Generality
Raw array	$O(n)$	$O(1)$	$n$	Full
Prefix-sum array	$O(1)$	$O(n)$	$n$	Sum only
Segment tree	$O(\log n)$	$O(\log n)$	$2n$	Any associative operation
Fenwick tree	$O(\log n)$	$O(\log n)$	$n$	Sum and operations with an inverse

Selection criteria:

• If the data does not change, a prefix-sum array is best; no extra structure is needed.
• If only the total is queried, Fenwick is sufficient: less memory, shorter code.
• If operations without an inverse, such as minimum or maximum, or range updates are needed, a segment tree is used.

An extension of the segment tree makes range updates logarithmic as well: the update is not propagated downward immediately but is kept at the node as a “pending change” and applied only once that subtree is descended into. This technique is covered in advanced algorithm topics.

Uses

Range queries are a common need for systems that work with time series and ordered data: the sum or maximum of measurements in a time interval, the number of records in a given range of a ranking, counting objects in a region of a game world.

If the data does not change, the same questions are answered with precomputed summaries; the reason these structures exist is that the data keeps changing.

Summary

• A raw array makes updates constant, and a prefix-sum array makes queries constant; if both are needed often, neither is sufficient.
• A segment tree divides the array in half and stores a summary of each subrange at every node; query and update are $O(\log n)$.
• Any range can be covered with at most a logarithmic number of nodes.
• By changing the combining operation, the same structure is used for minimum, maximum, or other associative operations.
• A Fenwick tree is concerned only with prefix sums; it gives the same cost with half the memory and shorter code.
• The reason these structures exist is that the data changes; for static data, precomputed summaries suffice.

Next Step

Range queries were one-dimensional: indices sat on a line. If positional data has two or more dimensions — points on a map, records in a feature space — how does the splitting idea extend? The next lesson covers this topic’s final structure: multidimensional trees.