Segment Trees

Build, point update, range query, iterative segment tree, recursive segment tree, lazy propagation, range assignment/addition, custom node merging, coordinate compression, and iterative versus recursive implementation.

Lazy propagation

A segment tree stores an aggregate for each node's interval. With lazy propagation, a range update marks a whole node with a pending tag instead of visiting every leaf; the tag is pushed to the children only when a later operation needs to go below that node.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Each operation visits O(log n) nodes: at most two partially covered nodes per level. Any associative merge works — sums, minimums, gcds, matrix products, “maximum subarray sum” nodes storing four values — as long as the tag composes with itself and with the aggregate.

#include <bits/stdc++.h>
using namespace std;

// range add, range sum and range min, recursive with lazy tags
struct SegTree {
    int n; vector<long long> sum, mn, lazy;
    explicit SegTree(const vector<long long>& a) : n((int)a.size()), sum(4 * n), mn(4 * n), lazy(4 * n, 0) { build(1, 0, n, a); }
    void build(int x, int l, int r, const vector<long long>& a) {
        if (r - l == 1) { sum[x] = mn[x] = a[l]; return; }
        int m = (l + r) / 2; build(2 * x, l, m, a); build(2 * x + 1, m, r, a); pull(x);
    }
    void pull(int x) { sum[x] = sum[2 * x] + sum[2 * x + 1]; mn[x] = min(mn[2 * x], mn[2 * x + 1]); }
    void apply(int x, int l, int r, long long v) { sum[x] += v * (r - l); mn[x] += v; lazy[x] += v; }
    void push(int x, int l, int r) {
        if (!lazy[x]) return;
        int m = (l + r) / 2; apply(2 * x, l, m, lazy[x]); apply(2 * x + 1, m, r, lazy[x]); lazy[x] = 0;
    }
    void add(int ql, int qr, long long v, int x, int l, int r) {          // [ql, qr)
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr) { apply(x, l, r, v); return; }             // fully covered: tag and stop
        push(x, l, r); int m = (l + r) / 2;
        add(ql, qr, v,
…

sum/min of [1,5): 18 / 1
after adding 10 to [2,7): sum/min of [1,5) = 48 / 3
30000 random range-adds and queries match a brute-force array

Advanced variants

Persistent segment trees, dynamic/sparse segment trees, merge-sort trees, segment tree beats overview, 2D segment trees, and segment tree on trees.

Each variant must state its supported operation, update model, complexity, and limitations.

Iterative (bottom-up) point update, range query O(log n), small constants lazy ranges are awkward Dynamic / sparse huge index range (10¹⁸) with few touched positions

O(log U) per op, nodes created on demand memory grows with updates query any past version

O(log n) time and new nodes per update memory O(n + q log n) count of values ≤ x in a range O(log² n) per query Segment tree beats range chmin/chmax with sums amortized O(log² n) complex to implement O(n²) memory if dense

Quiz

? What does a lazy tag represent?
+ An update applied to a node's whole interval but not yet pushed to its children :: Pushed only when an operation goes deeper.
- A deleted node :: No.
- A cached query answer :: No.
- An error flag :: No.

? Why does a range operation touch only O(log n) nodes?
+ At each level at most two nodes are partially covered; fully covered nodes stop the recursion. :: The rest is pruned.
- The tree has log n nodes. :: It has about 2n.
- Because of lazy tags only. :: Queries without updates are O(log n) too.
- It touches O(n). :: Not with pruning.

? Which variant answers queries about earlier versions of the array?
+ Persistent segment tree :: Path copying keeps old roots valid.
- Lazy segment tree :: Only the current version.
- Fenwick tree :: Current version only.
- Sparse table :: Static data.