9-decomp/9-decomp.tex

   1 \input ../sgr.tex
   2
   3 \hyphenation{mikro-strom mikro-stro-mo-vé}
   4
   5 \prednaska{9}{Dekompozice stromù}{}
   6
   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
  10 èase.
  11
  12 \h{Union-Find problem}
  13
  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.
  20
  21 \s{Triviální øe¹ení:} Ka¾dé tøídì pøiøadíme unikátní barvu, kterou obarvíme prvky tøídy. Operace \<Find>
  22 porovnává barvy, operace \<Union> prvky jedné tøídy pøebarvuje.
  23
  24 Operace \<Find> tak pracuje v~konstantním èase, \<Union> mù¾e zabrat a¾ lineární èas. Mù¾eme si
  25 pomoci tím, ¾e v¾dy pøebarvíme {\I men¹í} ze~sluèovaných ekvivalenèních tøíd (budeme
  26 si pro ka¾dou tøídu pamatovat seznam jejích prvkù a velikost). Tehdy mù¾e být ka¾dý
  27 prvek pøebarven jen $\O(\log n)$-krát, jeliko¾ ka¾dým pøebarvením se alespoò zdvojnásobí
  28 velikost tøídy, ve~které prvek le¾í. Posloupnost operací \<Union>, kterou vznikla tøída
  29 velikosti~$k$, tak trvá $\O(k\log k)$, tak¾e mù¾eme bezpeènì prohlásit, ¾e amortizovaná
  30 slo¾itost operace \<Union> je $\O(\log n)$.
  31
  32 \s{Chytøej¹í øe¹ení:} Ka¾dou tøídu budeme reprezentovat zakoøenìným stromem s~hranami
  33 orientovanými smìrem ke~koøeni (jinými slovy pro ka¾dý prvek si pamatujeme jeho otce
  34 nebo ¾e je to koøen). \<Find> nalezne koøeny stromù a porovná je, \<Union> pøipojí koøen
  35 jedné tøídy pod koøen druhé. Aby stromy nedegenerovaly, pøidáme dvì podmínky:
  36
  37 \itemize\ibull
  38 \:{\I Union by rank:} ka¾dý koøen $v$ si pamatuje svùj rank $r(v)$. Pokud spojujeme
  39 dva stromy s~koøeny $v$, $w$ a $r(v)<r(w)$, pøipojíme $v$ pod~$w$ a rank zachováme.
  40 Pokud $r(v)=r(w)$, pøipojíme libovolnì a nový koøen bude mít rank $r(v)+1$.%
  41 \foot{Stejnì by fungovalo pravidlo {\I Union by size,} které pøipojuje men¹í
  42 strom pod vìt¹í, ale ranky máme radìji, neb jsou skladnìj¹í a snáze se analyzují.}
  43
  44 \:{\I Path compression:} pokud z~vrcholu vystoupíme do~koøene (napøíklad
  45 bìhem operace \<Find>), pøepojíme v¹echny vrcholy na~cestì, po~které jsme pro¹li,
  46 rovnou pod koøen.
  47 \endlist
  48
  49 \s{Pozorování:} Samotné pravidlo Union by rank zajistí, ¾e strom ranku $r$ bude
  50 mít hloubku nejvý¹e $r$ a minimálnì $2^r$ vrcholù, tak¾e èasová slo¾itost operací
  51 bude omezena $\O(\log n)$.%
  52 \foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila.}
  53
  54 Ve~skuteènosti se popsaná struktura chová daleko lépe:
  55
  56 \s{Vìta:} (Tarjan, van Leeuwen \cite{tarjan84setunion}) Kombinace Union by rank a Path compression vede k~amortizované
  57 slo¾itosti obou operací $\O(\alpha(n))$, kde $\alpha$ je inverzní Ackermannova funkce.%
  58 \foot{Existuje varianta tohoto algoritmu, která dosahuje stejné slo¾itosti i v~nejhor¹ím
  59 pøípadì; té¾ je známo, ¾e asymptoticky lep¹í slo¾itosti nelze dosáhnout.}
  60
  61 \h{Union-Find s~pøedem známými Uniony}
  62
  63 Dále nás bude zajímat speciální varianta Union-Find problemu, v~ní¾ dopøedu známe
  64 posloupnost Unionù, èili strom, který spojováním komponent vznikne.\foot{Kdy se to hodí?
  65 Tøeba v~Thorupovì lineárním algoritmu \cite{thorup:usssp} na~nejkrat¹í cesty nebo
  66 v~Weiheho takté¾ lineárním algoritmu \cite{weihe:paths} na~hledání hranovì disjunktních
  67 cest v~rovinných grafech.}
  68 Jiná interpretace tého¾ (jen pozpátku) je dekrementální udr¾ování komponent
  69 souvislosti lesa: na~poèátku je dán les a umíme smazat hranu a otestovat, zda jsou
  70 dva vrcholy v~tém¾e stromu.
  71
  72 Popí¹eme algoritmus,
  73 který po~poèáteèním pøedzpracování v~èase $\O(n)$ zvládne \<Union> i \<Find> v~amortizovanì
  74 konstantním èase. Tento algoritmus je kombinací dekompozic popsaných Alstrupem v~\cite{alstrup97optimal}
  75 a \cite{alstrup98marked}.
  76
  77 \s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakoøenìný strom $T$ o~$n$ vrcholech
  78 definujeme:
  79 \itemize\ibull
  80 \:{\I Koøeny mikrostromù} $R$ budou nejvy¹¹í vrcholy, pod~nimi¾ je nejvý¹e $\log n$ listù
  81 a které nejsou koøenem celého~$T$.
  82 \:{\I Mikrostromy} le¾í v~$T$ od~tìchto koøenù ní¾e.
  83 \:{\I Spojovací hrany} vedou z~koøenù mikrostromù do~jejich otcù.
  84 \:{\I Makrostrom} je tvoøen zbývajícími vrcholy a hranami stromu~$T$.
  85 \endlist
  86
  87 \s{Pozorování:} Ka¾dý mikrostrom má nejvý¹e $\log n$ listù. Pod ka¾dým listem makrostromu le¾í
  88 alespoò jeden mikrostrom (mù¾e jich být i více, viz dekompozice hvìzdy na~obrázku), tak¾e
  89 listù makrostromu je nejvý¹e $n/\log n$.
  90
  91 Vnitøních vrcholù makro- i mikrostromù ale mù¾e být ne¹ikovnì mnoho, proto¾e se ve~stromech mohou
  92 vyskytovat dlouhé cesty. Pomù¾eme si snadno: ka¾dou cestu si budeme pamatovat zvlá¹» a ve~stromu
  93 ji nahradíme hranou, která bude vlo¾ena právì tehdy, kdy¾ budou pøítomny v¹echny hrany cesty.
  94
  95 \s{Pøíklad:} Následující obrázek ukazuje dekompozici nìkolika stromù za~pøepokladu,
  96 ¾e $\log n=4$. Vrcholy mikrostromù jsou èerné, makrostromu bílé. Spojovací hrany kreslíme teèkovanì,
  97 hrany komprimovaných cest tuènì.
  98
  99 \fig{mima.eps}{\epsfxsize}
 100
 101 \s{Algoritmus pro cesty:} Cestu délky~$l$ rozdìlíme na~úseky délky $\log n$, pro nì¾ si ulo¾íme
 102 mno¾iny ji¾ pøítomných hran (po~bitech jako èísla). Pak si je¹tì pamatujeme zkomprimovanou cestu (hrany
 103 odpovídají úsekùm a jsou pøítomny právì tehdy, jsou-li pøítomny v¹echny hrany pøíslu¹ného úseku)
 104 délky $l/\log n$ a pro ni \uv{pøebarvovací} strukturu pro Union-Find.
 105
 106 \>$\<Union>(x,y)$ (pøidání hrany $e=xy$ do~cesty):
 107 \algo
 108 \:Pøidáme $e$ do mno¾iny hran pøítomných v~pøíslu¹ném úseku.
 109 \:Pokud se tím úsek naplnil, pøidáme odpovídající hranu do~zkomprimované cesty.
 110 \endalgo
 111
 112 \>$\<Find>(x,y):$
 113 \algo
 114 \:Pokud $x$ a $y$ jsou v~tém¾e úseku, otestujeme bitovými operacemi, zda
 115   jsou v¹echny hrany mezi $x$ a $y$ pøítomny.
 116 \:Pokud jsou v~rùzných úsecích, rozdìlíme cestu z~$x$ do~$y$ na~posloupnost celých úsekù,
 117   na~které nám odpoví zkomprimovaná cesta, a~dva dotazy v~krajních èásteèných úsecích.
 118 \endalgo
 119
 120 Operace uvnitø úsekù pracují v~èase $\O(1)$, operace na~zkomprimované cestì v~$\O(\log l)$
 121 amortizovanì, ale za~dobu ¾ivota struktury je jich $\O(l/\log n)=\O(l/\log l)$, tak¾e celkovì zaberou lineární èas.
 122
 123 \s{Cestová komprese:} Operace na~mikro/makro-stromech budeme následujícím zpùsobem
 124 pøevádìt na~operace s~jejich cestovì komprimovanými podobami a na~operace s~cestovými strukturami:
 125
 126 \>$\<Union>(x,y)$:
 127 \algo
 128 \:Pokud $e=xy$ le¾í uvnitø nìjaké cesty, pøidáme ji do~cesty, co¾ buïto zpùsobí
 129   pøidávání jiné hrany, a~nebo u¾ jsme hotovi.
 130 \:Provedeme \<Union> v~komprimovaném stromu.
 131 \endalgo
 132
 133 \>$\<Find>(x,y)$:
 134 \algo
 135 \:Pokud $x$ a $y$ le¾í uvnitø jedné cesty, zeptáme se cestové struktury a konèíme.
 136 \:Pokud $x$ le¾í uvnitø nìjaké cesty, zjistíme dotazem na~cestovou strukturu,
 137   ke~kterému krajnímu vrcholu cesty je pøipojen, a~$x$ nahradíme tímto vrcholem.
 138   Není-li pøipojen k~¾ádnému, je~evidentnì odpovìï na~celý \<Find> negativní;
 139   pokud k~obìma, vybereme si libovolný, proto¾e jsou stejnì v~cestovì komprimovaném
 140   stromu spojeny hranou. Analogicky pro~$y$.
 141 \:Zeptáme se struktury pro komprimovaný strom.
 142 \endalgo
 143
 144 \s{Algoritmus pro mikrostromy:} Po~kompresi cest má ka¾dý mikrostrom nejvý¹e $2\log n$
 145 vrcholù, èili také nejvý¹e tolik hran. Hrany si oèíslujeme pøirozenými èísly, ka¾dou
 146 mno¾inu hran pak mù¾eme reprezentovat $2\log n$-bitovým èíslem a mno¾inové operace
 147 provádìt pomocí bitových v~konstantním èase.
 148
 149 Pro ka¾dý mikrostrom si pøedpoèítáme pro v¹echny jeho vrcholy~$v$ mno¾iny~$P_v$ hran le¾ících
 150 na~cestì z~koøene mikrostromu do~$v$. Navíc si budeme pro celý mikrostrom pamatovat mno¾inu
 151 pøítomných hran~$F$.
 152
 153 \>$\<Union>(x,y):$
 154
 155 \algo
 156 \:Najdeme poøadové èíslo $i$ hrany $xy$ (máme pøedpoèítané).
 157 \:$F \leftarrow F \cup \{i\}$.
 158 \endalgo
 159
 160 \>$\<Find>(x,y):$
 161
 162 \algo
 163 \:$P \leftarrow P_x \mathop{\Delta} P_v$ (mno¾ina hran le¾ících na~cestì z~$x$ do~$y$).
 164 \:Pokud $P\setminus F=\emptyset$, le¾í $x$ a $y$ ve~stejnì komponentì, jinak ne.
 165 \endalgo
 166
 167 \s{Algoritmus pro celý problém:} Strom rozlo¾íme na~mikrostromy, makrostromy a spojovací
 168 hrany. V~mikrostromech i makrostromech zkomprimujeme cesty. Pro cesty a mikrostromy pou¾ijeme
 169 vý¹e popsané struktury, pro ka¾dou spojovací hranu si budeme pamatovat jen znaèku,
 170 zda je pøítomna, a pro makrostrom pøebarvovací strukturu.
 171
 172 \>$\<Union>(x,y)$:
 173
 174 \algo
 175 \:Pokud $e=xy$ je spojovací, poznamenáme si, ¾e je pøítomna, a~konèíme.
 176 \:Nyní víme, ¾e $e$ le¾í uvnitø mikrostromu nebo makrostromu, a~tak provedeme \<Union>
 177    na~pøíslu¹né struktuøe.
 178 \endlist
 179
 180 \>$\<Find>(x,y)$:
 181
 182 \algo
 183 \:Le¾í-li $x$ a $y$ v~jednom mikrostromu, zeptáme se struktury pro~mikrostrom.
 184 \:Je-li $x$ uvnitø mikrostromu, zeptáme se mikrostruktury na~spojení s~koøenem mikrostromu.
 185   Není-li, odpovíme {\sc ne}, stejnì jako kdy¾ není pøítomna pøíslu¹ná spojovací hrana.
 186   Jinak $x$ nahradíme listem makrostromu, do~kterého spojovací hrana vede. Podobnì pro~$y$.
 187 \:Odpovíme podle struktury pro makrostrom.
 188 \endalgo
 189
 190 \s{Analýza:} Operace \<Find> trvá konstantní èas, proto¾e se rozlo¾í na~$\O(1)$ \<Find>ù
 191 v~dílèích strukturách a ka¾dý z~nich trvá konstantnì dlouho. V¹ech $n$ operací \<Union>
 192 trvá $\O(n)$, jeliko¾ zpùsobí $\O(n)$ amortizovanì konstantních operací s~mikrostromy, spojovacími
 193 hranami a cestami a $\O(n/\log n)$ operací s~makrostromy, které trvají $\O(\log n)$ amortizovanì
 194 ka¾dá.%
 195 \foot{To je v~prùmìru $\O(1)$ na~operaci a dokonce i amortizovanì, pokud necháme inicializaci
 196 struktury, která je lineární, naspoøit potenciál $\O(n)$, ze~kterého budeme prùbì¾nì platit
 197 sluèování v~makrostromu.}
 198
 199 \s{Cvièení:} Zkuste pomocí dekompozice vyøe¹it následující problém: je dán strom,
 200 jeho¾ ka¾dý vrchol mù¾e být oznaèený. Navrhnìte datovou strukturu, která bude umìt
 201 v~èase $\O(\log\log n)$ oznaèit nebo odznaèit vrchol a v~èase $\O(\log n/\log\log n)$ najít
 202 nejbli¾¹ího oznaèeného pøedchùdce.
 203
 204 \h{Fredericksonova clusterizace}
 205
 206 Mikro/makro-stromová dekompozice není jediný zpùsob, jak stromy rozkládat. Nìkdy
 207 se hodí napøíklad následující my¹lenka: \cite{frederickson91ambivalent}
 208
 209 \s{Definice:} (Fredericksonova clusterizace) Nech» $G$ je graf s~vrcholy stupòù nejvý¹e~3
 210 a $c\ge 1$. Pak $c$-clusterizací grafu $G$ nazveme libovolný rozklad
 211 $G$ na~souvislé podgrafy (clustery) $C_1, C_2, \ldots, C_k$ takový, ¾e platí:
 212 \itemize\ibull
 213 \:$\forall v \in V \exists ! i: v \in C_i$.
 214 \:$\forall i: \vert C_i\vert \le c$.
 215 \:$\forall i$ je vnìj¹í stupeò $C_i$ (tj. poèet hran, které vedou mezi $C_i$ a zbytkem grafu)
 216 nejvý¹e~3. Navíc pokud je právì~3, je cluster triviální, èili $\vert C_i \vert = 1$.
 217 \:®ádné dva sousední clustery nelze spojit.
 218 \endlist
 219
 220 \s{Vìta:} (Frederickson) Ka¾dá $c$-clusterizace grafu $G$ má $\O(V(G)/c)$ clusterù. Existuje
 221 algoritmus, který jednu takovou najde v~lineárním èase.
 222
 223 \proof První èást rozborem pøípadù, druhá hladovì pomocí DFS. \qed
 224
 225 \s{Pou¾ití:} Pøedchozí variantu Union-Find problemu bychom také mohli vyøe¹it nahrazením
 226 vrcholù stupnì $>3$ \uv{kruhovými objezdy bez jedné hrany}\foot{tzv. francouzský trik},
 227 nalezením $(\log n)$-clusterizace, pou¾itím bitové reprezentace mno¾in uvnitø clusterù
 228 a pøebarvovací struktury na~hrany mezi clustery.
 229
 230 \h{Stromoví pøedchùdci}
 231
 232 \s{Problém:} {\I (Least Common Ancestor alias LCA)} Chceme si pøedzpracovat zakoøenìný strom~$T$
 233 tak, abychom dokázali pro libovolné dva vrcholy $x,y$ najít co~nejrychleji jejich nejbli¾¹ího
 234 spoleèného pøedchùdce.
 235
 236 \s{Triviální øe¹ení LCA:}
 237 \itemize\ibull
 238 \:Vystoupáme z~$x$ i $y$ do~koøene, oznaèíme vrcholy na~cestách a kde se poprvé
 239   potkají, tam je hledaný pøedchùdce. To je lineární s~hloubkou a nepotøebuje
 240   pøedzpracování.
 241 \:Vylep¹ení: Budeme stoupat z~$x$ a $y$ støídavì. Tak potøebujeme jen lineárnì mnoho
 242   krokù vzhledem ke~vzdálenosti spoleèného pøedchùdce.
 243 \:Pøedpoèítáme v¹echny mo¾nosti: pøedzpracování $\O(n^2)$, dotaz $\O(1)$.
 244 \:\dots\ co dál?
 245 \endlist
 246
 247 \>Vìrni vtipùm o~matfyzácích a èlánku \cite{bender00lca} pøevedeme radìji tento problém na~jiný.
 248
 249 \s{Problém:} {\I (Range Minimum Query alias RMQ)} Chceme pøedzpracovat posloupnost èísel
 250 $a_1,\ldots a_n$ tak, abychom umìli rychle poèítat $\min_{x\le i\le y} a_i$.%
 251 \foot{V¹imnìte si, ¾e pro sumu místo minima je tento problém velmi snadný.}
 252
 253 \s{Lemma:} LCA lze pøevést na~RMQ s~lineárním èasem na~pøedzpracování a konstantním
 254 èasem na~pøevod dotazu.
 255
 256 \proof Strom projdeme do~hloubky a poka¾dé, kdy¾ nav¹tívíme vrchol (v~inorderu),
 257 zapí¹eme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejhlub¹í vrchol mezi libovolnou
 258 náv¹tìvou~$x$ a libovolnou náv¹tìvou~$y$.
 259 \qed
 260
 261 \s{Triviální øe¹ení RMQ:}
 262 \itemize\ibull
 263 \:Pøedpoèítáme v¹echny mo¾né dotazy: pøedzpracování $\O(n^2)$, dotaz $\O(1)$.
 264 \: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} \}$,
 265 èili minima v¹ech blokù velkých jako nìjaká mocnina dvojky. Kdy¾ se poté nìkdo zeptá
 266 na~minimum bloku $a_i,a_{i+1},\ldots,a_{j-1}$, najdeme nejvìt¹í~$k$ takové, ¾e $2^k < j-i$
 267 a vrátíme:
 268 $$\min( \min\{ a_i, \ldots, a_{i+2^k-1} \}, \min\{ a_{j-2^k}, \ldots, a_{j-1} \} ).$$
 269 Tak zvládneme dotazy v~èase $\O(1)$ po~pøedzpracování v~èase $\O(n\log n)$.
 270 \endlist
 271
 272 My si ov¹em v¹imneme, ¾e ná¹ pøevod z~LCA vytváøí dosti speciální instance problému RMQ,
 273 toti¾ takové, v~nich¾ je $\vert a_i - a_{i+1} \vert = 1$. Takovým instancím budeme
 274 øíkat RMQ${\pm}1$ a budeme je umìt øe¹it ¹ikovnou dekompozicí.
 275
 276 \s{Dekompozice} pro RMQ${\pm}1$: Vstupní posloupnost rozdìlíme na~bloky velikosti $b=1/2\cdot \log n$,
 277 ka¾dý dotaz umíme rozdìlit na~èást týkající se celých blokù a maximálnì dva dotazy na~èásteèné bloky.
 278
 279 V¹imneme si, ¾e aèkoliv blokù je mnoho, jejich mo¾ných typù (tj. posloupností klesání
 280 a stoupání) je pouze $2^{b-1}\le\sqrt n$ a bloky tého¾ typu se li¹í pouze posunutím
 281 o~konstantu. Vybudujeme proto kvadratickou strukturu pro jednotlivé typy a pro ka¾dý
 282 blok si zapamatujeme, jakého je typu a jaké má posunutí. Celkem strávíme èas
 283 $\O(n + \sqrt n \cdot \log^2 n) = \O(n)$ pøedzpracováním a $\O(1)$ dotazem.
 284
 285 Mimo to je¹tì vytvoøíme komprimovanou posloupnost, v~ní¾ ka¾dý blok nahradíme
 286 jeho minimem. Tuto posloupnost délky $n/b$ budeme pou¾ívat pro èásti dotazù
 287 týkající se celých blokù a pøipravíme si pro ni \uv{logaritmickou} variantu
 288 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í
 289 a $\O(1)$ na~dotaz.
 290
 291 Tak jsme získali algoritmus pro RMQ${\pm}1$ s~konstantním èasem na~dotaz po~lineárním
 292 pøedzpracování a vý¹e zmínìným pøevodem i algoritmus na~LCA se stejnými parametry.
 293 Je¹tì uká¾eme, ¾e pøevod mù¾e fungovat i v~opaèném smìru, a~tak mù¾eme získat
 294 i konstantní/lineární algoritmus pro obecné RMQ.
 295
 296 \s{Definice:} {\I Kartézský strom} pro posloupnost $a_1,\ldots,a_n$ je strom,
 297 jeho¾ koøenem je $a_j=\min_i a_i$, jeho levý podstrom je kartézský strom pro
 298 $a_1,\ldots,a_{j-1}$ a pravý podstrom kartézský strom pro $a_{j+1},\ldots,a_n$.
 299
 300 \s{Lemma:} Kartézský strom je mo¾né zkonstruovat v~lineárním èase.
 301
 302 \proof Pou¾ijeme inkrementální algoritmus. V¾dy si budeme pamatovat
 303 kartézský strom pro ji¾ zpracované prvky a pozici posledního zpracovaného
 304 prvku v~tomto stromu. Kdy¾ pøidáváme dal¹í prvek, hledáme místo, kam ho
 305 pøipojit, od~tohoto oznaèeného prvku nahoru. Pov¹imnìme si, ¾e vzhledem
 306 k~potenciálu rovnému hloubce oznaèeného prvku je èasová slo¾itost pøidání
 307 prvku amortizovanì konstantní.
 308 \qed
 309
 310 \s{Lemma:} RMQ lze pøevést na~LCA s~lineárním èasem na~pøedzpracování a konstantním
 311 èasem na~pøevod dotazu.
 312
 313 \proof Sestrojíme kartézský strom a RMQ pøevedeme na~LCA v~tomto stromu.
 314 \qed
 315
 316 Výsledky této podkapitoly mù¾eme shrnout do~následující vìty:
 317
 318 \s{Vìta:} Problémy LCA i RMQ je mo¾né øe¹it v~konstantním èase na~dotaz
 319 po~pøedzpracování v~lineárním èase.
 320
 321 \references
 322 \bye