Dekompozice: Oprava preklepu v analyze Union-Findu

[ga.git] / 9-decomp / 9-decomp.tex

\input ../sgr.tex

\hyphenation{mikro-strom mikro-stro-mo-vé}

\prednaska{9}{Dekompozice stromù}{}

V~této kapitole uká¾eme nìkolik datových struktur zalo¾ených
na~my¹lence dekompozice problému na~dostateènì malé podproblémy,
které u¾ umíme (obvykle vhodným kódováním èísly) øe¹it v~konstantním
èase.

\h{Union-Find Problem}

\s{Problém:} Udr¾ování tøíd ekvivalence: na~poèátku máme $N$ jednoprvkových ekvivalenèních
tøíd, provádíme operace \<Find> (zji¹tìní, zda dva prvky jsou ekvivalentní) a \<Union>
(slouèení dvou tøíd do~jedné). Také na~to lze pohlí¾et jako na~inkrementální udr¾ování
komponent souvislosti neorientovaného grafu: \<Union> je pøidání hrany, \<Find> test,
zda dva vrcholy le¾í v~té¾e komponentì. To se hodí v~mnoha algoritmech, kupøíkladu
v~Kruskalovì algoritmu pro hledání minimální kostry.

\s{Triviální øe¹ení:} Prvky ka¾dé tøídy obarvíme unikátní barvou (identifikátorem
tøídy). Operace \<Find> porovnává barvy, \<Union> prvky jedné ze~sjednocovaných
tøíd pøebarvuje.

Operace \<Find> tak pracuje v~konstantním èase, \<Union> mù¾e zabrat a¾ lineární èas. Mù¾eme si
pomoci tím, ¾e v¾dy pøebarvíme {\I men¹í} ze~sluèovaných ekvivalenèních tøíd (budeme
si pro ka¾dou tøídu pamatovat seznam jejích prvkù a velikost). Tehdy mù¾e být ka¾dý
prvek pøebarven jen $\O(\log n)$-krát, jeliko¾ ka¾dým pøebarvením se alespoò zdvojnásobí
velikost tøídy, ve~které prvek le¾í. Posloupnost operací \<Union>, kterou vznikla tøída
velikosti~$k$, tak trvá $\O(k\log k)$, tak¾e mù¾eme bezpeènì prohlásit, ¾e amortizovaná
slo¾itost operace \<Union> je $\O(\log n)$.

\s{Chytøej¹í øe¹ení:} Ka¾dou tøídu budeme reprezentovat zakoøenìným stromem s~hranami
orientovanými smìrem ke~koøeni (jinými slovy pro ka¾dý prvek si pamatujeme jeho otce
nebo ¾e je to koøen). \<Find> nalezne koøeny stromù a porovná je, \<Union> pøipojí koøen
jedné tøídy pod koøen druhé. Aby stromy nedegenerovaly, pøidáme dvì pravidla:

\itemize\ibull
\:{\I Union dle ranku:} ka¾dý koøen $v$ si bude pamatuje svùj rank $r(v)$, co¾ je nìjaké
pøirozené èíslo. Na~poèátku jsou v¹echny ranky nulové. Pokud spojujeme
dva stromy s~koøeny $v$, $w$ a $r(v)<r(w)$, pøipojíme $v$ pod~$w$ a rank zachováme.
Pokud $r(v)=r(w)$, pøipojíme libovolnì a nový koøen bude mít rank $r(v)+1$.%
\foot{Stejnì by fungovalo pravidlo {\I Union dle velikosti,} které pøipojuje men¹í
strom pod vìt¹í, ale ranky máme radìji, neb jsou skladnìj¹í a snáze se analyzují.}

\:{\I Komprese cest:} pokud z~vrcholu vystoupíme do~koøene (napøíklad
bìhem operace \<Find>), pøepojíme v¹echny vrcholy na~cestì, po~které jsme pro¹li,
rovnou pod koøen.
\endlist

Pro úèely analýzy struktury budeme uva¾ovat také ranky ostatních vrcholù -- ka¾dý vrchol
si ponese svùj rank z~doby, kdy byl naposledy koøenem. Struktura se ov¹em
podle rankù vnitøních vrcholù nijak neøídí a nemusí si je ani pamatovat.
Stromu s~koøenem ranku~$r$ budeme zkrácenì øíkat {\I strom ranku~$r$.}

\s{Invariant~C:} Na ka¾dé cestì z~vrcholu do~koøene pøíslu¹ného stromu ranky
ostøe rostou. Jinými slovy rank vrcholu, který není koøen, je men¹í, ne¾ je rank
jeho otce.

\proof
Na poèátku (pro jednovrcholové stromy) tvrzení jistì platí.
Nech» provedeme Union, který pøipojí vrchol~$v$ pod~$w$. Cesty do~koøene z~vrcholù,
které le¾ely pod~$w$, zùstanou zachovány, pouze se vrcholu~$w$ pøípadnì
zvý¹í rank. Cesty z~vrcholù pod~$v$ se roz¹íøí o~hranu~$vw$, na které rank
v~ka¾dém pøípadì roste.
Komprese cest nahrazuje otce vrcholu jeho vzdálenìj¹ím pøedkem, tak¾e se rank
otce mù¾e jedinì zvý¹it.
\qed

\s{Invariant~R:} Strom ranku~$r$ obsahuje alespoò $2^r$ vrcholù.

\proof
Indukcí podle èasu. Pro jednovrcholové stromy o~nulovém ranku tvrzení platí.
Nech» pøipojíme vrchol~$v$ pod vrchol~$w$. Je-li $r(v)<r(w)$, rank stromu
zùstane zachován a strom se je¹tì zvìt¹í. Je-li $r(v)=r(w)$, rank stromu
se zvìt¹í o~1, ale z~indukce víme, ¾e oba spojované stromy mìly alespoò
$2^{r(v)}$ vrcholù, tak¾e jejich spojením vznikne strom o~alespoò $2^{r(v)+1}$
vrcholech. Komprese cest zasahuje pouze do~vnitøní struktury stromu, ranky
ani velikosti stromù nemìní.
\qed

\s{Dùsledek:} Rank ka¾dého stromu je $\O(\log n)$, tak¾e rank ka¾dého vnitøního
vrcholu takté¾. Díky invariantu~C strávíme výstupem z~ka¾dého vrcholu do~koøene
také èas $\O(\log n)$, tak¾e logaritmická je i slo¾itost operací \<Union> a \<Find>.

K~tomu nám ov¹em staèilo samotné pravidlo Union podle ranku, o~kompresi cest
jsme zatím dokázali pouze to, ¾e slo¾itost v~nejhor¹ím pøípadì nezhor¹uje.%
\foot{Mimochodem, Komprese cest samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila \cite{tarjan84setunion}.}
Kombinace obou metod se ve~skuteènosti chová mnohem lépe:

\s{Vìta:} (Tarjan, van Leeuwen \cite{tarjan84setunion})
Posloupnost $m$~operací \<Union> a \<Find> provedená na~prázdné struktuøe s~$n$ vrcholy
trvá $\O(n + m\alpha(m,n))$, kde $\alpha$ je inverzní Ackermannova funkce.%
\foot{Je známo \cite{fredman:cellprobe}, ¾e asymptoticky lep¹í slo¾itosti nelze dosáhnout,
a~to ani v~modelu silnìj¹ím ne¾ RAM. Námi uvádìný algoritmus si témìø vystaèí
s~Pointer Machine, jen porovnávání rankù z~tohoto modelu vyboèuje. Slo¾itost
operací v~nejhor¹ím pøípadì je obecnì hor¹í, je znám dolní odhad $\Omega(\log n/\log\log n)$;
více viz Alstrup \cite{alstrup:worstuf}.}

Dùkaz této vìty neuvádíme, jeliko¾ je technicky dosti nároèný. Místo toho podobnou
metodou uká¾eme trochu slab¹í výsledek s~iterovaným logaritmem:

\s{Vìta':} Ve~struktuøe s~$n$ prvky trvá provedení posloupnosti $m$~operací
\<Union> a \<Find> $\O((n+m)\cdot\log^* n)$.

\def\up{\mathop{\uparrow}}

\s{Definice:} {\I Vì¾ovou funkci} $2\up k$ definujeme následovnì: $2\up 0=1$,
$2\up (k+1)=2^{2\up k}$.

Funkce $2\up k$ je tedy $k$-krát iterovaná mocnina dvojky a $\log^*$ je funkce
k~této funkci inverzní.

Vrcholy ve~struktuøe si nyní rozdìlíme podle jejich rankù:
$k$-tá skupina bude tvoøena tìmi vrcholy, jejich¾ rank je od~$2\up (k-1)+1$ do~$2\up k$. Vrcholy jsou
tedy rozdìleny do~$1+\log^*\log n$ skupin. Odhadnìme nyní shora poèet vrcholù v~$k$-té
skupinì.

\s{Invariant~S:} V~$k$-té skupinì le¾í nejvý¹e $n/(2\up k)$ vrcholù.

\proof
Nejprve uká¾eme, ¾e vrcholù s~rankem~$r$ je nejvý¹e $n/2^r$. Kdybychom nekomprimovali
cesty, snadno to plyne z~invariantù~C a~R: ka¾dému vrcholu ranku~$r$ pøiøadíme v¹ech
jeho alespoò $2^r$ potomkù. Jeliko¾ ranky na cestách smìrem ke~koøeni rostou, ¾ádného
potomka jsme nemohli pøiøadit více vrcholùm. Komprese cest ov¹em nemù¾e invariant
poru¹it, proto¾e nemìní ranky ani rozhodnutí, jak probìhne který \<Union>.

Teï u¾ staèí odhad $n/2^r$ seèíst pøes v¹echny ranky ve~skupinì:
$$
{n \over 2^{2\up(k-1)+1}} + {n \over 2^{2\up(k-1)+2}} + \cdots + {n \over 2^{2\up k}} \le
{n \over 2^{2\up(k-1)}} \cdot \sum_{i=1}^\infty {1 \over 2^i} =
{n \over 2^{2\up(k-1)}} \cdot 1 =
{n \over 2\up k}.
$$
\qed

\>{\sl Dùkaz vìty:}
Operace \<Union> a \<Find> potøebují nekonstantní èas pouze na~vystoupání
po~cestì ze~zadaného vrcholu~$v$ do~koøene stromu. Èas strávený na~této cestì
je pøímo úmìrný poètu hran cesty. Celá cesta je pøitom rozpojena a v¹echny
vrcholy le¾ící na~ní jsou pøepojeny pøímo pod~koøen stromu.

Hrany cesty, které spojují vrcholy z~rùzných skupin (takových je $\O(\log^* n)$),
naúètujeme právì provádìné operaci. Celkem jimi tedy strávíme èas $\O(m\log^*n)$.
Zbylé hrany budeme poèítat pøes celou dobu bìhu algoritmu a úètovat je vrcholùm.

Uva¾me vrchol~$v$ v~$k$-té skupinì, jeho¾ rodiè le¾í také v~$k$-té skupinì.
Jeliko¾ hrany na cestách do~koøene ostøe rostou, ka¾dým pøepojením vrcholu~$v$ rank jeho
rodièe vzroste. Proto po nejvý¹e $2\up k$ pøepojeních se bude rodiè vrcholu~$v$ nacházet
v~nìkteré z~vy¹¹ích skupin. Jeliko¾ rank vrcholu~$v$ se u¾ nikdy nezmìní, bude hrana z~$v$
do~jeho otce ji¾ nav¾dy hranou mezi skupinami. Ka¾dému vrcholu v~$k$-té skupinì tedy naúètujeme
nejvý¹e $2\up k$ pøepojení a jeliko¾, jak u¾ víme, jeho skupina obsahuje nejvý¹e $n/(2\up k)$ vrcholù,
naúètujeme celé skupinì èas $\O(n)$ a v¹em skupinám dohromady $\O(n\log^* n)$.
\qed

\h{Union-Find s~pøedem známými Uniony}

Dále nás bude zajímat speciální varianta Union-Find problému, v~ní¾ dopøedu známe
posloupnost Unionù, èili strom, který spojováním komponent vznikne.\foot{Kdy se to hodí?
Tøeba v~Thorupovì lineárním algoritmu \cite{thorup:usssp} na~nejkrat¹í cesty nebo
ve~Weiheho takté¾ lineárním algoritmu \cite{weihe:paths} na~hledání hranovì disjunktních
cest v~rovinných grafech.}
Jiná interpretace tého¾ (jen pozpátku) je dekrementální udr¾ování komponent
souvislosti lesa: na~poèátku je dán les, umíme smazat hranu a otestovat, zda jsou
dva vrcholy v~tém¾e stromu.

Popí¹eme algoritmus,
který po~poèáteèním pøedzpracování v~èase $\O(n)$ zvládne \<Union> i \<Find> v~amortizovanì
konstantním èase. Tento algoritmus je kombinací dekompozic popsaných Alstrupem \cite{alstrup97optimal,alstrup98marked}.

\s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakoøenìný strom $T$ o~$n$ vrcholech
definujeme:
\itemize\ibull
\:{\I Koøeny mikrostromù} budou nejvy¹¹í vrcholy v~$T$, pod~nimi¾ je nejvý¹e $\log n$ listù
a které nejsou koøenem celého~$T$.
\:{\I Mikrostromy} le¾í v~$T$ od~tìchto koøenù ní¾e.
\:{\I Spojovací hrany} vedou z~koøenù mikrostromù do~jejich otcù.
\:{\I Makrostrom} je tvoøen zbývajícími vrcholy a hranami stromu~$T$.
\endlist

\s{Pozorování:} Ka¾dý mikrostrom má nejvý¹e $\log n$ listù. Pod ka¾dým listem makrostromu le¾í
alespoò jeden mikrostrom (mù¾e jich být i více, viz dekompozice hvìzdy na~obrázku), tak¾e
listù makrostromu je nejvý¹e $n/\log n$.

Vnitøních vrcholù makro- i mikrostromù ale mù¾e být ne¹ikovnì mnoho, proto¾e se ve~stromech mohou
vyskytovat dlouhé cesty. Pomù¾eme si snadno: ka¾dou cestu si budeme pamatovat zvlá¹» a ve~stromu
ji nahradíme hranou, která bude vlo¾ena právì tehdy, kdy¾ budou pøítomny v¹echny hrany cesty.

\s{Pøíklad:} Následující obrázek ukazuje dekompozici nìkolika stromù za~pøedpokladu,
¾e $\log n=4$. Vrcholy mikrostromù jsou èerné, makrostromu bílé. Spojovací hrany kreslíme teèkovanì,
hrany komprimovaných cest tuènì.

\medskip
\fig{mima.eps}{\epsfxsize}

\s{Algoritmus pro cesty:} Cestu délky~$l$ rozdìlíme na~úseky délky $\log n$, pro nì¾ si ulo¾íme
mno¾iny ji¾ pøítomných hran (po~bitech jako èísla). Pak si je¹tì pamatujeme zkomprimovanou cestu (hrany
odpovídají úsekùm a jsou pøítomny právì tehdy, jsou-li pøítomny v¹echny hrany pøíslu¹ného úseku)
délky $l/\log n$ a pro ni \uv{pøebarvovací} strukturu pro Union-Find.

\>$\<Union>(x,y)$ (pøidání hrany $e=xy$ do~cesty):
\algo
\:Pøidáme $e$ do mno¾iny hran pøítomných v~pøíslu¹ném úseku.
\:Pokud se tím úsek naplnil, pøidáme odpovídající hranu do~zkomprimované cesty.
\endalgo

\>$\<Find>(x,y):$
\algo
\:Pokud $x$ a $y$ jsou v~tém¾e úseku, otestujeme bitovými operacemi, zda
  jsou v¹echny hrany mezi $x$ a $y$ pøítomny.
\:Pokud jsou v~rùzných úsecích, rozdìlíme cestu z~$x$ do~$y$ na~posloupnost celých úsekù,
  na~které nám odpoví zkomprimovaná cesta, a~dva dotazy v~krajních èásteèných úsecích.
\endalgo

Operace uvnitø úsekù pracují v~èase $\O(1)$, operace na~zkomprimované cestì v~$\O(\log l)$
amortizovanì, ale za~dobu ¾ivota struktury je jich $\O(l/\log n)=\O(l/\log l)$, tak¾e celkovì zaberou lineární èas.

\s{Komprese cest:} Operace na~mikro/makro-stromech budeme následujícím zpùsobem
pøevádìt na~operace s~jejich cestovì komprimovanými podobami a na~operace s~cestovými strukturami:

\>$\<Union>(x,y)$:
\algo
\:Pokud $e=xy$ le¾í uvnitø nìjaké cesty, pøidáme ji do~cesty, co¾ buïto zpùsobí
  pøidávání jiné hrany, a~nebo u¾ jsme hotovi.
\:Provedeme \<Union> v~komprimovaném stromu.
\endalgo

\>$\<Find>(x,y)$:
\algo
\:Pokud $x$ a $y$ le¾í uvnitø jedné cesty, zeptáme se cestové struktury a konèíme.
\:Pokud $x$ le¾í uvnitø nìjaké cesty, zjistíme dotazem na~cestovou strukturu,
  ke~kterému krajnímu vrcholu cesty je pøipojen, a~$x$ nahradíme tímto vrcholem.
  Není-li pøipojen k~¾ádnému, je~evidentnì odpovìï na~celý \<Find> negativní;
  pokud k~obìma, vybereme si libovolný, proto¾e jsou stejnì v~cestovì komprimovaném
  stromu spojeny hranou. Analogicky pro~$y$.
\:Zeptáme se struktury pro komprimovaný strom.
\endalgo

\s{Algoritmus pro mikrostromy:} Po~kompresi cest má ka¾dý mikrostrom nejvý¹e $2\log n$
vrcholù, èili také nejvý¹e tolik hran. Hrany si oèíslujeme pøirozenými èísly, ka¾dou
mno¾inu hran pak mù¾eme reprezentovat $(2\log n)$-bitovým èíslem a mno¾inové operace
provádìt pomocí bitových v~konstantním èase.

Pro ka¾dý mikrostrom si pøedpoèítáme pro v¹echny jeho vrcholy~$v$ mno¾iny~$P_v$ hran le¾ících
na~cestì z~koøene mikrostromu do~$v$. Navíc si budeme pro celý mikrostrom pamatovat mno¾inu
pøítomných hran~$F$.

\>$\<Union>(x,y):$

\algo
\:Najdeme poøadové èíslo $i$ hrany $xy$ (máme pøedpoèítané).
\:$F \leftarrow F \cup \{i\}$.
\endalgo

\>$\<Find>(x,y):$

\algo
\:$P \leftarrow P_x \mathop{\Delta} P_y$ (mno¾ina hran le¾ících na~cestì z~$x$ do~$y$).
\:Pokud $P\setminus F=\emptyset$, le¾í $x$ a $y$ ve~stejnì komponentì, jinak ne.
\endalgo

\s{Algoritmus pro celý problém:} Strom rozlo¾íme na~mikrostromy, makrostrom a spojovací
hrany. V~mikrostromech i makrostromu zkomprimujeme cesty. Pro cesty a mikrostromy pou¾ijeme
vý¹e popsané struktury, pro ka¾dou spojovací hranu si budeme pamatovat jen znaèku,
zda je pøítomna, a pro makrostrom pøebarvovací strukturu.

\>$\<Union>(x,y)$:

\algo
\:Pokud $e=xy$ je spojovací, poznamenáme si, ¾e je pøítomna, a~konèíme.
\:Nyní víme, ¾e $e$ le¾í uvnitø mikrostromu nebo makrostromu, a~tak provedeme \<Union>
   na~pøíslu¹né struktuøe.
\endlist

\>$\<Find>(x,y)$:

\algo
\:Le¾í-li $x$ a $y$ v~jednom mikrostromu, zeptáme se struktury pro~mikrostrom.
\:Je-li $x$ uvnitø mikrostromu, zeptáme se mikrostruktury na~spojení s~koøenem mikrostromu.
  Není-li, odpovíme {\sc ne}, stejnì jako kdy¾ není pøítomna pøíslu¹ná spojovací hrana.
  Jinak $x$ nahradíme listem makrostromu, do~kterého spojovací hrana vede. Podobnì pro~$y$.
\:Odpovíme podle struktury pro makrostrom.
\endalgo

\s{Analýza:} Operace \<Find> trvá konstantní èas, proto¾e se rozlo¾í na~$\O(1)$ \<Find>ù
v~dílèích strukturách a ka¾dý z~nich trvá konstantnì dlouho. V¹ech $n$ operací \<Union>
trvá $\O(n)$, jeliko¾ zpùsobí $\O(n)$ amortizovanì konstantních operací s~mikrostromy, spojovacími
hranami a cestami a $\O(n/\log n)$ operací s~makrostromem, které trvají $\O(\log n)$ amortizovanì
ka¾dá.%
\foot{To je v~prùmìru $\O(1)$ na~operaci a dokonce i amortizovanì, pokud necháme inicializaci
struktury, která je lineární, naspoøit potenciál $\O(n)$, ze~kterého budeme prùbì¾nì platit
sluèování v~makrostromu.}

\s{Cvièení:} Zkuste pomocí dekompozice vyøe¹it následující problém: je dán strom,
jeho¾ ka¾dý vrchol mù¾e být oznaèený. Navrhnìte datovou strukturu, která bude umìt
v~èase $\O(\log\log n)$ oznaèit nebo odznaèit vrchol a v~èase $\O(\log n/\log\log n)$ najít
nejbli¾¹ího oznaèeného pøedchùdce.

\h{Fredericksonova clusterizace}

Mikro/makro-stromová dekompozice není jediný zpùsob, jak stromy rozkládat. Nìkdy
se více hodí následující my¹lenka:

\s{Definice:} {\I (Fredericksonova clusterizace)} Nech» $k\ge 1$ je pøirozené èíslo
a $T$~strom s~maximálním stupnìm nejvý¹e~3. Pak $k$-clusterizací stromu~$T$
nazveme libovolný rozklad $V_1\cup\ldots\cup V_t$ mno¾iny~$V(T)$, pro který platí:
\itemize\ibull
\:Podgrafy stromu~$T$ indukované jednotlivými~$V_i$ jsou souvislé.
Tìmto podgrafùm budeme øíkat {\I clustery} a znaèit je~$C_i$.
\:Z~ka¾dého clusteru vedou nejvý¹e 3~hrany do sousedních clusterù.
Takovým hranám øíkáme {\I vnìj¹í,} jejich poèet je {\I vnìj¹í stupeò} clusteru $\<ed>(C_i)$.
Hrany uvnitø clusterù nazveme {\I vnitøní.}
\:Nech» $\vert C_i\vert$ znaèí poèet vrcholù clusteru~$C_i$.
Pak pro v¹echny clustery platí $\vert C_i\vert \le k$
a pro clustery vnìj¹ího stupnì~3 dokonce $\vert C_i\vert = 1$.
\:®ádné dva sousední clustery není mo¾né slouèit.
\endlist

\s{Úmluva:}
Clustery vnìj¹ího stupnì~0 se nazývají {\I izolované,}
stupnì~1 {\I listové,}
stupnì~2 {\I cestové} a
stupnì~3 {\I vìtvicí.}

\s{Pozorování:} Nech» $C$ a~$D$ jsou sousední clustery (bez újmy na obecnosti $\<ed>(C) \ge \<ed>(D)$).
Kdy je lze slouèit? Pøedev¹ím $\vert C\vert + \vert D\vert$ musí být nejvý¹e rovno~$k$. Pak mohou
nastat následující pøípady:
\itemize\ibull
\:Pokud~$C$ i~$D$ jsou listové, lze je slouèit do jednoho izolovaného clusteru.
\:Pokud~$C$ je cestový a $D$~listový, lze je slouèit do listového clusteru.
\:Pokud~$C$ i~$D$ jsou cestové, lze je slouèit do cestového clusteru.
\:Pokud~$C$ je vìtvicí a $D$~listový, lze je slouèit do cestového clusteru.
\:V~ostatních pøípadech sluèovat nelze, nebo» by vznikl cluster vnìj¹ího stupnì~4
  nebo stupnì~3 s~více ne¾ jedním vrcholem.
\endlist

\s{Vìta:} (Frederickson \cite{frederickson91ambivalent}) Ka¾dá $k$-clusterizace stromu~$T$
na $n$~vrcholech obsahuje $\O(n/k)$ clusterù.

\proof
Pokud clusterizace obsahuje pouze izolované nebo listové clustery, pak je konstantnì
velká a tvrzení triviálnì platí.

Pokud navíc obsahuje cestové clustery, musí být clustery propojeny do jedné cesty,
která zaèíná a konèí listovými clustery a ostatní clustery jsou cestové. Cestové
clustery rozdìlíme na velké (alespoò $k/2$ vrcholù) a malé (ostatní). V¹imneme si,
¾e malé spolu nemohou sousedit. Velkých je pøitom nejvý¹e $n/k$, tak¾e malých
nejvý¹e $n/k+1$.

Zbývá obecný pøípad, v~nìm¾ jsou i vìtvicí clustery. Uva¾me clusterizaèní strom~$S$:
jeho vrcholy odpovídají clusterùm, hrany externím hranám mezi nimi. Tento strom zakoøeòme
v~libovolném vìtvicím clusteru.

Pokud ve~stromu~$S$ nahradíme ka¾dou nevìtvící se cestu hranou, vznikne nìjaký
komprimovaný strom~$S'$. V~nìm u¾ jsou pouze listové clustery (coby listy) a
vìtvicí clustery (jako vnitøní vrcholy).

Nyní si v¹imneme, ¾e pro ka¾dý list~$\ell$ stromu~$S$ platí, ¾e tento cluster
spolu s~cestovými clustery nad ním (které se schovaly do hrany mezi~$\ell$ a jeho
otcem) musí mít velikost alespoò~$k$. V~opaèném pøípadì by toti¾ bylo mo¾né
tyto clustery spoleènì s~vìtvicím clusterem nad nimi slouèit do jediného clusteru,
co¾ by poru¹ilo poslední podmínku z~definice clusterizace.

Proto strom~$S'$ obsahuje nejvý¹e $n/k$ listù. A~jeliko¾ v¹echny jeho vnitøní
vrcholy mají alespoò~2 syny, musí být vnitøních vrcholù také nanejvý¹ $n/k$.

Zbývá zapoèítat cestové clustery. Uva¾me hranu~$e$ stromu~$S'$ a cestové clustery,
které se do ní zkomprimovaly. U¾ víme, ¾e je-li celková velikost tìchto clusterù~$r$,
mù¾e jich být nanejvý¹ $2r/k + 1$. A~jeliko¾ clustery jsou disjunktní, v~souètu
pøes v¹echny hrany~$e$ dostaneme $2n/k + \hbox{poèet hran stromu~$S'$} = \O(n/k)$.

Clusterù v¹ech typù je tedy dohromady $\O(n/k)$.
\qed

\s{Vìta:} (Frederickson \cite{frederickson91ambivalent}) Pro ka¾dé~$k$ lze $k$-clusterizaci
stromu o~$n$~vrcholech najít v~èase $\O(n)$.

\proof
Clusterizaci lze najít upraveným hledáním do hloubky, ale pøi tom je nutné øe¹it
mnoho rùzných pøípadù sluèování clusterù. Místo toho pou¾ijeme následující
hladový algoritmus.

Nejprve vytvoøíme z~ka¾dého vrcholu triviální cluster. Taková clusterizace
splòuje v¹echny podmínky kromì poslední. Budeme tedy clustery hladovì sluèovat.

Poøídíme si frontu clusterù, u~nich¾ jsme je¹tì nezkontrolovali sluèitelnost.
Na poèátku do ní umístíme v¹echny clustery. Pak v¾dy odebereme cluster, prozkoumáme
jeho sousedy a pokud mezi nimi je nìjaký, s~ním¾ lze sluèovat, tak to provedeme.
Nový cluster ulo¾íme do fronty, oba staré z~fronty odstraníme.

V¹imneme si, ¾e pøi ka¾dé kontrole poklesne velikost fronty o~1 -- buïto jsme
nesluèovali a zmizel pouze kontrolovaný cluster, anebo sluèovali, ale pak zmizely
dva clustery a pøibyl jeden. Jeliko¾ kontrolu i slouèení zvládneme v~konstantním
èase, celý algoritmus dobìhne v~èase $\O(n)$.
\qed

\s{Pou¾ití:} Pøedchozí variantu Union-Find problému bychom také mohli vyøe¹it nahrazením
vrcholù stupnì vìt¹ího ne¾~3 \uv{kruhovými objezdy bez jedné hrany},
nalezením $(\log n)$-clusterizace, pou¾itím bitové reprezentace mno¾in uvnitø clusterù
a pøebarvovací struktury na~hrany mezi clustery.

\h{Stromoví pøedchùdci}

\s{Problém:} {\I (Least Common Ancestor alias LCA)} Chceme si pøedzpracovat zakoøenìný strom~$T$
tak, abychom dokázali pro libovolné dva vrcholy $x,y$ najít co~nejrychleji jejich nejbli¾¹ího
spoleèného pøedchùdce.

\s{Triviální øe¹ení LCA:}
\itemize\ibull
\:Vystoupáme z~$x$ i $y$ do~koøene, oznaèíme vrcholy na~cestách a kde se poprvé
  potkají, tam je hledaný pøedchùdce. To je lineární s~hloubkou a nepotøebuje
  pøedzpracování.
\:Vylep¹ení: Budeme stoupat z~$x$ a $y$ støídavì. Tak potøebujeme jen lineárnì mnoho
  krokù vzhledem ke~vzdálenosti spoleèného pøedchùdce.
\:Pøedpoèítáme v¹echny mo¾nosti: pøedzpracování $\O(n^2)$, dotaz $\O(1)$.
\:\dots\ co dál?
\endlist

\>Vìrni vtipùm o~matfyzácích a èlánku \cite{bender00lca} pøevedeme radìji tento problém na~jiný.

\s{Problém:} {\I (Range Minimum Query alias RMQ)} Chceme pøedzpracovat posloupnost èísel
$a_1,\ldots a_n$ tak, abychom umìli rychle poèítat $\min_{x\le i\le y} a_i$.%
\foot{V¹imnìte si, ¾e pro sumu místo minima je tento problém velmi snadný.}

\s{Lemma:} LCA lze pøevést na~RMQ s~lineárním èasem na~pøedzpracování a konstantním
èasem na~pøevod dotazu.

\proof Strom projdeme do~hloubky a poka¾dé, kdy¾ vstoupíme do~vrcholu (a» ji¾ poprvé nebo se do~nìj vrátíme),
zapí¹eme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejvy¹¹í vrchol mezi libovolnou
náv¹tìvou~$x$ a libovolnou náv¹tìvou~$y$.
\qed

\s{Triviální øe¹ení RMQ:}
\itemize\ibull
\:Pøedpoèítáme v¹echny mo¾né dotazy: pøedzpracování $\O(n^2)$, dotaz $\O(1)$.
\:Pro ka¾dé $i$ a $j\le \log n$ pøedpoèítáme $m_{ij} = \min\{ a_i, a_{i+1}, \ldots, a_{i+2^j-1} \}$,
èili minima v¹ech blokù velkých jako nìjaká mocnina dvojky. Kdy¾ se poté nìkdo zeptá
na~minimum bloku $a_i,a_{i+1},\ldots,a_{j-1}$, najdeme nejvìt¹í~$k$ takové, ¾e $2^k < j-i$
a vrátíme:
$$\min( \min\{ a_i, \ldots, a_{i+2^k-1} \}, \min\{ a_{j-2^k}, \ldots, a_{j-1} \} ).$$
Tak zvládneme dotazy v~èase $\O(1)$ po~pøedzpracování v~èase $\O(n\log n)$.
\endlist

My si ov¹em v¹imneme, ¾e ná¹ pøevod z~LCA vytváøí dosti speciální instance problému RMQ,
toti¾ takové, v~nich¾ je $\vert a_i - a_{i+1} \vert = 1$. Takovým instancím budeme
øíkat RMQ${\pm}1$ a budeme je umìt øe¹it ¹ikovnou dekompozicí.

\s{Dekompozice} pro RMQ${\pm}1$: Vstupní posloupnost rozdìlíme na~bloky velikosti $b=1/2\cdot \log n$,
ka¾dý dotaz umíme rozdìlit na~èást týkající se celých blokù a maximálnì dva dotazy na~èásti blokù.

V¹imneme si, ¾e aèkoliv blokù je mnoho, jejich mo¾ných typù (tj. posloupností klesání
a stoupání) je pouze $2^{b-1}\le\sqrt n$ a bloky tého¾ typu se li¹í pouze posunutím
o~konstantu. Vybudujeme proto kvadratickou strukturu pro jednotlivé typy a pro ka¾dý
blok si zapamatujeme, jakého je typu a jaké má posunutí. Celkem strávíme èas
$\O(n + \sqrt n \cdot \log^2 n) = \O(n)$ pøedzpracováním a $\O(1)$ dotazem.

Mimo to je¹tì vytvoøíme komprimovanou posloupnost, v~ní¾ ka¾dý blok nahradíme
jeho minimem. Tuto posloupnost délky $n/b$ budeme pou¾ívat pro èásti dotazù
týkající se celých blokù a pøipravíme si pro ni \uv{logaritmickou} variantu
triviální struktury. To nás bude stát $\O(n/b\cdot\log (n/b))=\O(n/\log n\cdot\log n)=\O(n)$ na~pøedzpracování
a $\O(1)$ na~dotaz.

Tak jsme získali algoritmus pro RMQ${\pm}1$ s~konstantním èasem na~dotaz po~lineárním
pøedzpracování a vý¹e zmínìným pøevodem i algoritmus na~LCA se stejnými parametry.
Je¹tì uká¾eme, ¾e pøevod mù¾e fungovat i v~opaèném smìru, a~tak mù¾eme získat
i konstantní/lineární algoritmus pro obecné RMQ.

\s{Definice:} {\I Kartézský strom} pro posloupnost $a_1,\ldots,a_n$ je strom,
jeho¾ koøenem je minimum posloupnosti, tj. nìjaké $a_j=\min_i a_i$, jeho levý podstrom je
kartézský strom pro $a_1,\ldots,a_{j-1}$ a pravý podstrom kartézský strom pro $a_{j+1},\ldots,a_n$.

\s{Lemma:} Kartézský strom je mo¾né zkonstruovat v~lineárním èase.

\proof Pou¾ijeme inkrementální algoritmus. V¾dy si budeme pamatovat
kartézský strom pro ji¾ zpracované prvky a pozici posledního zpracovaného
prvku v~tomto stromu. Kdy¾ pøidáváme dal¹í prvek, hledáme místo, kam ho
pøipojit, od~tohoto oznaèeného prvku nahoru. Pov¹imnìme si, ¾e vzhledem
k~potenciálu rovnému hloubce oznaèeného prvku je èasová slo¾itost pøidání
prvku amortizovanì konstantní.
\qed

\s{Lemma:} RMQ lze pøevést na~LCA s~lineárním èasem na~pøedzpracování a konstantním
èasem na~pøevod dotazu.

\proof Sestrojíme kartézský strom a RMQ pøevedeme na~LCA v~tomto stromu.
\qed

Výsledky této podkapitoly mù¾eme shrnout do~následující vìty:

\s{Vìta:} Problémy LCA i RMQ je mo¾né øe¹it v~konstantním èase na~dotaz
po~pøedzpracování v~lineárním èase.

\s{Cvièení:} Vymyslete jednodu¹¹í strukturu pro RMQ, víte-li, ¾e v¹echny dotazy budou na~intervaly stejné délky.

\references
\bye