Segment Tree

A binary tree of range sums that answers range queries and single updates in O(log n).

Worth knowing first

Binary Search Tree (BST)

#How does it work?

A segment tree is a binary tree that answers queries such as sum, minimum or maximum over ranges of an array quickly, while still allowing the array to change.

The root covers the whole array, its two children the two halves, their children the quarters; the leaves are single elements. Each node holds the sum of its range.

For a query a[l..r], a node completely inside the range contributes its sum directly, a node completely outside is skipped, and only partly overlapping nodes are split into their children. So every query is answered with about 2·log n nodes at most.

When one element changes, only the nodes on the path from that leaf to the root are recomputed.

#Try it yourself

$ segment_tree --interactive

0–7

0–3

4–7

0–1

2–3

4–5

6–7

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

	0	1	2	3	4	5	6	7
a	5	2	7	3	6	1	4	8

Each node holds the sum of the range in its badge. A range sum is answered by looking at only a few nodes; when one element changes, only the path to the root is updated.

l · new valuer · positionSpeed

VisitingNewRemovingFound / read

#Basic operations

query(l, r): Returns the sum of a[l..r] in O(log n).
update(i, x): Sets a[i] = x and updates the sums on the path in O(log n).
build(a): Builds the tree bottom-up in O(n).
Lazy propagation: An extension that also handles updates to a whole range, such as adding to every element, in O(log n).

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

class SegmentTree:
    """Range sums with point updates; node k covers a range, its children are 2k and 2k + 1."""

    def __init__(self, a: list) -> None:
        self.n = len(a)
        self.sums = [0] * (4 * self.n)
        self._build(1, 0, self.n - 1, a)

    def _build(self, k: int, lo: int, hi: int, a: list) -> None:
        if lo == hi:
            self.sums[k] = a[lo]
            return
        mid = (lo + hi) // 2
        self._build(2 * k, lo, mid, a)
        self._build(2 * k + 1, mid + 1, hi, a)
        self.sums[k] = self.sums[2 * k] + self.sums[2 * k + 1]

    def query(self, l: int, r: int, k: int = 1, lo: int = 0, hi: int = -1) -> int:
        if hi == -1:
            hi = self.n - 1
        if r < lo or hi < l:      # completely outside
            return 0
        if l <= lo and hi <= r:   # completely inside
            return self.sums[k]
        mid = (lo + hi) // 2      # partly: ask both children
        return self.query(l, r, 2 * k, lo, mid) + self.query(l, r, 2 * k + 1, mid + 1, hi)

    def update(self, i: int, x: int, k: int = 1, lo: int = 0, hi: int = -1) -> None:
        if hi == -1:
            hi = self.n - 1
        if lo == hi:
            self.sums[k] = x
            return
        mid = (lo + hi) // 2
        if i <= mid:
            self.update(i, x, 2 * k, lo, mid)
        else:
            self.update(i, x, 2 * k + 1, mid + 1, hi)
        self.sums[k] = self.sums[2 * k] + self.sums[2 * k + 1]


tree = SegmentTree([5, 2, 7, 3, 6, 1, 4, 8])
print(tree.query(2, 5))  # 7 + 3 + 6 + 1
tree.update(5, 10)
print(tree.query(2, 5))  # 7 + 3 + 6 + 10

#Complexity

Operation	Time
Build	O(n)
Range query	O(log n)
Single update	O(log n)
Memory	O(n) (about 2n–4n nodes)

A plain prefix sum array answers queries in O(1) but needs O(n) recomputation on every update. A segment tree does both in O(log n). Instead of sums, any associative operation works: minimum, maximum, gcd and so on.

#When to use it?

Range problems with both queries and updates: live leaderboards, range maximum over time series, region queries in games, sweep-line algorithms in computational geometry and many classic competitive programming problems.

#Practice

Easy

1/3

What does each node of a segment tree hold?

1The sum (or another summary such as min/max) of its range
2A single element only
3The whole array
4The length of its range

1–4 pick · ← → move · enter continue

Medium

1/1

For a = [5, 2, 7, 3, 6, 1, 4, 8], what is the sum of a[2..5] (0-based)?

117
218
323
410

1–4 pick · ← → move · enter continue

Hard

1/1

Why use a segment tree when a prefix sum array exists?

1A prefix array needs O(n) recomputation per update; a segment tree also updates in O(log n)
2A prefix array gives wrong answers
3A segment tree uses less memory
4A prefix array only works on sorted arrays

1–4 pick · ← → move · enter continue

#Up next

Lessons that build on this one:

Fenwick Tree (BIT)