uniolympiads Ελληνικά

Segment tree

Range queries for any associative operation, with point updates or, with lazy propagation, whole-range updates. O(log⁡n)O(\log n) per operation.

When

A Fenwick tree is not enough when the operation has no inverse (minimum, maximum, gcd) or when a node must store something composite, such as "maximum subarray sum".

The idea

A complete binary tree over the array: the leaves are the elements, and each internal node holds the combination of its two children. Any [l,r][l, r] splits into O(log⁡n)O(\log n) nodes, at most two per level.

The first version is iterative, bottom-up: leaves at positions n,…,2n−1n, \dots, 2n-1, the parent of ii is ⌊i/2⌋\lfloor i/2 \rfloor. It works for every nn, not only powers of 2. It keeps two results, left and right, so that it stays correct for non-commutative operations (e.g. function composition).

For a different operation you change only combine and IDENTITY: for sums, 00 and a + b; for maximum, LLONG_MIN and max.

Lazy propagation. When an update covers a whole range ("add vv to [l,r][l, r]"), we do not go down to the leaves. Where a node is covered entirely, we update its sum by v⋅(length)v \cdot (\text{length}) and note in lazy that its children are owed +v+v. The debt is passed to the children (push) only when we need to go down.

Pitfalls

  • The recursive version needs an array of size 4n4n, not 2n2n.
  • Range Updates and Sums also has "set the whole range to vv". Then lazy holds a pair (assign, add), and an assignment cancels any addition below it. The order of application in apply is the whole difficulty.
  • In Hotel Queries you want a position, not a value: "the first room with capacity ≥x\ge x". Walk down from the root, always left if the left child has maximum ≥x\ge x. That is O(log⁡n)O(\log n), not O(log⁡2n)O(\log^2 n) with a binary search on top.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/segment-tree.cpp
// Segment tree, iterative (bottom-up), for any associative operation with an identity.
// Here: point assignment and range minimum on [l, r], 0-indexed. O(log n) per operation.
// Change combine() and IDENTITY for sums, max, gcd, ...

struct SegmentTree {
    static constexpr ll IDENTITY = LLONG_MAX;
    int n;
    vector<ll> t;

    static ll combine(ll a, ll b) {
        return min(a, b);
    }

    SegmentTree(const vector<ll>& a) : n(a.size()), t(2 * a.size(), IDENTITY) {
        for (int i = 0; i < n; i++) {
            t[n + i] = a[i];
        }
        for (int i = n - 1; i >= 1; i--) {
            t[i] = combine(t[2 * i], t[2 * i + 1]);
        }
    }

    void set(int i, ll v) {
        i += n;
        t[i] = v;
        while (i > 1) {
            i /= 2;
            t[i] = combine(t[2 * i], t[2 * i + 1]);
        }
    }

    ll query(int l, int r) {
        ll left = IDENTITY;
        ll right = IDENTITY;
        l += n;
        r += n + 1;
        while (l < r) {
            if (l & 1) {
                left = combine(left, t[l]);
                l++;
            }
            if (r & 1) {
                r--;
                right = combine(t[r], right);
            }
            l /= 2;
            r /= 2;
        }
        return combine(left, right);
    }
};

Tested on 500 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

cpp/lazy-segment-tree.cpp
// Segment tree with lazy propagation: add v to every element of [l, r], sum of [l, r].
// 0-indexed, recursive, O(log n) per operation.
// lazy[node] = value already added to tree[node] but not yet pushed to its children.

struct LazySegmentTree {
    int n;
    vector<ll> tree;
    vector<ll> lazy;

    LazySegmentTree(const vector<ll>& a) : n(a.size()), tree(4 * a.size() + 4, 0), lazy(4 * a.size() + 4, 0) {
        if (n > 0) {
            build(a, 1, 0, n - 1);
        }
    }

    void build(const vector<ll>& a, int node, int l, int r) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(a, 2 * node, l, mid);
        build(a, 2 * node + 1, mid + 1, r);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    void apply(int node, int l, int r, ll v) {
        tree[node] += v * (r - l + 1);
        lazy[node] += v;
    }

    void push(int node, int l, int r) {
        if (lazy[node] != 0) {
            int mid = (l + r) / 2;
            apply(2 * node, l, mid, lazy[node]);
            apply(2 * node + 1, mid + 1, r, lazy[node]);
            lazy[node] = 0;
        }
    }

    void add(int ql, int qr, ll v, int node, int l, int r) {
        if (qr < l || r < ql) {
            return;
        }
        if (ql <= l && r <= qr) {
            apply(node, l, r, v);
            return;
        }
        push(node, l, r);
        int mid = (l + r) / 2;
        add(ql, qr, v, 2 * node, l, mid);
        add(ql, qr, v, 2 * node + 1, mid + 1, r);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    ll sum(int ql, int qr, int node, int l, int r) {
        if (qr < l || r < ql) {
            return 0;
        }
        if (ql <= l && r <= qr) {
            return tree[node];
        }
        push(node, l, r);
        int mid = (l + r) / 2;
        return sum(ql, qr, 2 * node, l, mid) + sum(ql, qr, 2 * node + 1, mid + 1, r);
    }

    void add(int l, int r, ll v) {
        add(l, r, v, 1, 0, n - 1);
    }

    ll sum(int l, int r) {
        return sum(l, r, 1, 0, n - 1);
    }
};

Tested on 500 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.