CONCEPT · Candidate Master
Segment tree
also segtree · range tree
A binary tree over the array. Each node combines its interval. Point update and range query walk O(log n) nodes. Works for min, gcd, and other non-invertible ops.
Intuition
Any query interval is a disjoint union of O(log n) nodes you already stored.
When to reach for it
- Range min / gcd / max with updates
- Lazy range-add + range-query
- Walking the tree for 'first index ≥ x'
- CSES Dynamic Range Minimum Queries
Usual pits
- Seeding min with 0 instead of +∞
- Half-open [l,r) vs inclusive [l,r] off-by-one
- Copying a lazy template into a point-update problem
- Using a segtree for static sums — prefixes are enough