Euler Tour Technique
Flatten trees into arrays. Subtrees become ranges. Query and update subtrees with range structures.
Lessons
1. Intro
(Converting trees to arrays)
2. What is an Euler Tour
(DFS traversal order)
3. Entry and Exit Times
(tin and tout arrays)
4. Subtrees as Ranges
(Why this works)
5. Flattening the Tree
(Building the array)
6. Basic Implementation
(Computing tin and tout)
7. Example Tree
(Computing times step by step)
8. Quiz: Entry and Exit Times
Knowledge check
9. Check Your Understanding
(Entry/exit time properties)
10. Problem - Subtree Queries
(CSES 1137)
11. Core Idea - Subtree to Range
(The key observation)
12. Core Idea - Which Times to Use
(Entry times only)
13. Algorithm
(Euler tour plus segment tree)
14. Subtree Queries - Implementation
(Code and submit)
15. Subtree Queries - Walkthrough
(Example execution)
16. Lessons Learned
(summary)
17. Quiz: Subtree as Range
Knowledge check
18. Euler Tour Variants
(Different approaches)
19. Entry-Only Variant
(Just tin values)
20. Entry-Exit Variant
(tin and tout pairs)
21. Full Tour Variant
(Complete node sequence)
22. Quiz: Euler Tour Variants
Knowledge check
23. Check Your Understanding
(Variant selection)
24. Problem - Path Queries
(CSES 1138)
25. Core Idea - Path as Prefix
(DFS order property)
26. Core Idea - Prefix Sum Trick
(Converting to range query)
27. Algorithm
(Modified Euler tour)
28. Path Queries - Implementation
(BIT for prefix sums)
29. Path Queries - Walkthrough
(Example execution)
30. Lessons Learned
Adding and subtracting
31. Quiz: Path Query Updates
Knowledge check
32. Combining with Segment Trees
(Beyond sums)
33. BIT as Lighter Alternative
(When to use Fenwick tree)
34. Space Complexity
(Memory usage)
35. Update Types
(Point vs range updates)
36. Query Types
(What you can ask)
37. Ancestor Check
(Fast relationship test)
38. Rerooting Limitation
(Fixed root only)
39. Check Your Understanding
(Complexity analysis)
40. DFS Order Matters
(Consistent traversal)
41. Quiz: Ancestor Check
Knowledge check
42. Connection to Heavy-Light Decomposition
Different tools, same goal
43. Practical Tips
(Implementation advice)
44. Common Mistakes
(What goes wrong)
45. Problem - Company Queries II
(CSES 1688)
46. Core Idea - LCA via Euler Tour
(RMQ on depth array)
47. Algorithm
(Full tour plus RMQ)
48. Company Queries II - Implement Solution
(Submit your code)
49. Lessons Learned
(Full tour power)
50. Quiz: Combining with Data Structures
Knowledge check
51. Section Recap
(What you learned)