Segment Tree

A balanced binary tree over an array that answers range queries and point or range updates in logarithmic time.

The idea

A segment tree stores an associative aggregate (sum, min, max, gcd) for every contiguous segment of an array, arranged so that any query range decomposes into O(log n) canonical segments. Leaves hold single elements; each internal node combines its two children. Building takes O(n); a query or point update takes O(log n).

Range updates with lazy propagation

Kronos motion — operating point

To update an entire range at once, attach a lazy tag to each node recording a pending modification that has not yet been pushed to children. When a query or update descends through a node, its pending tag is applied and propagated downward. This keeps range-add plus range-sum, or range-assign plus range-max, at O(log n) per operation.

Recursive query

python

def query(node, lo, hi, l, r):
    if r < lo or hi < l:
        return IDENTITY          # disjoint
    if l <= lo and hi <= r:
        return tree[node]        # fully covered
    mid = (lo + hi) // 2
    left  = query(2*node,   lo,    mid, l, r)
    right = query(2*node+1, mid+1, hi,  l, r)
    return combine(left, right)

Variants

Iterative bottom-up segment trees cut constant factors for point updates.
Persistent segment trees keep every historical version for O(log n) each, enabling k-th order-statistic queries over ranges.
Segment tree beats handles range-min-assign and range-sum together via a potential argument.
Merge-sort trees store a sorted list per node for range order-statistic counting.

When to prefer it

Choose a segment tree over a Fenwick tree when the aggregate is not easily invertible (min, max, gcd) or when range updates with lazy tags are needed. Fenwick trees are smaller and faster for plain prefix sums.