Graph Theory37 sections · 1633 units
Open in Course

Lessons Learned

(summary)

Euler tour converts subtree problems into range problems. Any subtree query becomes a range query on [tin[v], tout[v]]. This works for sums, min/max, XOR, or any operation a segment tree can handle.

The tree structure is irrelevant after flattening. Time complexity drops from O(n)O(n) per query to O(log⁡n)O(\log n) per query. This pattern appears in many tree problems. If you see a problem asking for repeated subtree queries with point updates, Euler tour is almost always the right approach.