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(logn)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.