De ce contează?
Ai de mers 37 de stații de metrou. Poți opri în fiecare — 37 de pași — sau observi că 37 = 32 + 4 + 1: iei expresul care sare 32 de stații, apoi unul de 4, apoi mergi o stație. Trei salturi în loc de 37. Binary lifting pregătește exact astfel de „expresuri” pe un arbore: salturi de 1, 2, 4, 8, … strămoși.
Ideea-cheie
Pe un arbore cu rădăcină, „al k-lea strămoș al lui v” e nodul la care ajungi
urcând k muchii de la v spre rădăcină. O interogare se rezolvă naiv urcând
muchie cu muchie — dar problemele dau sute de mii de interogări, pe lanțuri
lungi. Declicul care salvează totul: orice k se scrie în binar ca sumă de
puteri distincte ale lui 2, deci pot înlocui k pași mărunți cu cel mult
log k salturi pregătite dinainte.