Pred tým, než začnete študovať tento text je dobré sa uistiť, že viete ako funguje prehľadávanie grafu do hĺbky (DFS).

Najnižší spoločný predok

Úloha, ktorú budeme riešiť, je nasledovná: máme zakorenený strom s $n$ vrcholmi (kde napr. $n=100\,000$) a chceme si niečo šikovné predpočítať a následne vedieť pre ľubovoľné dva vrcholy $x$ a $y$ efektívne nájsť ich najmenšieho spoločného predka (tiež nazývaného najnižší alebo najbližší spoločný predok, least common ancestor, LCA) -- teda taký vrchol $z=lca(x,y)$, ktorý je predkom aj $x$, aj $y$, a spomedzi všetkých takých vrcholov je najhlbšie (teda najbližšie ku $x$ aj $y$).

Skôr, než sa pustíme do riešenia, uveďme stručne, načo je dobré vedieť niečo takéto robiť. LCA je užitočným nástrojom v úlohách, v ktorých máme na vstupe strom (zväčša nejako ováhovaný a nezakorenený) a máme odpovedať na veľa otázok o cestách po tomto strome. Totiž keď si strom zakoreníme, tak platí, že ľubovoľná cesta v ňom ide najskôr "hore" a potom "dole" -- presnejšie, cesta z $x$ do $y$ ide najskôr "hore" z $x$ do $lca(x,y)$ a odtiaľ "dole" do $y$.

Inými slovami, cestu z $x$ do $y$ vieme rozdeliť na dve cesty, ktoré obe idú len "hore": cestu z $x$ do $z$ a cestu z $y$ do $z$. A o takýchto špeciálnych cestách si už často počas prehľadávania do hĺbky vieme predpočítať všetko potrebné.

Ak by nás napríklad zaujímala dĺžka cesty z $x$ do $y$, stačí mať pre každý vrchol predpočítanú jeho vzdialenosť $d$ od koreňa. Potom už vieme v konštantnom čase povedať, že cesta z $x$ do $z$ má dĺžku $d(x)-d(z)$ a cesta z $y$ do $z$ dĺžku $d(y)-d(z)$ -- inými slovami, cesta z $x$ do $y$ má dĺžku $d(x)+d(y)-2d(z)$. Otázky o dĺžke ciest budeme teda vedieť zodpovedať tak rýchlo, ako rýchlo vieme nájsť najbližšieho spoločného predka dvoch vrcholov.

Prvý pokus: čas priamo úmerný počtu hrán na ceste

Asi najjednoduchším spôsobom, ako nájsť $z$ a neprezerať pri tom zbytočné časti stromu, je začať zostrojovať cesty z $x$ aj $y$ dohora.

Môžeme napr. striedavo robiť krok z $x$ a krok z $y$, pričom si značíme už navštívené hodnoty a prestaneme, keď jedna cesta príde do vrcholu, ktorým už prešla druhá.

Ak máme predpočítané hĺbky vrcholov (merané v počte hrán, ignorujúc ich prípadné dĺžky), môžeme toto riešenie implementovať aj v konštantnej pamäti. Kým je jeden z vrcholov $x$ a $y$ hlbšie ako druhý, ten hlbší nahradíme jeho otcom. A potom kým máme dva rôzne vrcholy $x$ a $y$ v rovnakej hĺbke, oba nahradíme ich otcami. Akonáhle dostaneme dvakrát ten istý vrchol, je to zjavne hľadaný vrchol $z$.

Je zjavné, že počet prezretých vrcholov je menej ako dvojnásobkom počtu vrcholov, ktoré skutočne ležia na ceste z $x$ do $y$, a teda je časová zložitosť odpovede na otázku lineárna od dĺžky uvedenej cesty.

Praktické riešenie: $O(n\log n)$ predpočítanie aj pamäť, $O(\log n)$ na otázku

Ak vám stačí v praxi dostatočne efektívne riešenie tejto úlohy, toto je posledná časť tohto receptu, ktorú ešte potrebujete čítať.

Pokúsime sa teraz vymyslieť nejaký rýchlejší spôsob, ako nájsť najbližšieho spoločného predka. Jednou možnosťou, ak by sme ju vedeli realizovať, by bolo binárne vyhľadávanie. Zoberme si cestu z $x$ do koreňa. Najbližší spoločný predok vrcholov $x$ a $y$ určite leží na tejto ceste. A čo viac, má tú vlastnosť, že od neho vyššie sú všetko predkovia vrcholu $y$, zatiaľ čo od neho nižšie to predkovia nie sú.

Aby sme podľa tohto pozorovania vedeli spraviť efektívne riešenie, potrebujeme vedieť efektívne robiť dve veci: Prvou je povedať, či je vrchol $u$ predkom vrcholu $v$. Druhou je k vrcholom $u_1$ a $u_2$ (kde $u_2$ je predok $u_1$) nájsť vrchol, ktorý je na pol ceste medzi nimi.

Pozrime sa najskôr na prvý problém. Pomocou správneho triku vieme tieto otázky zodpovedať veľmi ľahko, dokonca v konštantnom čase. Opäť upravíme úvodné prehľadávanie do hĺbky. Budeme mať jedno globálne počítadlo počtu krokov. Na začiatku ho nastavíme na nulu a vždy, keď prejdeme po hrane (či už dodola alebo späť dohora) jeho hodnotu zvýšime. Pre každý vrchol $v$ si zapamätáme dve hodnoty: čas $s(v)$ jeho objavenia (hodnotu počítadla, keď sme doň prišli) a čas $t(v)$ jeho opustenia (hodnotu, keď z neho odchádzame dohora).

Teraz by malo byť zjavné, že ak $u$ je predkom $v$, tak $s(u) < s(v)$ a zároveň $t(v) < t(u)$. A naopak, ak obe tieto nerovnosti platia, tak $u$ musí byť predkom $v$. Takže pomocou hodnôt $s$ a $t$ vieme v konštantnom čase testovať, či je vrchol $u$ predkom vrcholu $v$.

A čo druhý problém? Nuž, ten tak ľahko riešiť nevieme. Ale ofintíme to trošku ináč. Namiesto klasického binárneho vyhľadávania budeme robiť po strome "skoky", ktorých veľkosti budú mocniny dvojky.

Označme $p_i(x)$ vrchol vo vzdialenosti $2^i$ nad vrcholom $x$. Už vieme, že pre každé $x$ je $p_0(x)=p(x)$. No a ak poznáme všetky hodnoty $p_i(x)$, ľahko spočítame všetky hodnoty $p_{i+1}(x)$: zjavne platí $p_{i+1}(x)=p_i(p_i(x))$. (Slovne: ak chcem vedieť, čo je $2^{i+1}$ krokov nad $x$, pozriem sa, čo je $2^i$ krokov nad $x$, a následne čo je $2^i$ krokov nad dotyčným vrcholom.)

Zjavne žiaden vrchol nemá hĺbku väčšiu ako $n$, preto stačí $\ell=\lceil\log_2 n\rceil$ takýchto fáz. Čas výpočtu týchto údajov je teda $O(n\log n)$, a rovnaké je aj množstvo pamäte, ktorú spotrebujeme.

A ako pomocou týchto údajov nájdeme najbližšieho spoločného predka vrcholov $x$ a $y$? Ak $x$ je predkom $y$, odpoveďou je on. V opačnom prípade sa postupne budeme z $x$ pozerať o $2^{\ell-1},\dots,2^2,2^1,2^0$ krokov dohora. Vždy, keď uvidíme vrchol, ktorý ešte nie je predkom $y$, presunieme $x$ doň (a pokračujeme nasledujúcou veľkosťou kroku). Keď tento proces skončí, nový vrchol $x$ bude zjavne posledným predkom pôvodného $x$, ktorý ešte nie je predkom $y$. Otec tohto nového $x$ je teda odpoveďou, ktorú hľadáme.

Hľadanie minima na intervale v konštantnom čase

Opakujeme ešte raz varovanie: Odtiaľto ďalej nasleduje text, ktorý obsahuje kopec zaujímavej teórie. Ukážeme si v ňom, ako túto úlohu riešiť optimálne. Tieto vylepšenia však v praxi nie sú potrebné -- rozdiel medzi konštantou a logaritmom nás trápi len zriedka.

Tak, slabšie povahy už sú preč a my ostatní sa pustime do ďalšieho kroku.

Opäť raz začneme tým, že sa pozrieme na obyčajné prehľadávanie do hĺbky a zase raz si všimneme niečo ďalšie, čo nám pomôže.

Predstavme si, že vrcholy $x$ a $y$, ktoré nás zaujímajú, poznáme skôr, ako spustíme prehľadávanie. Teraz sa pozerajme na to, ako prehľadávanie do hĺbky beží, a všimnime si dva okamihy: ten, kedy prvýkrát objavíme $x$, a ten, kedy prvýkrát objavíme $y$. Ako spoznať ich najbližšieho spoločného predka $z$? Jednoducho: je to najvyššie položený zo všetkých vrcholov, cez ktoré sme prechádzali medzi objavením $x$ a objavením $y$.

Ako nám toto pozorovanie pomôže? Tak, že našu úlohu "nájsť najbližšieho spoločného predka v strome" prevedieme na jednoduchšiu úlohu "nájsť minimum v danom úseku poľa".

Počas prehľadávania nášho stromu do hĺbky si budeme pamätať hĺbku vrchola, v ktorom práve sme (merané v počte hrán) a vyplníme si dve polia: $K(t)$ bude vrchol, v ktorom sme boli, keď bolo počítadlo krokov na hodnote $t$, a $H(t)$ bude hĺbka dotyčného vrcholu. Navyše si ku každému vrcholu zapamätáme hodnotu počítadla v okamihu, keď sme doň prvýkrát prišli.

Ako teraz budeme hľadať najbližšieho spoločného predka? Na vstupe dostaneme vrcholy $x$ a $y$. Zistíme si časy kedy boli objavené a označíme ich $t_1$ a $t_2$ tak, aby $t_1 \leq t_2$. Teraz už len stačí nájsť také $t$ z intervalu od $t_1$ po $t_2$ vrátane, pre ktoré je hodnota $H(t)$ najmenšia. Potom totiž, ako sme vyššie uviedli, platí $z=K(t)$.

Vo zvyšku tohto vzorového riešenia budeme teda riešiť túto zjednodušenú úlohu: ako v poli $H$ čo najrýchlejšie hľadať takéto minimá.

Prvé lepšie riešenie: len O(n) na predspracovanie

V tomto okamihu vieme spraviť nové riešenie, ktoré je lepšie od toho prechádzajúceho. Toto riešenie potrebuje už len čas a pamäť $O(n)$ na predspracovanie a potom rovnako ako vyššie budeme vedieť v čase $O(\log n)$ zodpovedať každú otázku.

Na toto stačí nad poľom $H$ postaviť intervalový strom, kde si v každom vrchole budeme pamätať index minima v úseku, ktorý danému vrcholu zodpovedá. Tento strom vieme vyrobiť v lineárnom čase a pomocou neho vieme nájsť minimum ľubovoľného úseku v logaritmickom čase.

Druhé lepšie riešenie: odpoveď v konštantnom čase!

Nový trik v tomto riešení: keď hľadáme minimum intervalu a pri tom ho delíme na menšie kusy, tieto menšie kusy nemusia byť disjunktné -- aj keď sa budú prekrývať, všetko bude v poriadku, minimum nemáme ako netrafiť.

Pole $H$, v ktorom chceme hľadať minimá, má dĺžku $2n-1$. Pre jednoduchšie vyjadrovanie označme túto hodnotu $m$.

(Všimnite si, že $n$ a $m$ sú rádovo rovnako veľké. Keď teda budeme napr. hovoriť "lineárny", je jedno, či myslíme závislosť času behu od $n$ alebo od $m$.)

Tiež tu jemne upravme definíciu $\ell$ na $\lfloor \log_2 m\rfloor$.

Pre každé $i$ od 0 do $m-1$ a pre každé $j$ od 0 po $\ell$ spočítame index $I(i,j)$, na ktorom sa nachádza minimum úseku, ktorý začína na pozícii $i$ a má dĺžku $2^j$. Inými slovami, pre každý možný začiatok úseku nájdeme minimum úseku dĺžky 1, 2, 4, 8, atď.

Ako na to? Jednoducho. Na začiatku už priamo vieme tieto hodnoty pre $j=0$, keďže minimom úseku dĺžky 1 je jeho jediný prvok. A akonáhle vieme všetky minimá pre úseky dĺžky $2^j$, ľahko v lineárnom čase spočítame všetky minimá pre úseky dĺžky $2^{j+1}$: Keď chceme zistiť $I(i,j+1)$, stačí sa pozrieť na $a=I(i,j)$ a $b=I(i+2^j,j)$ a porovnať hodnoty $H(a)$ a $H(b)$.

(Slovne: interval dĺžky $2^{j+1}$ jednoducho rozdelíme na dva intervaly dĺžky $2^j$. O každom z nich sme už spočítali, kde má minimum, takže už len stačí tieto dve minimá porovnať.)

No a ako nám tieto údaje pomôžu? Teraz príde k slovu trik, ktorý sme spomínali na začiatku tejto časti. Povedzme napríklad, že potrebujeme nájsť minimum úseku, ktorý začína na pozícii $i$ a má dĺžku 19. Na to sa stačí pozrieť na dva úseky: na úsek začínajúci na pozícii $i$ s dĺžkou 16 a (teraz to príde!) na úsek začínajúci na pozícii $i+(19-16) = i+3$ s dĺžkou 16. Pre oba tieto úseky máme pozíciu minima predpočítanú, a teda všetko potrebné vieme spraviť v konštantnom čase.

Stále druhé riešenie, nechutné technické detaily

Ak ste už uverili, že máme riešenie, ktoré na otázky odpovedá v konštantnom čase, robíte chybu :)

Presnejšie, ešte nám na to chýba jeden krok: ako sa z čísla 19 dopracovať v konštantnom čase k číslu 16? Teda presnejšie, k hodnote $j=4$ takej, že $2^j = 16$? Hodnotu $j$ potrebujeme, aby sme vedeli pozrieť na správne miesto do predpočítanej tabuľky.

Niektoré procesory na takéto operácie majú inštrukcie, takže by sme sa mohli tváriť, že to v konštantnom čase ide. My sme ale frajeri a na takéto sa odvolávať nepotrebujeme -- namiesto toho si to predpočítame!

Ako by vyzeralo pole, kde je ku každej dĺžke úseku napísané to správne $j$? Takto:

dĺžka | 1 2 3 4 5 6 7 8 9 ...
-------------------------
    j | 0 1 1 2 2 2 2 3 3 ...

Hodnota 1 je v ňom $2\times$, hodnota 2 je tam $4\times$, hodnota 3 zase $8\times$, atď. No a takéto pole si ľahko na začiatku vyplníme v lineárnom čase (dva vnorené cykly) a potom sa už doň stačí len pozerať.

Takže zhrnutie tohto riešenia:

• Prehľadávaním do hĺbky v čase $O(n)$ zostrojíme polia $K$ a $H$.
• V čase $O(n)$ predpočítame tabuľku, ktorú sme práve popísali.
• V čase aj pamäti $O(n\log n)$ predpočítame indexy $I(i,j)$, kde sú minimá úsekov dĺžky, ktorá je mocninou dvoch.
• Každú otázku teraz zodpovieme v konštantnom čase tak, že nájdeme správne $j$ a pozrieme sa na nanajvýš dve hodnoty v poli $I(i,j)$.

Kam ďalej?

Už síce vieme hľadať najbližšieho spoločného predka v konštantnom čase, ešte stále to ale nie je dokonalé. Vyššie popísané riešenie má totiž logaritmický faktor navyše v čase predpočítania aj v potrebnej pamäti. Na to, aby sme mali optimálne riešenie, sa potrebujeme aj tých zbaviť.

Toto sem niekto doplní, keď sa mu bude chcieť. Zdroj je mišofov vzorák úlohy KSP27-3-9.