\section{Najnižší spoločný predok}

Budeme sa zaoberať hľadaním najnižšieho spoločného predka (lowest common ancestor) dvoch vrcholov v strome. 
Pod označením $z = lca(u,v)$ budeme rozumieť, že $z$ je najnižším spoločným predkom vrcholov $u$ a $v$. 

\begin{figure}[hb]
\centerline{\includegraphics[width=0.5\textwidth]{figures/l09-lca.eps}}
\caption{\label{fig:l09-lca}Strom v preorder očíslovaní}
\end{figure}

\paragraph{}
Na strome na obrázku \ref{fig:l09-lca} vidieť nasledujúce príklady $lca$.\\\\
$lca(2, 4) = 1$\\
$lca(2, 6) = 0$\\
$lca(9, 10) = 9$\\

Triviálnym algoritmom vieme nájsť $lca$ pre ľubovoľné dva vrcholy v čase $O(n)$. 
Stačí sledovať cestu od vrcholov do koreňa a prvý vrchol, ktorý je na oboch cestách spoločný bude $lca$.

Budeme sa zaoberať algoritmom, pomocou ktorého nájdeme $lca$ pre ľubovoľné dva vrcholy v čase $O(1)$, 
pričom na predspracovanie budeme potrebovať čas $O(n)$. Takýto algoritmus vymysleli Harel a Tarjan 1984, neskôr zjednodušili Schieber a Vishkin 1988 a my si ukážeme ešte jednoduchšiu verziu podľa článku Bender a Farach-Coulton (2000).

Prehľadajme strom do hĺbky. Všimnime si prvý moment kedy objavíme vrchol $u$ a prvý moment kedy
objavíme vrchol $v$. Najbližšieho spoločného predka $u, v$ spoznáme jednoducho. Je to najvyššie
položený vrchol spomedzi vrcholov, ktoré sme prechádzali medzi objavením $u$ a $v$.  

Pomocou tejto myšlienky prevedieme úlohu hľadania najbližšieho spoločného predka na inú na prvý
pohľad ľahšiu úlohu.

\medskip
Prehľadajme náš strom do hĺbky. V každom kroku prehľadávania si zapamätáme hĺbku aktuálneho vrchola
$D(t)$ a číslo aktuálneho vrchola $V(t)$. Navyše pre každý vrchol si zapamätáme kedy sme ho prvý
krát objavili (pole $R$).

Nájdenie $lca(u, v)$ bude vyzerať nasledovne. Zistíme kedy boli objavené $u, v$, označme tieto časy 
$t_u, t_v$ (bunv. nech $t_u < t_v$). Teraz nájdeme také $t$ z intervalu $<t_u, t_v>$ aby $D(t)$ bolo
čo najmenšie. Potom $lca(u, v) = V(t)$. Všimnime si, že polia $D, V$ majú dĺžku $2n - 1$, čo je
stále $O(N)$.

Takto sme previedli úlohu hľadanie najbližšieho spoločného predka na úlohu rýchleho hľadania minima
v úseku poľa (range minimum query - RMQ).

Napríklad pre strom na obrázku \ref{fig:l09-lca} dostaneme polia:

\begin{tabular}{c*{21}{@{~~~}c}}
\hline
i:& 0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\
\hline
V:& 0&1&2&1&3&4&3&5&3&1&0&6&7&6&8&6&0&9&10&9&0\\
D:& 0&1&2&1&2&3&2&3&2&1&0&1&2&1&2&1&0&1&2&1&0\\
\hline
R:& 0&1&2&4&5&7&11&12&14&17&18\\
\hline
\end{tabular}


\paragraph{Odpoveď v čase $O(1)$, predspracovanie v čase $O(N \lg N)$:}

Začnime najprv algoritmom, ktorý nám hľadanie minima v úseku poľa umožní v konštantnom čase, ale
ešte nebude mať optimálny čas predspracovania a použitú pamäť.

Majme poľe $A[1..N]$ v ktorom chceme rýchlo vedieť odpovedať na otázky typu:
Aké je minimum z čísel $A[i], A[i+1], \dots, A[j-1]$?

Pre každý prvok poľa $A$ a všetky zmysluplné $k$ si zapamätáme nasledovné minimá:
$$B[i][k] = min (A[i], A[i+1], \dots A[i + 2^k - 1])$$

Týchto hodnôt je $O(N \lg N)$ a spočítať ich vieme v rovnakom čase (treba počítať najprv pre $k =
0$, z nich potom pre $k = 1$, atď).

Odpoveď na otázku: $min (A[i], \dots, A[j-1])$, potom vieme vypočítať nasledovne:

\begin{enumerate}
\item Nájdeme najväčšie $k$ také, že $2^k \leq j - i$.
\item A potom platí:
$$min (A[i], \dots, A[j-1]) = min(min(A[i], \dots, A[i + 2^k - 1]), min(A[j - 2^k], \dots,
A[j-1]))$$
$$min (A[i], \dots, A[j-1]) = min(B[i][k], B[j - 2^k][k])$$
\end{enumerate}

Druhý krok vieme zjavne spraviť v konštantom čase. Na to, aby sme v takomto čase vedeli
spraviť aj prvý krok si potrebujeme príslušné hodnoty $k$ predpočítať (zaberie nám to $O(N)$ pamäte
a rovnako veľa času na predpočítanie).

\paragraph{Vylepšenie na predspracovanie v $O(N)$}

Nasekajme naše pôvodné pole na úseky dĺžky $M$. Potom pri odpovedi na otázku o minime v intervale
$<i, j)$ môžu nastať dva prípady:
buď celý interval leží v tom istom úseku, alebo vieme hľadaný interval rozdeliť na
koniec úseku, kde leží $i$, niekoľko celých úsekov a začiatok úseku, kde leží $j$.

Úplne prvou vecou, čo môžeme spraviť je pre každý úsek spočítať minimum a tieto minimá uložiť do
nového poľa $A'$. Toto vieme spraviť v čase $O(N)$ a nové pole bude mať dĺžku $O(N/M)$.
V tomto poli budeme chcieť opäť hľadať minimum, použijeme na to predspracovanie popisané v
predchádzajúcej časti. Toto predspracovanie bude mať zložitosť $O(N/M lg(N/M))$. 
Ak $M = O(\lg N)$, tak toto predspracovanie má zložitosť lineárnu od $N$.

Ešte ale treba vyriešiť hľadanie minima v úsekoch. Tu si všimnime, že naše pole $D$ v ktorom hľadáme
minimá má jednu špeciálnu vlastnosť: jeho susedné hodnoty sa lišia o $+1$ alebo $-1$.

Zapíšme si každý úsek ako postupnosť $+,-$ (prvý znak môžeme odignorovať) 
podľa toho ako sa daný prvok líši od prechádzajúceho.
Takto dostaneme niekoľko typov úsekov (ak bude $M$ dostatočne malé, tak typov úsekov bude menej ako
počet všetkých úsekov). Pre každý typ a každú dvojicu začiatok, koniec predpočítame pozíciu minima
(tá je jednoznačne určená len z $+,-$). 

Ako vhodná hodnota $M$ sa ukazuje $M = \frac{1}{2} \lg N$. V tomto prípade máme $2^{D-1} = \sqrt{N} /
2$ rôzných úsekov. V každom z nich potrebujeme nájsť odpoveď na $M^2 = \frac{1}{4} \lg^2 N$ otázok.
To celé je teda rádovo $O(\sqrt{N} \lg^2 N)$ hodnôt a v rovnakom čase vieme aj tieto hodnoty
spočítať.

Celý algoritmus sa dá teda zhrnúť nasledovne. Predpočítanie:
\begin{enumerate}
\item Prehľadaj strom do hĺbky a popritom generuj polia $V, D, R$.
\item Nasekaj pole $D$ na úseky dĺžky $M = \frac{1}{2} \lg N$.
\item Pre každý úsek zisti jeho minimum to ulož do poľa $D'$. Nad poľom $D$ predpočítať pole
popísané v predoslej časti.
\item Pre každý úsek zisti jeho typ a pre každý typ predpočítaj príslušné odpovede.
\end{enumerate}

Odpoveď na otázku $lca(u,v)$:
\begin{enumerate}
\item Nájdi v poli $R$ príslušné hodnoty pre $u, v$: $t_u, t_v$.
\item Zisti v ktorých úsekoch sú hodnoty $t_u, t_v$.
\item Zisti príslušné minimum v prvom a poslednom úseku. Pomocou štruktúry z predchádzajúcej časti
zisti minimum z úsekov medzi nimi.
\item Z týchto troch miním vyber najmenšie: $t$.
\item Odpoveď je $V(t)$.
\end{enumerate}
