Binary Lifting
Find ancestors by jumping one step at a time? That's O(n). Binary lifting makes it O(log n).
Lessons
1. Intro
(The goal)
2. The k-th Ancestor Problem
(Find ancestor k steps up)
3. Naive Approach
(Jump one step at a time)
4. Binary Representation Core Idea
(Any number as sum of powers)
5. Sparse Table Idea
(Store power-of-2 ancestors)
6. Table Dimensions
(How many columns needed)
7. Base Case - First Column
(Direct parents)
8. Recurrence Relation
Build from previous
9. Recurrence Example
(How $up[v][2]$ is computed)
10. Quiz: Sparse Table Construction
Knowledge check
11. Building the Table
(Column by column)
12. Building Code
(Pseudocode for preprocessing)
13. Answering Queries
(Decompose k into powers)
14. Query Pseudocode
(Jump by set bits)
15. Query Example
(Finding 13th ancestor)
16. Quiz: Query Decomposition
Knowledge check
17. Complexity Summary
(Preprocessing and queries)
18. Problem - Company Queries I
(CSES 1687 - k-th ancestor)
19. Core Idea - Tree Structure
(Input is a tree)
20. Core Idea - Handling Invalid Queries
(When k exceeds depth)
21. Algorithm
Preprocess then query
22. Company Queries I - Implementation
Binary lifting code
23. Walkthrough
(Sample input trace)
24. Lessons Learned
(What you practiced)
25. Quiz: K-th Ancestor Edge Cases
Knowledge check
26. Extension - LCA
Finding LCA
27. Problem - Company Queries II
(CSES 1688 - LCA)
28. Core Idea - Same Depth First
(Bring nodes to same level)
29. Core Idea - Binary Search for LCA
(Jump both simultaneously)
30. Why This Works
(Jump as far as possible)
31. Algorithm
(LCA with binary lifting)
32. Company Queries II - Implementation
(Pseudocode for LCA)
33. Walkthrough
(Sample LCA trace)
34. Walkthrough - Different Subtrees
(Nodes in separate branches)
35. Lessons Learned
(What you practiced)
36. Quiz: LCA via Binary Lifting
Knowledge check
37. Problem - Kth Ancestor of a Tree Node
(LeetCode 1483)
38. Core Idea - Constructor Preprocessing
(Build table once)
39. Core Idea - Query Method
(Return -1 if out of bounds)
40. Algorithm
(Class-based binary lifting)
41. Kth Ancestor - Implementation
(Pseudocode for class)
42. Walkthrough
(Sample queries)
43. Lessons Learned
(What you practiced)
44. Quiz: Time and Space Tradeoffs
Knowledge check
45. Applications Beyond Ancestors
(Where binary lifting is used)
46. Space Improvement Note
(Reducing memory usage)
47. Comparison to Naive Approach
(Why binary lifting wins)
48. Quiz: Binary Lifting Recurrence
Knowledge check
49. Next Section Teaser
(More LCA techniques)
50. Section Recap
(What you learned)