Hard · Binary Lifting
Understand → Visualise → Practice.
Preprocess a rooted tree and return the lowest common ancestor for every pair query.
With binary lifting, first raise the deeper node to the same depth, then raise both together by the largest jumps that keep them apart. Their parent is the LCA.
Run DFS or BFS from the root to record each node's parent and depth.
Lift the deeper node by the depth difference, one set bit at a time.
From the largest power down, jump both nodes when their ancestors differ. If they were equal after levelling, that node is the answer; otherwise it is their parent.
O((n + q) log n) time and O(n log n) space.
Lifting both nodes before equalising their depths can skip past the true ancestor.
Read the full guide first: Fenwick Trees and Segment Trees.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.