3 \hyphenation{mikro-strom mikro-stro-mo-vé}
5 \prednaska{9}{Dekompozice stromů}{}
7 V~této kapitole ukážeme několik datových struktur založených
8 na~myšlence dekompozice problému na~dostatečně malé podproblémy,
9 které už umíme (obvykle vhodným kódováním čísly) řešit v~konstantním
12 \h{Union-Find Problem}
14 \s{Problém:} Udržování tříd ekvivalence: na~počátku máme $N$ jednoprvkových ekvivalenčních
15 tříd, provádíme operace \<Find> (zjištění, zda dva prvky jsou ekvivalentní) a \<Union>
16 (sloučení dvou tříd do~jedné). Také na~to lze pohlížet jako na~inkrementální udržování
17 komponent souvislosti neorientovaného grafu: \<Union> je přidání hrany, \<Find> test,
18 zda dva vrcholy leží v~téže komponentě. To se hodí v~mnoha algoritmech, kupříkladu
19 v~Kruskalově algoritmu pro hledání minimální kostry.
21 \s{Triviální řešení:} Prvky každé třídy obarvíme unikátní barvou (identifikátorem
22 třídy). Operace \<Find> porovnává barvy, \<Union> prvky jedné ze~sjednocovaných
25 Operace \<Find> tak pracuje v~konstantním čase, \<Union> může zabrat až lineární čas. Můžeme si
26 pomoci tím, že vždy přebarvíme {\I menší} ze~slučovaných ekvivalenčních tříd (budeme
27 si pro každou třídu pamatovat seznam jejích prvků a velikost). Tehdy může být každý
28 prvek přebarven jen $\O(\log n)$-krát, jelikož každým přebarvením se alespoň zdvojnásobí
29 velikost třídy, ve~které prvek leží. Posloupnost operací \<Union>, kterou vznikla třída
30 velikosti~$k$, tak trvá $\O(k\log k)$, takže můžeme bezpečně prohlásit, že amortizovaná
31 složitost operace \<Union> je $\O(\log n)$.
33 \s{Chytřejší řešení:} Každou třídu budeme reprezentovat zakořeněným stromem s~hranami
34 orientovanými směrem ke~kořeni (jinými slovy pro každý prvek si pamatujeme jeho otce
35 nebo že je to kořen). \<Find> nalezne kořeny stromů a porovná je, \<Union> připojí kořen
36 jedné třídy pod kořen druhé. Aby stromy nedegenerovaly, přidáme dvě pravidla:
39 \:{\I Union dle ranku:} každý kořen $v$ si bude pamatuje svůj rank $r(v)$, což je nějaké
40 přirozené číslo. Na~počátku jsou všechny ranky nulové. Pokud spojujeme
41 dva stromy s~kořeny $v$, $w$ a $r(v)<r(w)$, připojíme $v$ pod~$w$ a rank zachováme.
42 Pokud $r(v)=r(w)$, připojíme libovolně a nový kořen bude mít rank $r(v)+1$.%
43 \foot{Stejně by fungovalo pravidlo {\I Union dle velikosti,} které připojuje menší
44 strom pod větší, ale ranky máme raději, neb jsou skladnější a snáze se analyzují.}
46 \:{\I Komprese cest:} pokud z~vrcholu vystoupíme do~kořene (například
47 během operace \<Find>), přepojíme všechny vrcholy na~cestě, po~které jsme prošli,
51 Pro účely analýzy struktury budeme uvažovat také ranky ostatních vrcholů -- každý vrchol
52 si ponese svůj rank z~doby, kdy byl naposledy kořenem. Struktura se ovšem
53 podle ranků vnitřních vrcholů nijak neřídí a nemusí si je ani pamatovat.
54 Stromu s~kořenem ranku~$r$ budeme zkráceně říkat {\I strom ranku~$r$.}
56 \s{Invariant~C:} Na každé cestě z~vrcholu do~kořene příslušného stromu ranky
57 ostře rostou. Jinými slovy rank vrcholu, který není kořen, je menší, než je rank
61 Na počátku (pro jednovrcholové stromy) tvrzení jistě platí.
62 Nechť provedeme Union, který připojí vrchol~$v$ pod~$w$. Cesty do~kořene z~vrcholů,
63 které ležely pod~$w$, zůstanou zachovány, pouze se vrcholu~$w$ případně
64 zvýší rank. Cesty z~vrcholů pod~$v$ se rozšíří o~hranu~$vw$, na které rank
65 v~každém případě roste.
66 Komprese cest nahrazuje otce vrcholu jeho vzdálenějším předkem, takže se rank
67 otce může jedině zvýšit.
70 \s{Invariant~R:} Strom ranku~$r$ obsahuje alespoň $2^r$ vrcholů.
73 Indukcí podle času. Pro jednovrcholové stromy o~nulovém ranku tvrzení platí.
74 Nechť připojíme vrchol~$v$ pod vrchol~$w$. Je-li $r(v)<r(w)$, rank stromu
75 zůstane zachován a strom se ještě zvětší. Je-li $r(v)=r(w)$, rank stromu
76 se zvětší o~1, ale z~indukce víme, že oba spojované stromy měly alespoň
77 $2^{r(v)}$ vrcholů, takže jejich spojením vznikne strom o~alespoň $2^{r(v)+1}$
78 vrcholech. Komprese cest zasahuje pouze do~vnitřní struktury stromu, ranky
79 ani velikosti stromů nemění.
82 \s{Důsledek:} Rank každého stromu je $\O(\log n)$, takže rank každého vnitřního
83 vrcholu taktéž. Díky invariantu~C strávíme výstupem z~každého vrcholu do~kořene
84 také čas $\O(\log n)$, takže logaritmická je i složitost operací \<Union> a \<Find>.
86 K~tomu nám ovšem stačilo samotné pravidlo Union podle ranku, o~kompresi cest
87 jsme zatím dokázali pouze to, že složitost v~nejhorším případě nezhoršuje.%
88 \foot{Mimochodem, Komprese cest samotná by také na~složitost $\O(\log n)$ amortizovaně stačila \cite{tarjan84setunion}.}
89 Kombinace obou metod se ve~skutečnosti chová mnohem lépe:
91 \s{Věta:} (Tarjan, van Leeuwen \cite{tarjan84setunion})
92 Posloupnost $m$~operací \<Union> a \<Find> provedená na~prázdné struktuře s~$n$ vrcholy
93 trvá $\O(n + m\alpha(m,n))$, kde $\alpha$ je inverzní Ackermannova funkce.%
94 \foot{Je známo \cite{fredman:cellprobe}, že asymptoticky lepší složitosti nelze dosáhnout,
95 a~to ani v~modelu silnějším než RAM. Námi uváděný algoritmus si téměř vystačí
96 s~Pointer Machine, jen porovnávání ranků z~tohoto modelu vybočuje. Složitost
97 operací v~nejhorším případě je obecně horší, je znám dolní odhad $\Omega(\log n/\log\log n)$;
98 více viz Alstrup \cite{alstrup:worstuf}.}
100 Důkaz této věty neuvádíme, jelikož je technicky dosti náročný. Místo toho podobnou
101 metodou ukážeme trochu slabší výsledek s~iterovaným logaritmem:
103 \s{Věta':} Ve~struktuře s~$n$ prvky trvá provedení posloupnosti $m$~operací
104 \<Union> a \<Find> $\O((n+m)\cdot\log^* n)$.
106 \def\up{\mathop{\uparrow}}
108 \s{Definice:} {\I Věžovou funkci} $2\up k$ definujeme následovně: $2\up 0=1$,
109 $2\up (k+1)=2^{2\up k}$.
111 Funkce $2\up k$ je tedy $k$-krát iterovaná mocnina dvojky a $\log^*$ je funkce
112 k~této funkci inverzní.
114 Vrcholy ve~struktuře si nyní rozdělíme podle jejich ranků:
115 $k$-tá skupina bude tvořena těmi vrcholy, jejichž rank je od~$2\up (k-1)+1$ do~$2\up k$. Vrcholy jsou
116 tedy rozděleny do~$1+\log^*\log n$ skupin. Odhadněme nyní shora počet vrcholů v~$k$-té
119 \s{Invariant~S:} V~$k$-té skupině leží nejvýše $n/(2\up k)$ vrcholů.
122 Nejprve ukážeme, že vrcholů s~rankem~$r$ je nejvýše $n/2^r$. Kdybychom nekomprimovali
123 cesty, snadno to plyne z~invariantů~C a~R: každému vrcholu ranku~$r$ přiřadíme všech
124 jeho alespoň $2^r$ potomků. Jelikož ranky na cestách směrem ke~kořeni rostou, žádného
125 potomka jsme nemohli přiřadit více vrcholům. Komprese cest ovšem nemůže invariant
126 porušit, protože nemění ranky ani rozhodnutí, jak proběhne který \<Union>.
128 Teď už stačí odhad $n/2^r$ sečíst přes všechny ranky ve~skupině:
130 {n \over 2^{2\up(k-1)+1}} + {n \over 2^{2\up(k-1)+2}} + \cdots + {n \over 2^{2\up k}} \le
131 {n \over 2^{2\up(k-1)}} \cdot \sum_{i=1}^\infty {1 \over 2^i} =
132 {n \over 2^{2\up(k-1)}} \cdot 1 =
138 Operace \<Union> a \<Find> potřebují nekonstantní čas pouze na~vystoupání
139 po~cestě ze~zadaného vrcholu~$v$ do~kořene stromu. Čas strávený na~této cestě
140 je přímo úměrný počtu hran cesty. Celá cesta je přitom rozpojena a všechny
141 vrcholy ležící na~ní jsou přepojeny přímo pod~kořen stromu.
143 Hrany cesty, které spojují vrcholy z~různých skupin (takových je $\O(\log^* n)$),
144 naúčtujeme právě prováděné operaci. Celkem jimi tedy strávíme čas $\O(m\log^*n)$.
145 Zbylé hrany budeme počítat přes celou dobu běhu algoritmu a účtovat je vrcholům.
147 Uvažme vrchol~$v$ v~$k$-té skupině, jehož rodič leží také v~$k$-té skupině.
148 Jelikož hrany na cestách do~kořene ostře rostou, každým přepojením vrcholu~$v$ rank jeho
149 rodiče vzroste. Proto po nejvýše $2\up k$ přepojeních se bude rodič vrcholu~$v$ nacházet
150 v~některé z~vyšších skupin. Jelikož rank vrcholu~$v$ se už nikdy nezmění, bude hrana z~$v$
151 do~jeho otce již navždy hranou mezi skupinami. Každému vrcholu v~$k$-té skupině tedy naúčtujeme
152 nejvýše $2\up k$ přepojení a jelikož, jak už víme, jeho skupina obsahuje nejvýše $n/(2\up k)$ vrcholů,
153 naúčtujeme celé skupině čas $\O(n)$ a všem skupinám dohromady $\O(n\log^* n)$.
156 \h{Union-Find s~předem známými Uniony}
158 Dále nás bude zajímat speciální varianta Union-Find problému, v~níž dopředu známe
159 posloupnost Unionů, čili strom, který spojováním komponent vznikne.\foot{Kdy se to hodí?
160 Třeba v~Thorupově lineárním algoritmu \cite{thorup:usssp} na~nejkratší cesty nebo
161 ve~Weiheho taktéž lineárním algoritmu \cite{weihe:paths} na~hledání hranově disjunktních
162 cest v~rovinných grafech.}
163 Jiná interpretace téhož (jen pozpátku) je dekrementální udržování komponent
164 souvislosti lesa: na~počátku je dán les, umíme smazat hranu a otestovat, zda jsou
165 dva vrcholy v~témže stromu.
168 který po~počátečním předzpracování v~čase $\O(n)$ zvládne \<Union> i \<Find> v~amortizovaně
169 konstantním čase. Tento algoritmus je kombinací dekompozic popsaných Alstrupem \cite{alstrup97optimal,alstrup98marked}.
171 \s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakořeněný strom $T$ o~$n$ vrcholech
174 \:{\I Kořeny mikrostromů} budou nejvyšší vrcholy v~$T$, pod~nimiž je nejvýše $\log n$ listů
175 a které nejsou kořenem celého~$T$.
176 \:{\I Mikrostromy} leží v~$T$ od~těchto kořenů níže.
177 \:{\I Spojovací hrany} vedou z~kořenů mikrostromů do~jejich otců.
178 \:{\I Makrostrom} je tvořen zbývajícími vrcholy a hranami stromu~$T$.
181 \s{Pozorování:} Každý mikrostrom má nejvýše $\log n$ listů. Pod každým listem makrostromu leží
182 alespoň jeden mikrostrom (může jich být i více, viz dekompozice hvězdy na~obrázku), takže
183 listů makrostromu je nejvýše $n/\log n$.
185 Vnitřních vrcholů makro- i mikrostromů ale může být nešikovně mnoho, protože se ve~stromech mohou
186 vyskytovat dlouhé cesty. Pomůžeme si snadno: každou cestu si budeme pamatovat zvlášť a ve~stromu
187 ji nahradíme hranou, která bude vložena právě tehdy, když budou přítomny všechny hrany cesty.
189 \s{Příklad:} Následující obrázek ukazuje dekompozici několika stromů za~předpokladu,
190 že $\log n=4$. Vrcholy mikrostromů jsou černé, makrostromu bílé. Spojovací hrany kreslíme tečkovaně,
191 hrany komprimovaných cest tučně.
194 \fig{mima.eps}{\epsfxsize}
196 \s{Algoritmus pro cesty:} Cestu délky~$l$ rozdělíme na~úseky délky $\log n$, pro něž si uložíme
197 množiny již přítomných hran (po~bitech jako čísla). Pak si ještě pamatujeme zkomprimovanou cestu (hrany
198 odpovídají úsekům a jsou přítomny právě tehdy, jsou-li přítomny všechny hrany příslušného úseku)
199 délky $l/\log n$ a pro ni \uv{přebarvovací} strukturu pro Union-Find.
201 \>$\<Union>(x,y)$ (přidání hrany $e=xy$ do~cesty):
203 \:Přidáme $e$ do množiny hran přítomných v~příslušném úseku.
204 \:Pokud se tím úsek naplnil, přidáme odpovídající hranu do~zkomprimované cesty.
209 \:Pokud $x$ a $y$ jsou v~témže úseku, otestujeme bitovými operacemi, zda
210 jsou všechny hrany mezi $x$ a $y$ přítomny.
211 \:Pokud jsou v~různých úsecích, rozdělíme cestu z~$x$ do~$y$ na~posloupnost celých úseků,
212 na~které nám odpoví zkomprimovaná cesta, a~dva dotazy v~krajních částečných úsecích.
215 Operace uvnitř úseků pracují v~čase $\O(1)$, operace na~zkomprimované cestě v~$\O(\log l)$
216 amortizovaně, ale za~dobu života struktury je jich $\O(l/\log n)=\O(l/\log l)$, takže celkově zaberou lineární čas.
218 \s{Komprese cest:} Operace na~mikro/makro-stromech budeme následujícím způsobem
219 převádět na~operace s~jejich cestově komprimovanými podobami a na~operace s~cestovými strukturami:
223 \:Pokud $e=xy$ leží uvnitř nějaké cesty, přidáme ji do~cesty, což buďto způsobí
224 přidávání jiné hrany, a~nebo už jsme hotovi.
225 \:Provedeme \<Union> v~komprimovaném stromu.
230 \:Pokud $x$ a $y$ leží uvnitř jedné cesty, zeptáme se cestové struktury a končíme.
231 \:Pokud $x$ leží uvnitř nějaké cesty, zjistíme dotazem na~cestovou strukturu,
232 ke~kterému krajnímu vrcholu cesty je připojen, a~$x$ nahradíme tímto vrcholem.
233 Není-li připojen k~žádnému, je~evidentně odpověď na~celý \<Find> negativní;
234 pokud k~oběma, vybereme si libovolný, protože jsou stejně v~cestově komprimovaném
235 stromu spojeny hranou. Analogicky pro~$y$.
236 \:Zeptáme se struktury pro komprimovaný strom.
239 \s{Algoritmus pro mikrostromy:} Po~kompresi cest má každý mikrostrom nejvýše $2\log n$
240 vrcholů, čili také nejvýše tolik hran. Hrany si očíslujeme přirozenými čísly, každou
241 množinu hran pak můžeme reprezentovat $(2\log n)$-bitovým číslem a množinové operace
242 provádět pomocí bitových v~konstantním čase.
244 Pro každý mikrostrom si předpočítáme pro všechny jeho vrcholy~$v$ množiny~$P_v$ hran ležících
245 na~cestě z~kořene mikrostromu do~$v$. Navíc si budeme pro celý mikrostrom pamatovat množinu
251 \:Najdeme pořadové číslo $i$ hrany $xy$ (máme předpočítané).
252 \:$F \leftarrow F \cup \{i\}$.
258 \:$P \leftarrow P_x \mathop{\Delta} P_y$ (množina hran ležících na~cestě z~$x$ do~$y$).
259 \:Pokud $P\setminus F=\emptyset$, leží $x$ a $y$ ve~stejně komponentě, jinak ne.
262 \s{Algoritmus pro celý problém:} Strom rozložíme na~mikrostromy, makrostrom a spojovací
263 hrany. V~mikrostromech i makrostromu zkomprimujeme cesty. Pro cesty a mikrostromy použijeme
264 výše popsané struktury, pro každou spojovací hranu si budeme pamatovat jen značku,
265 zda je přítomna, a pro makrostrom přebarvovací strukturu.
270 \:Pokud $e=xy$ je spojovací, poznamenáme si, že je přítomna, a~končíme.
271 \:Nyní víme, že $e$ leží uvnitř mikrostromu nebo makrostromu, a~tak provedeme \<Union>
272 na~příslušné struktuře.
278 \:Leží-li $x$ a $y$ v~jednom mikrostromu, zeptáme se struktury pro~mikrostrom.
279 \:Je-li $x$ uvnitř mikrostromu, zeptáme se mikrostruktury na~spojení s~kořenem mikrostromu.
280 Není-li, odpovíme {\sc ne}, stejně jako když není přítomna příslušná spojovací hrana.
281 Jinak $x$ nahradíme listem makrostromu, do~kterého spojovací hrana vede. Podobně pro~$y$.
282 \:Odpovíme podle struktury pro makrostrom.
285 \s{Analýza:} Operace \<Find> trvá konstantní čas, protože se rozloží na~$\O(1)$ \<Find>ů
286 v~dílčích strukturách a každý z~nich trvá konstantně dlouho. Všech $n$ operací \<Union>
287 trvá $\O(n)$, jelikož způsobí $\O(n)$ amortizovaně konstantních operací s~mikrostromy, spojovacími
288 hranami a cestami a $\O(n/\log n)$ operací s~makrostromem, které trvají $\O(\log n)$ amortizovaně
290 \foot{To je v~průměru $\O(1)$ na~operaci a dokonce i amortizovaně, pokud necháme inicializaci
291 struktury, která je lineární, naspořit potenciál $\O(n)$, ze~kterého budeme průběžně platit
292 slučování v~makrostromu.}
294 \s{Cvičení:} Zkuste pomocí dekompozice vyřešit následující problém: je dán strom,
295 jehož každý vrchol může být označený. Navrhněte datovou strukturu, která bude umět
296 v~čase $\O(\log\log n)$ označit nebo odznačit vrchol a v~čase $\O(\log n/\log\log n)$ najít
297 nejbližšího označeného předchůdce.
299 \h{Fredericksonova clusterizace}
301 Mikro/makro-stromová dekompozice není jediný způsob, jak stromy rozkládat. Někdy
302 se více hodí následující myšlenka:
304 \s{Definice:} {\I (Fredericksonova clusterizace)} Nechť $k\ge 1$ je přirozené číslo
305 a $T$~strom s~maximálním stupněm nejvýše~3. Pak $k$-clusterizací stromu~$T$
306 nazveme libovolný rozklad $V_1\cup\ldots\cup V_t$ množiny~$V(T)$, pro který platí:
308 \:Podgrafy stromu~$T$ indukované jednotlivými~$V_i$ jsou souvislé.
309 Těmto podgrafům budeme říkat {\I clustery} a značit je~$C_i$.
310 \:Z~každého clusteru vedou nejvýše 3~hrany do sousedních clusterů.
311 Takovým hranám říkáme {\I vnější,} jejich počet je {\I vnější stupeň} clusteru $\<ed>(C_i)$.
312 Hrany uvnitř clusterů nazveme {\I vnitřní.}
313 \:Nechť $\vert C_i\vert$ značí počet vrcholů clusteru~$C_i$.
314 Pak pro všechny clustery platí $\vert C_i\vert \le k$
315 a pro clustery vnějšího stupně~3 dokonce $\vert C_i\vert = 1$.
316 \:Žádné dva sousední clustery není možné sloučit.
320 Clustery vnějšího stupně~0 se nazývají {\I izolované,}
321 stupně~1 {\I listové,}
322 stupně~2 {\I cestové} a
323 stupně~3 {\I větvicí.}
325 \s{Pozorování:} Nechť $C$ a~$D$ jsou sousední clustery (bez újmy na obecnosti $\<ed>(C) \ge \<ed>(D)$).
326 Kdy je lze sloučit? Především $\vert C\vert + \vert D\vert$ musí být nejvýše rovno~$k$. Pak mohou
327 nastat následující případy:
329 \:Pokud~$C$ i~$D$ jsou listové, lze je sloučit do jednoho izolovaného clusteru.
330 \:Pokud~$C$ je cestový a $D$~listový, lze je sloučit do listového clusteru.
331 \:Pokud~$C$ i~$D$ jsou cestové, lze je sloučit do cestového clusteru.
332 \:Pokud~$C$ je větvicí a $D$~listový, lze je sloučit do cestového clusteru.
333 \:V~ostatních případech slučovat nelze, neboť by vznikl cluster vnějšího stupně~4
334 nebo stupně~3 s~více než jedním vrcholem.
337 \s{Věta:} (Frederickson \cite{frederickson91ambivalent}) Každá $k$-clusterizace stromu~$T$
338 na $n$~vrcholech obsahuje $\O(n/k)$ clusterů.
341 Pokud clusterizace obsahuje pouze izolované nebo listové clustery, pak je konstantně
342 velká a tvrzení triviálně platí.
344 Pokud navíc obsahuje cestové clustery, musí být clustery propojeny do jedné cesty,
345 která začíná a končí listovými clustery a ostatní clustery jsou cestové. Cestové
346 clustery rozdělíme na velké (alespoň $k/2$ vrcholů) a malé (ostatní). Všimneme si,
347 že malé spolu nemohou sousedit. Velkých je přitom nejvýše $n/k$, takže malých
350 Zbývá obecný případ, v~němž jsou i větvicí clustery. Uvažme clusterizační strom~$S$:
351 jeho vrcholy odpovídají clusterům, hrany externím hranám mezi nimi. Tento strom zakořeňme
352 v~libovolném větvicím clusteru.
354 Pokud ve~stromu~$S$ nahradíme každou nevětvící se cestu hranou, vznikne nějaký
355 komprimovaný strom~$S'$. V~něm už jsou pouze listové clustery (coby listy) a
356 větvicí clustery (jako vnitřní vrcholy).
358 Nyní si všimneme, že pro každý list~$\ell$ stromu~$S$ platí, že tento cluster
359 spolu s~cestovými clustery nad ním (které se schovaly do hrany mezi~$\ell$ a jeho
360 otcem) musí mít velikost alespoň~$k$. V~opačném případě by totiž bylo možné
361 tyto clustery společně s~větvicím clusterem nad nimi sloučit do jediného clusteru,
362 což by porušilo poslední podmínku z~definice clusterizace.
364 Proto strom~$S'$ obsahuje nejvýše $n/k$ listů. A~jelikož všechny jeho vnitřní
365 vrcholy mají alespoň~2 syny, musí být vnitřních vrcholů také nanejvýš $n/k$.
367 Zbývá započítat cestové clustery. Uvažme hranu~$e$ stromu~$S'$ a cestové clustery,
368 které se do ní zkomprimovaly. Už víme, že je-li celková velikost těchto clusterů~$r$,
369 může jich být nanejvýš $2r/k + 1$. A~jelikož clustery jsou disjunktní, v~součtu
370 přes všechny hrany~$e$ dostaneme $2n/k + \hbox{počet hran stromu~$S'$} = \O(n/k)$.
372 Clusterů všech typů je tedy dohromady $\O(n/k)$.
375 \s{Věta:} (Frederickson \cite{frederickson91ambivalent}) Pro každé~$k$ lze $k$-clusterizaci
376 stromu o~$n$~vrcholech najít v~čase $\O(n)$.
379 Clusterizaci lze najít upraveným hledáním do hloubky, ale při tom je nutné řešit
380 mnoho různých případů slučování clusterů. Místo toho použijeme následující
383 Nejprve vytvoříme z~každého vrcholu triviální cluster. Taková clusterizace
384 splňuje všechny podmínky kromě poslední. Budeme tedy clustery hladově slučovat.
386 Pořídíme si frontu clusterů, u~nichž jsme ještě nezkontrolovali slučitelnost.
387 Na počátku do ní umístíme všechny clustery. Pak vždy odebereme cluster, prozkoumáme
388 jeho sousedy a pokud mezi nimi je nějaký, s~nímž lze slučovat, tak to provedeme.
389 Nový cluster uložíme do fronty, oba staré z~fronty odstraníme.
391 Všimneme si, že při každé kontrole poklesne velikost fronty o~1 -- buďto jsme
392 neslučovali a zmizel pouze kontrolovaný cluster, anebo slučovali, ale pak zmizely
393 dva clustery a přibyl jeden. Jelikož kontrolu i sloučení zvládneme v~konstantním
394 čase, celý algoritmus doběhne v~čase $\O(n)$.
397 \s{Použití:} Předchozí variantu Union-Find problému bychom také mohli vyřešit nahrazením
398 vrcholů stupně většího než~3 \uv{kruhovými objezdy bez jedné hrany},
399 nalezením $(\log n)$-clusterizace, použitím bitové reprezentace množin uvnitř clusterů
400 a přebarvovací struktury na~hrany mezi clustery.
402 \h{Stromoví předchůdci}
404 \s{Problém:} {\I (Least Common Ancestor alias LCA)} Chceme si předzpracovat zakořeněný strom~$T$
405 tak, abychom dokázali pro libovolné dva vrcholy $x,y$ najít co~nejrychleji jejich nejbližšího
406 společného předchůdce.
408 \s{Triviální řešení LCA:}
410 \:Vystoupáme z~$x$ i $y$ do~kořene, označíme vrcholy na~cestách a kde se poprvé
411 potkají, tam je hledaný předchůdce. To je lineární s~hloubkou a nepotřebuje
413 \:Vylepšení: Budeme stoupat z~$x$ a $y$ střídavě. Tak potřebujeme jen lineárně mnoho
414 kroků vzhledem ke~vzdálenosti společného předchůdce.
415 \:Předpočítáme všechny možnosti: předzpracování $\O(n^2)$, dotaz $\O(1)$.
419 \>Věrni vtipům o~matfyzácích a článku \cite{bender00lca} převedeme raději tento problém na~jiný.
421 \s{Problém:} {\I (Range Minimum Query alias RMQ)} Chceme předzpracovat posloupnost čísel
422 $a_1,\ldots a_n$ tak, abychom uměli rychle počítat $\min_{x\le i\le y} a_i$.%
423 \foot{Všimněte si, že pro sumu místo minima je tento problém velmi snadný.}
425 \s{Lemma:} LCA lze převést na~RMQ s~lineárním časem na~předzpracování a konstantním
426 časem na~převod dotazu.
428 \proof Strom projdeme do~hloubky a pokaždé, když vstoupíme do~vrcholu (ať již poprvé nebo se do~něj vrátíme),
429 zapíšeme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejvyšší vrchol mezi libovolnou
430 návštěvou~$x$ a libovolnou návštěvou~$y$.
433 \s{Triviální řešení RMQ:}
435 \:Předpočítáme všechny možné dotazy: předzpracování $\O(n^2)$, dotaz $\O(1)$.
436 \: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} \}$,
437 čili minima všech bloků velkých jako nějaká mocnina dvojky. Když se poté někdo zeptá
438 na~minimum bloku $a_i,a_{i+1},\ldots,a_{j-1}$, najdeme největší~$k$ takové, že $2^k < j-i$
440 $$\min( \min\{ a_i, \ldots, a_{i+2^k-1} \}, \min\{ a_{j-2^k}, \ldots, a_{j-1} \} ).$$
441 Tak zvládneme dotazy v~čase $\O(1)$ po~předzpracování v~čase $\O(n\log n)$.
444 My si ovšem všimneme, že náš převod z~LCA vytváří dosti speciální instance problému RMQ,
445 totiž takové, v~nichž je $\vert a_i - a_{i+1} \vert = 1$. Takovým instancím budeme
446 říkat RMQ${\pm}1$ a budeme je umět řešit šikovnou dekompozicí.
448 \s{Dekompozice} pro RMQ${\pm}1$: Vstupní posloupnost rozdělíme na~bloky velikosti $b=1/2\cdot \log n$,
449 každý dotaz umíme rozdělit na~část týkající se celých bloků a maximálně dva dotazy na~části bloků.
451 Všimneme si, že ačkoliv bloků je mnoho, jejich možných typů (tj. posloupností klesání
452 a stoupání) je pouze $2^{b-1}\le\sqrt n$ a bloky téhož typu se liší pouze posunutím
453 o~konstantu. Vybudujeme proto kvadratickou strukturu pro jednotlivé typy a pro každý
454 blok si zapamatujeme, jakého je typu a jaké má posunutí. Celkem strávíme čas
455 $\O(n + \sqrt n \cdot \log^2 n) = \O(n)$ předzpracováním a $\O(1)$ dotazem.
457 Mimo to ještě vytvoříme komprimovanou posloupnost, v~níž každý blok nahradíme
458 jeho minimem. Tuto posloupnost délky $n/b$ budeme používat pro části dotazů
459 týkající se celých bloků a připravíme si pro ni \uv{logaritmickou} variantu
460 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í
463 Tak jsme získali algoritmus pro RMQ${\pm}1$ s~konstantním časem na~dotaz po~lineárním
464 předzpracování a výše zmíněným převodem i algoritmus na~LCA se stejnými parametry.
465 Ještě ukážeme, že převod může fungovat i v~opačném směru, a~tak můžeme získat
466 i konstantní/lineární algoritmus pro obecné RMQ.
468 \s{Definice:} {\I Kartézský strom} pro posloupnost $a_1,\ldots,a_n$ je strom,
469 jehož kořenem je minimum posloupnosti, tj. nějaké $a_j=\min_i a_i$, jeho levý podstrom je
470 kartézský strom pro $a_1,\ldots,a_{j-1}$ a pravý podstrom kartézský strom pro $a_{j+1},\ldots,a_n$.
472 \s{Lemma:} Kartézský strom je možné zkonstruovat v~lineárním čase.
474 \proof Použijeme inkrementální algoritmus. Vždy si budeme pamatovat
475 kartézský strom pro již zpracované prvky a pozici posledního zpracovaného
476 prvku v~tomto stromu. Když přidáváme další prvek, hledáme místo, kam ho
477 připojit, od~tohoto označeného prvku nahoru. Povšimněme si, že vzhledem
478 k~potenciálu rovnému hloubce označeného prvku je časová složitost přidání
479 prvku amortizovaně konstantní.
482 \s{Lemma:} RMQ lze převést na~LCA s~lineárním časem na~předzpracování a konstantním
483 časem na~převod dotazu.
485 \proof Sestrojíme kartézský strom a RMQ převedeme na~LCA v~tomto stromu.
488 Výsledky této podkapitoly můžeme shrnout do~následující věty:
490 \s{Věta:} Problémy LCA i RMQ je možné řešit v~konstantním čase na~dotaz
491 po~předzpracování v~lineárním čase.
493 \s{Cvičení:} Vymyslete jednodušší strukturu pro RMQ, víte-li, že všechny dotazy budou na~intervaly stejné délky.