CONCEPT · Grandmaster
Euler tour
also tree flattening · tin tout
DFS timestamps turn a subtree into a contiguous array segment. Then Fenwick/segtree do subtree updates and queries.
Intuition
You visit a subtree in one uninterrupted interval. Flatten that interval; the tree becomes an array.
When to reach for it
- Subtree sum / min with updates
- O(1) 'is u in v's subtree?'
- CSES Subtree Queries
Usual pits
- Mixing half-open [in,out) with inclusive out
- Path queries need a different flatten (in and out as two events)
- 1-based Fenwick vs 0-based timestamps