Algorithms / Euler Tour Subtree Ranges
Least You Need to Know: Euler Tours, Subtree Intervals, and Flattened Trees
An Euler-tour-style entry order can flatten a rooted tree so each subtree becomes a **contiguous interval** in an array. That converts many subtree problems into familiar range-query problems.
The least you need to know
- DFS entry times record when each node is first visited.
- A subtree of node `u` occupies a contiguous interval in entry order.
- Flattening lets Fenwick trees or segment trees answer subtree aggregates.
- Subtree size determines the interval length in simple entry-order flattening.
- Tree-to-array reductions are common preprocessing tricks.
Key notation
tin[u]
entry time of node `u` in DFS order
subtree_size[u]
number of nodes in the subtree rooted at `u`
[tin[u], tin[u] + size[u])
array interval covering the subtree in flattened order
Tiny worked example
- Suppose DFS visits nodes in entry order `1, 2, 4, 5, 3, 6`.
- If node `2` has descendants `4` and `5`, then its subtree occupies the contiguous block `2, 4, 5` in that entry list.
- A subtree-sum query can then become a range-sum query on that block.
- This is why Euler tours pair naturally with Fenwick and segment trees.
Common mistakes
- Students sometimes mix entry times with full walk positions from a different Euler-tour convention.
- The interval formula depends on which flattening variant is used.
- The contiguous-range trick works for rooted subtrees, not arbitrary connected subgraphs.
How to recognize this kind of problem
- A tree problem asks for repeated subtree sums, counts, or updates.
- The solution hints at flattening a tree into an array.
- A later data structure wants contiguous intervals.