Binary Lifting (Kth Ancestor of a Tree Node)
Errichto Algorithms · 18:01
Binary lifting (also called jump pointers) answers "k-th ancestor of node v" queries in O(log n) time. It works by precomputing, for every node, its ancestor 2^j levels up. Any k can then be written as a sum of powers...