---
title: "Segment Tree"
summary: One combining function, three shapes (plain, lazy, persistent), and the invariant that makes every variant obvious.
difficulty: core
tags: [range queries, lazy, structure]
time: log n
space: 4n
prereq: [structures/fenwick]
see: [trees/euler-tour, advanced-tree/hld, structures/sparse-table]
demo: segtree
---

:::definition label="The idea"
Store, for every node $v$ covering a range $[l,r)$, the aggregate of that range. Combine children on the way up, and on a query keep two accumulators (left result, right result) while descending — the result is *not* commutative-safe unless you say so.
:::

```cpp segtree-iterative.cpp
struct Seg {                                   // n = power of two, [l, r)
    int n; vector<ll> t;
    Seg(int m) { n = 1; while (n < m) n *= 2; t.assign(2 * n, 0); }
    void build(const vector<ll>& a) {
        for (int i = 0; i < (int)a.size(); i++) t[n + i] = a[i];
        for (int i = n - 1; i > 0; i--) t[i] = t[2*i] + t[2*i+1];
    }
    void setv(int p, ll x) { for (t[p += n] = x; p > 1; p >>= 1) t[p>>1] = t[2*p] + t[2*p+1]; }
    ll query(int l, int r) {                   // half-open
        ll s = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) s += t[l++];
            if (r & 1) s += t[--r];
        }
        return s;
    }
};
```

:::note title="Why `4n` (or `2·pow2`), and why the iterative version is 2n"
The recursive layout needs up to $4n$ nodes because ranges split unevenly; the bottom-up layout packs a complete tree of `pow2` leaves into $2n$ cells with no gaps. The iterative version is faster (no recursion, no function calls), needs no `build` recursion and no push logic — and it cannot do lazy propagation, which is the only reason to prefer the recursive one.
:::

:::props title="Everything is the same code with a different combine"
| `combine` | query | extra needed |
|---|---|---|
| `+` | range sum | lazy for range add |
| `min` / `max` | range min/max | lazy for range add (shift both) |
| gcd | range gcd | $\gcd(a_l, \text{suffix differences})$ — the standard trick |
| count of ones | "first position with value ≥ x" | descend by comparing $t[2v]$ |
| matrix | linear recurrences | @matrices/recurrences |
| `or` of bitsets | reachability | $O(n^2/64)$ memory, careful |
:::

## Lazy propagation, without the folklore
:::note title="The invariant that makes lazy correct"
`t[v]` is always the correct answer for $v$'s range *as if all pending updates on the path to v were applied*; `lazy[v]` is what still has to be pushed to $v$'s children.
:::

```cpp segtree-lazy.cpp
struct Lazy {
    int n; vector<ll> t, lz;
    Lazy(int m) { n = 1; while (n < m) n *= 2; t.assign(2*n, 0); lz.assign(2*n, 0); }
    void apply(int v, int l, int r, ll x) { t[v] += x * (r - l); if (r - l > 1) lz[v] += x; }
    void push(int v, int l, int r) {
        if (!lz[v]) return;
        int m = (l + r) >> 1;
        apply(2*v, l, m, lz[v]); apply(2*v+1, m, r, lz[v]);
        lz[v] = 0;
    }
    void upd(int v, int l, int r, int ql, int qr, ll x) {
        if (r <= ql || qr <= l) return;
        if (ql <= l && r <= qr) return apply(v, l, r, x), void();
        push(v, l, r);
        int m = (l + r) >> 1;
        upd(2*v, l, m, ql, qr, x); upd(2*v+1, m, r, ql, qr, x);
        t[v] = t[2*v] + t[2*v+1];
    }
    ll ask(int v, int l, int r, int ql, int qr) {
        if (r <= ql || qr <= l) return 0;
        if (ql <= l && r <= qr) return t[v];
        push(v, l, r);
        int m = (l + r) >> 1;
        return ask(2*v, l, m, ql, qr) + ask(2*v+1, m, r, ql, qr);
    }
};
```

:::warning title="The three bugs that actually happen"
1. Forgetting `push` **before descending** in both `upd` and `ask` — the children then answer with stale values while the parent looks right.
2. Applying the update to `t[v]` without multiplying by the length (sum) or by the count of affected elements (chmax/chmin need the "second maximum" trick, not a length).
3. Using one lazy value for two different operations (add and assign): assign must *override*, so `lz` needs a tag type plus a "set" flag, and the ordering is set-then-add, never the reverse.
:::

:::example title="Segment tree beats, in one sentence"
For "range chmin + range sum/max", store max and second-max per node; a `chmin(x)` with second-max $< x \le$ max only touches the top value, so you can update it in $O(1)$ and push lazily — amortised $O(\log^2 n)$ per operation. The general lesson: *store enough auxiliary information that the update becomes trivial at the node*, and prove the amortised bound with a potential (here: how many times a value can be reduced).
:::

:::props title="Three more segment-tree shapes worth owning"
- **merge-sort tree**: each node keeps its sorted array — "count values in $[l,r)$ within $[x,y]$" in $O(\log^2 n)$, static and simple,
- **persistent**: path-copy $O(\log n)$ nodes per update; "k-th smallest in a subarray" and all "offline prefix" queries in $O(\log n)$ with $O(n\log n)$ memory,
- **implicit / dynamic**: build nodes on demand over a range up to $10^9$ — "add interval, query max" with coordinates too large to compress because updates are online.
:::

:::demo id="segtree" caption="Query ranges marked on the tree: exactly the nodes that get `taken`, at most two per level, which is the O(log n) proof in one picture."
:::

:::problems
- [[CSES 1648]] Dynamic Range Sum Queries | https://cses.fi/problemset/task/1648 | easy | point update
- [[CSES 1649]] Dynamic Range Minimum Queries | https://cses.fi/problemset/task/1649 | easy | min, no lazy
- [[CSES 1736]] Polynomial Queries | https://cses.fi/problemset/task/1736 | core | arithmetic-progression lazy
- [[CF 242E]] XOR on Segment | https://codeforces.com/problemset/problem/242/E | core | per-bit lazy
:::