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 by rank:} ka¾dý koøen $v$ si pamatuje svùj rank $r(v)$. Na~poèátku
40 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 by size,} 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 Path compression:} 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 \s{Pozorování:} Samotné pravidlo Union by rank zajistí, ¾e strom ranku $r$ bude
52 mít hloubku nejvý¹e $r$ a minimálnì $2^r$ vrcholù, tak¾e èasová slo¾itost operací
53 bude omezena $\O(\log n)$ v~nejhor¹ím pøípadì.%
54 \foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila. \cite{tarjan84setunion}}
56 Amortizovanì se ale popsaná struktura chová daleko lépe:
58 \s{Vìta:} (Tarjan, van Leeuwen \cite{tarjan84setunion}) Kombinace Union by rank a Path compression vede k~amortizované
59 slo¾itosti obou operací $\O(\alpha(n))$, kde $\alpha$ je inverzní Ackermannova funkce.%
60 \foot{Existuje varianta tohoto algoritmu, která dosahuje stejné slo¾itosti i v~nejhor¹ím
61 pøípadì; té¾ je známo, ¾e asymptoticky lep¹í slo¾itosti nelze dosáhnout.}
63 Dùkaz této vìty neuvádíme, jeliko¾ je technicky dosti nároèný, ale naznaèíme alespoò,
64 ¾e amortizovaná èasová slo¾itost je omezena iterovaným logaritmem, konkrétnì ¾e
65 ve~struktuøe s~$n$ prvky trvá provedení $\ell$~operací Union a Find $\O((n+\ell)\cdot\log^* n)$.
67 \def\up{\mathop{\uparrow}}
69 \s{Definice:} {\I Vì¾ovou funkci} $2\up k$ definujeme následovnì: $2\up 0=1$,
70 $2\up (k+1)=2^{2\up k}$.
72 Funkce $2\up k$ je tedy $k$-krát iterovaná mocnina dvojky a $\log^*$ je funkce
73 k~této funkci inverzní.
75 Vrcholy ve~struktuøe si nyní rozdìlíme podle jejich rankù (vrchol, který ji¾ není
76 koøenem, si pamatuje svùj poslední rank z~doby, kdy je¹tì koøenem byl):
77 $k$-tá skupina bude tvoøena tìmi vrcholy, jejich¾ rank je od~$2\up (k-1)+1$ do~$2\up k$. Vrcholy jsou
78 tedy rozdìleny do~$1+\log^*\log n$ skupin. Odhadnìme nyní shora poèet vrcholù v~$k$-té
79 skupinì, vyu¾ívajíce toho, ¾e vrcholù s~rankem~$r$ je nejvý¹e~$n/2^r$:
81 {n \over 2^{2\up(k-1)+1}} + {n \over 2^{2\up(k-1)+2}} + \cdots + {n \over 2^{2\up k}} \le
82 {n \over 2^{2\up(k-1)}} \cdot \sum_{i=1}^\infty {1 \over 2^i} =
83 {n \over 2^{2\up(k-1)}} \cdot 1 =
87 Operace Union a Find potøebují nekonstantní èas pouze na~vystoupání ze~zadaného vrcholu~$v$ do~koøene stromu
88 a tento èas je pøímo úmìrný poètu hran na~cestì z~$v$ do~koøene. Tato cesta je následnì rozpojena a v¹echny
89 vrcholy le¾ící na~ní jsou pøepojeny pøímo pod~koøen stromu. Hrany cesty, které spojují vrcholy z~rùzných
90 skupin (takových je jistì $\O(\log^* n)$), naúètujeme právì provádìné operaci, tak¾e
91 jimi celkem strávíme èas $\O(\ell\log^*n)$. Zbylé hrany budeme poèítat pøes celou dobu bìhu
92 algoritmu a úètovat je vrcholùm.
94 Uva¾me vrchol~$v$ v~$k$-té skupinì, který ji¾ není koøenem stromu. Hrana z~$v$ do~jeho rodièe
95 bude úètována vrcholu~$v$ pouze tehdy, le¾í-li rodiè také v~$k$-té skupinì. Jen¾e
96 ranky vrcholù na~cestì z~libovolného vrcholu do~koøene ostøe rostou, tak¾e pøi ka¾dém pøepojení
97 rank rodièe vrcholu~$v$ vzroste, a~proto po~$2\up k$ pøepojeních bude rodiè vrcholu~$v$ v~$(k+1)$-ní
98 nebo vy¹¹í skupinì. Ka¾dému vrcholu v~$k$-té skupinì tedy úètujeme nejvý¹e $2\up k$ pøepojení
99 a jeliko¾, jak u¾ víme, jeho skupina obsahuje nejvý¹e $n/(2\up k)$ vrcholù, naúètujeme
100 celé skupinì èas $\O(n)$ a v¹em skupinám dohromady $\O(n\log^* n)$.
102 \h{Union-Find s~pøedem známými Uniony}
104 Dále nás bude zajímat speciální varianta Union-Find problému, v~ní¾ dopøedu známe
105 posloupnost Unionù, èili strom, který spojováním komponent vznikne.\foot{Kdy se to hodí?
106 Tøeba v~Thorupovì lineárním algoritmu \cite{thorup:usssp} na~nejkrat¹í cesty nebo
107 ve~Weiheho takté¾ lineárním algoritmu \cite{weihe:paths} na~hledání hranovì disjunktních
108 cest v~rovinných grafech.}
109 Jiná interpretace tého¾ (jen pozpátku) je dekrementální udr¾ování komponent
110 souvislosti lesa: na~poèátku je dán les, umíme smazat hranu a otestovat, zda jsou
111 dva vrcholy v~tém¾e stromu.
114 který po~poèáteèním pøedzpracování v~èase $\O(n)$ zvládne \<Union> i \<Find> v~amortizovanì
115 konstantním èase. Tento algoritmus je kombinací dekompozic popsaných Alstrupem v~\cite{alstrup97optimal}
116 a \cite{alstrup98marked}.
118 \s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakoøenìný strom $T$ o~$n$ vrcholech
121 \:{\I Koøeny mikrostromù} budou nejvy¹¹í vrcholy v~$T$, pod~nimi¾ je nejvý¹e $\log n$ listù
122 a které nejsou koøenem celého~$T$.
123 \:{\I Mikrostromy} le¾í v~$T$ od~tìchto koøenù ní¾e.
124 \:{\I Spojovací hrany} vedou z~koøenù mikrostromù do~jejich otcù.
125 \:{\I Makrostrom} je tvoøen zbývajícími vrcholy a hranami stromu~$T$.
128 \s{Pozorování:} Ka¾dý mikrostrom má nejvý¹e $\log n$ listù. Pod ka¾dým listem makrostromu le¾í
129 alespoò jeden mikrostrom (mù¾e jich být i více, viz dekompozice hvìzdy na~obrázku), tak¾e
130 listù makrostromu je nejvý¹e $n/\log n$.
132 Vnitøních vrcholù makro- i mikrostromù ale mù¾e být ne¹ikovnì mnoho, proto¾e se ve~stromech mohou
133 vyskytovat dlouhé cesty. Pomù¾eme si snadno: ka¾dou cestu si budeme pamatovat zvlá¹» a ve~stromu
134 ji nahradíme hranou, která bude vlo¾ena právì tehdy, kdy¾ budou pøítomny v¹echny hrany cesty.
136 \s{Pøíklad:} Následující obrázek ukazuje dekompozici nìkolika stromù za~pøepokladu,
137 ¾e $\log n=4$. Vrcholy mikrostromù jsou èerné, makrostromu bílé. Spojovací hrany kreslíme teèkovanì,
138 hrany komprimovaných cest tuènì.
141 \fig{mima.eps}{\epsfxsize}
143 \s{Algoritmus pro cesty:} Cestu délky~$l$ rozdìlíme na~úseky délky $\log n$, pro nì¾ si ulo¾íme
144 mno¾iny ji¾ pøítomných hran (po~bitech jako èísla). Pak si je¹tì pamatujeme zkomprimovanou cestu (hrany
145 odpovídají úsekùm a jsou pøítomny právì tehdy, jsou-li pøítomny v¹echny hrany pøíslu¹ného úseku)
146 délky $l/\log n$ a pro ni \uv{pøebarvovací} strukturu pro Union-Find.
148 \>$\<Union>(x,y)$ (pøidání hrany $e=xy$ do~cesty):
150 \:Pøidáme $e$ do mno¾iny hran pøítomných v~pøíslu¹ném úseku.
151 \:Pokud se tím úsek naplnil, pøidáme odpovídající hranu do~zkomprimované cesty.
156 \:Pokud $x$ a $y$ jsou v~tém¾e úseku, otestujeme bitovými operacemi, zda
157 jsou v¹echny hrany mezi $x$ a $y$ pøítomny.
158 \:Pokud jsou v~rùzných úsecích, rozdìlíme cestu z~$x$ do~$y$ na~posloupnost celých úsekù,
159 na~které nám odpoví zkomprimovaná cesta, a~dva dotazy v~krajních èásteèných úsecích.
162 Operace uvnitø úsekù pracují v~èase $\O(1)$, operace na~zkomprimované cestì v~$\O(\log l)$
163 amortizovanì, ale za~dobu ¾ivota struktury je jich $\O(l/\log n)=\O(l/\log l)$, tak¾e celkovì zaberou lineární èas.
165 \s{Cestová komprese:} Operace na~mikro/makro-stromech budeme následujícím zpùsobem
166 pøevádìt na~operace s~jejich cestovì komprimovanými podobami a na~operace s~cestovými strukturami:
170 \:Pokud $e=xy$ le¾í uvnitø nìjaké cesty, pøidáme ji do~cesty, co¾ buïto zpùsobí
171 pøidávání jiné hrany, a~nebo u¾ jsme hotovi.
172 \:Provedeme \<Union> v~komprimovaném stromu.
177 \:Pokud $x$ a $y$ le¾í uvnitø jedné cesty, zeptáme se cestové struktury a konèíme.
178 \:Pokud $x$ le¾í uvnitø nìjaké cesty, zjistíme dotazem na~cestovou strukturu,
179 ke~kterému krajnímu vrcholu cesty je pøipojen, a~$x$ nahradíme tímto vrcholem.
180 Není-li pøipojen k~¾ádnému, je~evidentnì odpovìï na~celý \<Find> negativní;
181 pokud k~obìma, vybereme si libovolný, proto¾e jsou stejnì v~cestovì komprimovaném
182 stromu spojeny hranou. Analogicky pro~$y$.
183 \:Zeptáme se struktury pro komprimovaný strom.
186 \s{Algoritmus pro mikrostromy:} Po~kompresi cest má ka¾dý mikrostrom nejvý¹e $2\log n$
187 vrcholù, èili také nejvý¹e tolik hran. Hrany si oèíslujeme pøirozenými èísly, ka¾dou
188 mno¾inu hran pak mù¾eme reprezentovat $(2\log n)$-bitovým èíslem a mno¾inové operace
189 provádìt pomocí bitových v~konstantním èase.
191 Pro ka¾dý mikrostrom si pøedpoèítáme pro v¹echny jeho vrcholy~$v$ mno¾iny~$P_v$ hran le¾ících
192 na~cestì z~koøene mikrostromu do~$v$. Navíc si budeme pro celý mikrostrom pamatovat mno¾inu
198 \:Najdeme poøadové èíslo $i$ hrany $xy$ (máme pøedpoèítané).
199 \:$F \leftarrow F \cup \{i\}$.
205 \:$P \leftarrow P_x \mathop{\Delta} P_y$ (mno¾ina hran le¾ících na~cestì z~$x$ do~$y$).
206 \:Pokud $P\setminus F=\emptyset$, le¾í $x$ a $y$ ve~stejnì komponentì, jinak ne.
209 \s{Algoritmus pro celý problém:} Strom rozlo¾íme na~mikrostromy, makrostrom a spojovací
210 hrany. V~mikrostromech i makrostromu zkomprimujeme cesty. Pro cesty a mikrostromy pou¾ijeme
211 vý¹e popsané struktury, pro ka¾dou spojovací hranu si budeme pamatovat jen znaèku,
212 zda je pøítomna, a pro makrostrom pøebarvovací strukturu.
217 \:Pokud $e=xy$ je spojovací, poznamenáme si, ¾e je pøítomna, a~konèíme.
218 \:Nyní víme, ¾e $e$ le¾í uvnitø mikrostromu nebo makrostromu, a~tak provedeme \<Union>
219 na~pøíslu¹né struktuøe.
225 \:Le¾í-li $x$ a $y$ v~jednom mikrostromu, zeptáme se struktury pro~mikrostrom.
226 \:Je-li $x$ uvnitø mikrostromu, zeptáme se mikrostruktury na~spojení s~koøenem mikrostromu.
227 Není-li, odpovíme {\sc ne}, stejnì jako kdy¾ není pøítomna pøíslu¹ná spojovací hrana.
228 Jinak $x$ nahradíme listem makrostromu, do~kterého spojovací hrana vede. Podobnì pro~$y$.
229 \:Odpovíme podle struktury pro makrostrom.
232 \s{Analýza:} Operace \<Find> trvá konstantní èas, proto¾e se rozlo¾í na~$\O(1)$ \<Find>ù
233 v~dílèích strukturách a ka¾dý z~nich trvá konstantnì dlouho. V¹ech $n$ operací \<Union>
234 trvá $\O(n)$, jeliko¾ zpùsobí $\O(n)$ amortizovanì konstantních operací s~mikrostromy, spojovacími
235 hranami a cestami a $\O(n/\log n)$ operací s~makrostromem, které trvají $\O(\log n)$ amortizovanì
237 \foot{To je v~prùmìru $\O(1)$ na~operaci a dokonce i amortizovanì, pokud necháme inicializaci
238 struktury, která je lineární, naspoøit potenciál $\O(n)$, ze~kterého budeme prùbì¾nì platit
239 sluèování v~makrostromu.}
241 \s{Cvièení:} Zkuste pomocí dekompozice vyøe¹it následující problém: je dán strom,
242 jeho¾ ka¾dý vrchol mù¾e být oznaèený. Navrhnìte datovou strukturu, která bude umìt
243 v~èase $\O(\log\log n)$ oznaèit nebo odznaèit vrchol a v~èase $\O(\log n/\log\log n)$ najít
244 nejbli¾¹ího oznaèeného pøedchùdce.
246 \h{Fredericksonova clusterizace}
248 Mikro/makro-stromová dekompozice není jediný zpùsob, jak stromy rozkládat. Nìkdy
249 se hodí napøíklad následující my¹lenka:
251 \s{Definice:} {\I (Fredericksonova clusterizace)} Nech» $G$ je graf s~vrcholy stupòù nejvý¹e~3
252 a $c\ge 1$. Pak $c$-clusterizací grafu $G$ nazveme libovolný rozklad
253 $G$ na~souvislé podgrafy {\I (clustery)} $C_1, C_2, \ldots, C_k$ takový, ¾e platí:
255 \:Ka¾dý vrchol se nachází v~právì jednom clusteru (hrany mohou vést i mezi clustery).
256 \:Ka¾dý cluster má nejvý¹e~$c$ vrcholù.
257 \:Vnìj¹í stupeò ka¾dého clusteru (tj. poèet hran, které vedou mezi $C_i$ a ostatními
258 clustery; mezi ka¾dou dvojicí clusterù poèítáme jen jednu hranu) je nejvý¹e~3.
259 Navíc pokud je právì~3, je cluster triviální, èili $\vert C_i \vert = 1$.
260 \:®ádné dva sousední clustery nelze spojit.
263 \s{Vìta:} (Frederickson \cite{frederickson91ambivalent}) Ka¾dá $c$-clusterizace grafu $G$ má $\O(\vert V(G)\vert /c)$ clusterù. Existuje
264 algoritmus, který jednu takovou najde v~lineárním èase.
266 \proof První èást rozborem pøípadù, druhá hladovì pomocí DFS. \qed
268 \s{Pou¾ití:} Pøedchozí variantu Union-Find problému bychom také mohli vyøe¹it nahrazením
269 vrcholù stupnì $>3$ \uv{kruhovými objezdy bez jedné hrany}\foot{tzv. francouzský trik},
270 nalezením $(\log n)$-clusterizace, pou¾itím bitové reprezentace mno¾in uvnitø clusterù
271 a pøebarvovací struktury na~hrany mezi clustery.
273 \h{Stromoví pøedchùdci}
275 \s{Problém:} {\I (Least Common Ancestor alias LCA)} Chceme si pøedzpracovat zakoøenìný strom~$T$
276 tak, abychom dokázali pro libovolné dva vrcholy $x,y$ najít co~nejrychleji jejich nejbli¾¹ího
277 spoleèného pøedchùdce.
279 \s{Triviální øe¹ení LCA:}
281 \:Vystoupáme z~$x$ i $y$ do~koøene, oznaèíme vrcholy na~cestách a kde se poprvé
282 potkají, tam je hledaný pøedchùdce. To je lineární s~hloubkou a nepotøebuje
284 \:Vylep¹ení: Budeme stoupat z~$x$ a $y$ støídavì. Tak potøebujeme jen lineárnì mnoho
285 krokù vzhledem ke~vzdálenosti spoleèného pøedchùdce.
286 \:Pøedpoèítáme v¹echny mo¾nosti: pøedzpracování $\O(n^2)$, dotaz $\O(1)$.
290 \>Vìrni vtipùm o~matfyzácích a èlánku \cite{bender00lca} pøevedeme radìji tento problém na~jiný.
292 \s{Problém:} {\I (Range Minimum Query alias RMQ)} Chceme pøedzpracovat posloupnost èísel
293 $a_1,\ldots a_n$ tak, abychom umìli rychle poèítat $\min_{x\le i\le y} a_i$.%
294 \foot{V¹imnìte si, ¾e pro sumu místo minima je tento problém velmi snadný.}
296 \s{Lemma:} LCA lze pøevést na~RMQ s~lineárním èasem na~pøedzpracování a konstantním
297 èasem na~pøevod dotazu.
299 \proof Strom projdeme do~hloubky a poka¾dé, kdy¾ vstoupíme do~vrcholu (a» ji¾ poprvé nebo se do~nìj vrátíme),
300 zapí¹eme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejvy¹¹í vrchol mezi libovolnou
301 náv¹tìvou~$x$ a libovolnou náv¹tìvou~$y$.
304 \s{Triviální øe¹ení RMQ:}
306 \:Pøedpoèítáme v¹echny mo¾né dotazy: pøedzpracování $\O(n^2)$, dotaz $\O(1)$.
307 \: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} \}$,
308 èili minima v¹ech blokù velkých jako nìjaká mocnina dvojky. Kdy¾ se poté nìkdo zeptá
309 na~minimum bloku $a_i,a_{i+1},\ldots,a_{j-1}$, najdeme nejvìt¹í~$k$ takové, ¾e $2^k < j-i$
311 $$\min( \min\{ a_i, \ldots, a_{i+2^k-1} \}, \min\{ a_{j-2^k}, \ldots, a_{j-1} \} ).$$
312 Tak zvládneme dotazy v~èase $\O(1)$ po~pøedzpracování v~èase $\O(n\log n)$.
315 My si ov¹em v¹imneme, ¾e ná¹ pøevod z~LCA vytváøí dosti speciální instance problému RMQ,
316 toti¾ takové, v~nich¾ je $\vert a_i - a_{i+1} \vert = 1$. Takovým instancím budeme
317 øíkat RMQ${\pm}1$ a budeme je umìt øe¹it ¹ikovnou dekompozicí.
319 \s{Dekompozice} pro RMQ${\pm}1$: Vstupní posloupnost rozdìlíme na~bloky velikosti $b=1/2\cdot \log n$,
320 ka¾dý dotaz umíme rozdìlit na~èást týkající se celých blokù a maximálnì dva dotazy na~èásti blokù.
322 V¹imneme si, ¾e aèkoliv blokù je mnoho, jejich mo¾ných typù (tj. posloupností klesání
323 a stoupání) je pouze $2^{b-1}\le\sqrt n$ a bloky tého¾ typu se li¹í pouze posunutím
324 o~konstantu. Vybudujeme proto kvadratickou strukturu pro jednotlivé typy a pro ka¾dý
325 blok si zapamatujeme, jakého je typu a jaké má posunutí. Celkem strávíme èas
326 $\O(n + \sqrt n \cdot \log^2 n) = \O(n)$ pøedzpracováním a $\O(1)$ dotazem.
328 Mimo to je¹tì vytvoøíme komprimovanou posloupnost, v~ní¾ ka¾dý blok nahradíme
329 jeho minimem. Tuto posloupnost délky $n/b$ budeme pou¾ívat pro èásti dotazù
330 týkající se celých blokù a pøipravíme si pro ni \uv{logaritmickou} variantu
331 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í
334 Tak jsme získali algoritmus pro RMQ${\pm}1$ s~konstantním èasem na~dotaz po~lineárním
335 pøedzpracování a vý¹e zmínìným pøevodem i algoritmus na~LCA se stejnými parametry.
336 Je¹tì uká¾eme, ¾e pøevod mù¾e fungovat i v~opaèném smìru, a~tak mù¾eme získat
337 i konstantní/lineární algoritmus pro obecné RMQ.
339 \s{Definice:} {\I Kartézský strom} pro posloupnost $a_1,\ldots,a_n$ je strom,
340 jeho¾ koøenem je minimum posloupnosti, tj. nìjaké $a_j=\min_i a_i$, jeho levý podstrom je
341 kartézský strom pro $a_1,\ldots,a_{j-1}$ a pravý podstrom kartézský strom pro $a_{j+1},\ldots,a_n$.
343 \s{Lemma:} Kartézský strom je mo¾né zkonstruovat v~lineárním èase.
345 \proof Pou¾ijeme inkrementální algoritmus. V¾dy si budeme pamatovat
346 kartézský strom pro ji¾ zpracované prvky a pozici posledního zpracovaného
347 prvku v~tomto stromu. Kdy¾ pøidáváme dal¹í prvek, hledáme místo, kam ho
348 pøipojit, od~tohoto oznaèeného prvku nahoru. Pov¹imnìme si, ¾e vzhledem
349 k~potenciálu rovnému hloubce oznaèeného prvku je èasová slo¾itost pøidání
350 prvku amortizovanì konstantní.
353 \s{Lemma:} RMQ lze pøevést na~LCA s~lineárním èasem na~pøedzpracování a konstantním
354 èasem na~pøevod dotazu.
356 \proof Sestrojíme kartézský strom a RMQ pøevedeme na~LCA v~tomto stromu.
359 Výsledky této podkapitoly mù¾eme shrnout do~následující vìty:
361 \s{Vìta:} Problémy LCA i RMQ je mo¾né øe¹it v~konstantním èase na~dotaz
362 po~pøedzpracování v~lineárním èase.
364 \s{Cvièení:} Vymyslete jednodu¹¹í strukturu pro RMQ, víte-li, ¾e v¹echny dotazy budou na~intervaly stejné délky.
projects / ga.git / blob