Concepts

A segment tree is a data structure that answers questions about contiguous ranges of an array, such as "what is the sum of elements 3 through 7?" or "what is the minimum in this range?", and keeps those answers fast even while the array keeps changing. This chapter explains why you need one, what it looks like, and the vocabulary used in the rest of the guide.

The problem: queries and updates mixed together

Suppose an array of length n receives a long stream of two kinds of requests:

• Point update: change the value of a[i].
• Range query: return the sum (or minimum, or maximum) of a[l] through a[r-1].

The simplest approach keeps the plain array and loops over the range for every query. Updates cost O(1), but each query costs O(n).

a = [5, 3, 7, 9, 6, 4, 1, 2]

def update(i, value):
    a[i] = value          # O(1)

def query(l, r):
    return sum(a[l:r])    # O(n): adds every element in the range

Prefix sums versus a segment tree

If the values never change, prefix sums are hard to beat. Store in prefix[i] the sum of the first i elements, and any range sum becomes a single subtraction. The catch is that changing one element invalidates every prefix sum after it, so an update costs O(n).

from itertools import accumulate

a = [5, 3, 7, 9, 6, 4, 1, 2]
prefix = [0, *accumulate(a)]   # [0, 5, 8, 15, 24, 30, 34, 35, 37]

def query(l, r):
    return prefix[r] - prefix[l]   # O(1)

def update(i, value):
    diff = value - a[i]
    a[i] = value
    for k in range(i + 1, len(prefix)):   # O(n): fix every later prefix
        prefix[k] += diff

print(query(2, 6))   # 26

Instead of making one operation extremely fast and the other slow, a segment tree makes both operations `O(log n)`. With hundreds of thousands of requests, that is the difference between seconds and hours.

What the tree looks like

A segment tree is a binary tree in which every node is responsible for one range of the array and stores a summary of that range (its sum, minimum, and so on).

• The root covers the whole range [0, n).
• A node covering [lo, hi) splits at the midpoint mid: the left child covers [lo, mid) and the right child covers [mid, hi).
• A leaf covers a range of length 1, that is, a single element.
• An internal node stores the combination of its two children.

Because each split halves the range, the tree has height about log2 n. Any query range can be covered by a handful of disjoint nodes (at most two per level), and changing one element only requires recomputing the single path from that leaf to the root. That is why both operations run in O(log n).

What the combine operation must satisfy

The operation stored in the tree must be associative, and the implementation is cleanest when it also has an identity element. In algebra this structure is called a monoid.

import math

# (combine function, identity)
SUM = (lambda x, y: x + y, 0)
MIN = (min, math.inf)
MAX = (max, -math.inf)
GCD = (math.gcd, 0)
XOR = (lambda x, y: x ^ y, 0)

op, identity = MIN
print(op(op(4, 9), 2) == op(4, op(9, 2)))   # True: associativity
print(op(identity, 7))                      # 7: the identity changes nothing

A question like "what is the median of this range?" does not fit: the parent's answer cannot be computed from the two children's summaries alone, so a basic segment tree cannot answer it.

Vocabulary

• Node and segment: a cell of the tree and the slice of the array it covers.
• Combine (merge): the operation that turns two child values into the parent value.
• Identity: the neutral value returned for nodes outside the query, such as 0 for sums and infinity for minimums.
• Point update and range query: the two operations a basic segment tree supports.
• Range update: a request such as "add 3 to every element in this range", handled with lazy propagation.
• Fenwick tree (binary indexed tree, BIT): a shorter, lighter alternative specialized for invertible operations such as sums.

When to use it

• Array values change often, and range sums, minimums, or maximums are queried in between.
• You repeatedly count "how many elements seen so far are smaller than x" over sorted coordinates.
• A sweep line opens and closes intervals and needs to maintain aggregate state as it moves.

If the values never change, prefix sums or a sparse table are simpler and faster.

Summary

A segment tree stores a summary for every range obtained by repeatedly halving the array, which makes both point updates and range queries O(log n). As long as the combine operation is associative and has an identity, the same structure answers sums, minimums, maximums, GCDs, and more. The next chapter builds a tree by hand and traces queries and updates through it.