De ce contează?
Te uiți într-un arbore genealogic uriaș și cauți, pentru două persoane, cel mai apropiat strămoș pe care îl au în comun — bunicul, străbunicul sau poate un strămoș mult mai vechi. Dacă o persoană e cu câteva generații mai jos decât cealaltă, întâi o „urci” până ajung în aceeași generație, apoi urci amândouă persoanele în paralel, generație cu generație, până dai de același nume. Acel nume este strămoșul comun cel mai apropiat. Asta calculează LCA.
Intuiția
Într-un arbore cu rădăcină, fiecare nod are un singur drum în sus, către
rădăcină. Cel mai apropiat strămoș comun (LCA) al nodurilor u și v este
primul nod în care aceste două drumuri se unesc. Imaginează-ți două degete care
pornesc din u și v și urcă spre rădăcină: în clipa în care ajung pe același
nod, acela e LCA.
Orice metodă de LCA are exact două faze, în această ordine: (1) aliniezi adâncimile — urci nodul mai adânc până ajunge la nivelul celuilalt — apoi (2) urci amândouă nodurile împreună până se întâlnesc. Binary lifting nu schimbă planul, doar comprimă fiecare urcare în salturi pe puteri ale lui 2: în loc de o mie de pași de 1, faci ~10 sărituri — practic „cauți binar” strămoșul.