From 6a6a23fd94094c20b537af1782dc6c052c384754 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 29 Dec 2006 19:26:40 +0100 Subject: [PATCH] Prvni verze. --- 10-decomp/10-decomp.tex | 334 +++++++++++++++++++++++++++++----------- 1 file changed, 246 insertions(+), 88 deletions(-) diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex index 2e5348e..1727415 100644 --- a/10-decomp/10-decomp.tex +++ b/10-decomp/10-decomp.tex @@ -2,112 +2,270 @@ \prednaska{10}{Dekompozice stromù}{zapsal Ale¹ ©nupárek} +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} -Na Uion-Find problem (UF) mù¾eme nahlí¾et ze více stran (udr¾ování ekvivalencí, -inkrementální souvislost grafu). K èemu je to dobré? -Napøíklad v Kruskalovì algoritmu pro hledání minimálních koster v grafu. -\h{Udr¾ování tøíd ekvivalence } -Mìjme nìjakou mno¾inu M, která se dá rozlo¾it na k ekvivalentních podmon¾in (tøídy ekvivalence). Na mno¾iòe M chceme provádìt -dvì operace: jsou p,q z M ekvivalentní (ve stejné tøídì ekvivalence)? (find(p,q)) Dále chceme umìt spojit dvì tøídy ekvivalence do jedné (union(p,q)). -\h{Inkrementální idr¾ování komponent souvislosti grafu} -Jedná se o pøipad podobný udr¾ování tøíd ekvivalence. Tentokrát mnou¾inou M bude mno¾ina vrcholù V grafu G (V,E). -Za »øídy ekvivalence budou jednotlivé komponenty souvislosti grafu G. Operace find nám øekne o dvou vrcholech nachází-li -se ve stejné komponen»e, èi nikoliv. Operace union nám spojí dvì komponenty do jedné pøidáním hrany. Pokud pøipustíme mazání hran, -øe©ení problému je výraznì te¾¹í. - -\h{Bì¾ná implementace } -Ka¾dé tøídì ekvivalence pøiøadíme unikátní barvu, kterou obarvíme její prvky. Pro operaci find staèí porovnat barvy prvkù. -Pro operaci union dvou komponent je nutné pøebarvit obì na stejnou barvu. Budeme pøebarvovat -v¾dy tu men¹í pak celková operace union bude trvat $\O(n\log(n) + m)$. (Ka¾dé pøebarvení minimálnì zdvojnásobí velikost nové komponenty.) -\h {Chytøej¹í implementace } -Budeme-li prvky za stejné tøídy reprezentovat ve jednom stromì (synové mají ukazatel svého otce), operaci find -provedeme prùchodem ze zadaných prvkù do koøene. Prvky jsou ve stejné komponentì souvislosti, pokud mají stejného otce. -Operace union bude spojení dvou stromù do jednoho (otec jednoho stromu se zavìsí pod listy druhého). -Takto definovaný union nemusí garantovat logaritmickou slo¾itost pro find, -v extrémním pøipadì mù¾e strom mít lineární hloubku vzhledem k poètu vrcholù. - -Degeneraci stromu lze zabránit pøidánim podmínky urèující, jaký strom bude dole. -První mmo¾nost (union by size) je povìsit dolu vìtsí strom. -Druhá mo¾nost (union by rank) je ka¾dému vrcholu nastavit na zaèátku nìjaký rank (tøeba 1). Pokud je $r1 (zji¹tìní, zda dva prvky jsou ekvivalentní) a \ +(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: \ je pøidání hrany, \ 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í:} Ka¾dé tøídì pøiøadíme unikátní barvu, kterou obarvíme prvky tøídy. Operace \ +porovává barvy, operace \ prvky jedné tøídy pøebarví. -\s{Lemma: } Pro ka¾dou C-clusterizaci n-vrcholového stromu je $\O(n/C)$ clusterù. +Operace \ tak pracuje v~konstantním èase, \ mù¾e zabrat a¾ lineární. Mù¾eme si ale +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í \, 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 \ je $\O(\log n)$. -\s{Vìta: } Pro ka¾dé C lze C-clusterizaci (splòujíci pøedchozí lemma) najít v èase $\O(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). \ nalezne koøeny stromù a porovná je, \ pøipojí koøen +jedné tøídy pod koøen druhé. Aby stromy nedegenerovaly, pøidáme dvì podmínky: -\s{Dùkaz: } za pomoci DFS ... -\h{Jednodu¹¹í clusterizace} -Pøedpokládejme, ¾e máme zakoøeòené stromy -\s{Definice: } Koøeny makrostromù jsou nejvy¹¹i vrcholy, pod kterými je maximálnì $\log(n)$ listù. -Celá clusterizace se nám rozpadne na následujíci pøipady: \itemize\ibull -\:N-strom: (má stupeò 1) -\:M-strom: (má stupeò 2) -\:cestu: ka¾dá cesta se popí¹e bitovým polem, jednotlivé úseky se poí¹í jednotlivými slovy +\:{\I Union by rank:} ka¾dý koøen $v$ si pamatuje svùj rank $r(v)$. Pokud spojujeme +dva stromy s~koøeny $v$, $w$ a $r(v)), pøepojíme v¹echny vrcholy na~cestì, po~které jsme pro¹li, +rovnou pod koøen. \endlist -poèet listù v makrostromu je maximálnì $n/\log(n)$ z toho vyplývá, ¾e vý¹ka makrostromu $\O(n/log(n))$ -\s{Co si potøebujeme pamatovat} +\s{Pozorování:} Pravidlo Union by rank samotné zajistí, ¾e strom ranku $r$ bude +mít hloubku nejvý¹e $r$ a minimálnì $2^r$ vrcholù, tak¾e èasová slo¾itost operací +bude omezena $\O(\log n)$.% +\foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila.} + +\s{Vìta:} (Tarjan et al.) Kombinace Union by rank a Path compression vede k~amortizované +slo¾itosti obou operací $\O(\alpha(n))$, kde $\alpha$ je inverzní Ackermannova funkce.% +\foot{Existuje varianta tohoto algoritmu, která dosahuje stejné slo¾itosti i v~nejhor¹ím +pøípadì; té¾ je známo, ¾e asymptoticky lep¹í slo¾itosti nelze dosáhnout.} + +\h{Union-Find s~pøedem známými Uniony} + +Dále nás bude zajímat speciální varianta Union-Find problemu, v~ní¾ dopøedu známe +posloupnost unionù, èili strom, který spojováním komponent vznikne. Popí¹eme algoritmus, +který po~poèáteèním pøedzpracování v~èase $\O(n)$ zvládne \ i \ v~amortizovanì +konstantním èase. + +\s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakoøenìný strom $T$ o~$n$ vrcholech +definujeme: \itemize\ibull -\: $\log(n)$ na clusterizaci -\: makrostrom G s $C_i$ zkontrahovanými pro deg 1,3 do vrcholu a deg 2 do hrany, jeho velikost je $\O(n/\log(n))$ -\:mikrostromy, bitovì popsány +\:{\I Koøeny mikrostromù} $R$ budou nejvy¹¹í vrcholy, pod~nimi¾ je nejvý¹e $\log n$ listù. +\:{\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 zbytkem stromu~$T$, který nepatøí ani do~mikrostromù, ani do~spojovacích hran. \endlist -\h{Makrostromy} -V makrostromu jsou takové hrany, které vedly v pùvodním stromu mezi clustery, vrcholy budou hranièní -vrcholy pøislu¹ných clusterù, cluster stupnì 1 je v novém stromì list, cluster stupnì 2 nahradíme -hranou mezi hranièními vrcholy a cluster stupòe 3 má jeden vnìj¹í vrchol, který je také v novém stromì. +\s{Pozorování:} Ka¾dý mikrostrom má nejvý¹e $\log n$ listù. Pod ka¾dým listem makrostromu le¾í +alespoò jeden makrostrom\foot{Mù¾e jich být i více, pøedstavte si dekompozici hvìzdy.}, 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. Pomu¾eme si snadno: ka¾dou cestu si budeme pamatovat zvlá¹» a ve~stromu +ji nahradíme hranou, která bude existovat právì tehdy, kdy¾ budou pøítomny v¹echny hrany cesty. + +\s{Algoritmus pro cesty:} Cestu délky~$l$ rozdìlíme na~úseky délky $\log n$, pro nì¾ si pamatujeme +(jako èísla) mno¾iny ji¾ pøítomných hran. 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. -\s{find(x,y)} \algo -nech» $i,j: x \in C_i, y \in C_j$ -\:pokud $i=j$, ptáme se v $C_i$ (mikro-find(i,j)) -\:pokud $i\not = j$, najdeme hranièní vrcholy pøíslu¹ných clusterù, tj. $h_i \in C_i, h_j \in C_j$ a provedeme makro-find($h_i$,$h_j$) - find($i$,$j$):=makro-find($h_i$,$h_j$) and mikro-find($i$,$h_i$) and mikro-find($j$,$h_j$); +\:\(x,y) (pøidání hrany $e=xy$ na~cestu): +\::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. +\:\(x,y): +\::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, 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 -\s{delete(x,y)} +Operace uvnitø úsekù pracují v~èase $\O(1)$, operace na~zkomprimované cestì v~$\O(\log l)$ +amortizovanì, ale je jich $\O(l/\log n)=\O(l/\log l)$, tak¾e celkovì zaberou lineární èas. + +\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~konstatní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 pamatovat mno¾inu pøítomných hran~$F$. + \algo -\: pokud $x,y$ je makro-hrana, sma¾eme ji -\: pokud $x,y \in C_i$ pak mikro-delete v $C_i$, pokud je $deg(C_i)=2$ a find($h_1$,$h_2$)==FALSE ($h_1, h_2$hranièní vrcholy), -pak makro-delete hrany odpovýdajíci $C_i$. ($C_i$ je neprùchodná) +\:\(x,y) +\::Najdeme poøadové èíslo $i$ hrany $xy$ (máme pøedpoèítané). +\::$F := F \cup \{i\}$. +\:\(x,y): +\::$P := P_x \mathop{\Delta} P_v$ (to je 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 -\h{Mikrostromy} + +\s{Algoritmus pro celý problém:} Zkomprimujeme cesty a výsledný strom rozlo¾íme +na~mikrostromy, makrostromy a spojovací hrany. 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. + +\>Operace $\(x,y)$: + +\algo +\:Pokud $e=xy$ le¾í uvnitø cesty, pøidáme ji do~cesty, co¾ buïto zpùsobí + pøidávání jiné hrany do~stromu, a~nebo u¾ jsme hotovi. +\:Pokud $e$ je spojovací, poznamenáme si, ¾e je pøítomna, a~konèíme. +\:Pokud $e$ le¾í uvnitø mikrostromu nebo makrostromu, provedeme \ + na~pøíslu¹né struktuøe. +\endlist + +\>Operace $\(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ý \ negativní, + pokud k~obìma, vybereme si libovolný, proto¾e jsou stejnì v~cestovì komprimovaném + stromu spojeny hranou. Analogicky pro~$y$. +\:[Nyní jsou $x$ a $y$ vrcholy cestovì zkomprimovaného stromu.] +\:Le¾í-li $x$ a $y$ v~jednom mikrostromu, zeptáme se struktury pro~mikrostrom. +\:Je-li $x$ uvnitø mikrostromu, zeptáme se mikrostromové struktury 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$. +\:[Nyní jsou $x$ a $y$ vrcholy makrostromu.] +\:Odpovíme podle struktury pro makrostrom. +\endalgo + +\s{Analýza:} Operace s~mikrostromy, spojovacími hranami a cestami jsou, jak u¾ víme, +amortizovanì konstantní. Operace s~makrostromy také, jeliko¾ trvají $\O(\log n)$, +ale provede se jich pouze $\O(n/\log n)$. Ka¾dou operaci \ nebo \ +rozlo¾íme $\O(1)$ tìchto dílèích operací, tak¾e bude také trvat $\O(1)$ amortizovanì. + +\h{Fredericksonova clusterizace} + +Mikro/makro-stromová dekompozice není jediný zpùsob, jak stromy rozkládat. Nìkdy +se hodí napøíklad následující my¹lenka: + +\s{Definice:} (Fredericksonova clusterizace) Nech» $G$ je graf kde $\forall v \in V(G): {\rm deg}(v)\le 3$ +a $c \in {\bb N}$. Pak $c$-clusterizací grafu $G$ nazveme libovolný rozklad +$G$ na~souvislé podgrafy (clustery) $G_1, G_2, \ldots, G_k$ takový, ¾e platí: +\itemize\ibull +\:$\forall v \in V \exists ! i: v \in C_i$. +\:$\forall i: \vert C_i\vert \le c$. +\:$\forall i$ je vnìj¹i stupeò $C_i$ (tj. poèet hran, které vedou mezi $C_i$ a zbytkem grafu) +nejvý¹e~3. Navíc pokud je právì~3, je cluster triviální, èili $\vert C_i \vert = 1$. +\:®ádné dva sousední clustery nelze spojit. +\endlist + +\s{Vìta:} (Frederickson) $c$-clusterizace grafu $G$ má $\O(V(G)/c)$ clusterù a lze ji +najít v~lineárním èase. + +\s{Dùkaz:} Hladovì pomocí DFS. \qed + +\s{Pou¾ití:} Pøedchozí variantu Union-Find problemu bychom také mohli vyøe¹it nahrazením +vrcholù stupnì $>3$ \uv{kruhovými objezdy bez jedné hrany}\foot{tzv. francouzský trik}, +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 -\: strom zakoøením a oèísluji mu hrany $0..h < \log(n)$ -\: pamatujeme si: \itemize\ibull - \:$\forall v \in C_i$ mno¾inu hran $P_v$ na cestì do koøene v (bitový vektor) - \:mon¾inu smazaných hran, operace delete pøidá hranu do mno¾iny - \:hranièní vrcholy - \endlist -\: $P_x \oplus P_y$ je cesta z x do y +\: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 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 sèítání místo minima je tento problém velmi snadný.} + +\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 délky~$l$, najdeme nejbli¾¹í ni¾¹í mocninu dvojky a spoèteme minimum +z~minim blokù této velikost pøira¾ených k~zaèátku a ke~konci dotazovaného bloku. +Tak zvládneme dotaz v~èase $\O(1)$ za~cenu pøedzpracování v~èase $\O(n\log n)$. +\endlist + +\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. + +\s{Dùkaz:} Strom projdeme do~hloubky a poka¾dé, kdy¾ nav¹tívíme vrchol (v~inorderu), +zapí¹eme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejhlub¹í vrchol mezi poslední +náv¹tìvou~$x$ a první náv¹tìvou~$y$, nebo opaènì. +\qed + +My si ov¹em v¹imneme, ¾e tento pøevod 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~èásteèné bloky. + +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í 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)=\O(n)$ na~pøedzpracování +a $\O(1)$ na~dotaz. + +To nám tedy dává algoritmus pro RMQ${\pm}1$ s~konstantním èasem na~dotaz po~lineárním +pøedzpracováním 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 $a_j=\min_i a_i$, jeho levý syn je kartézský strom pro +$a_1,\ldots,a_{j-1}$ a pravý syn kartézský strom pro $a_{j+1},\ldots,a_n$. + +\s{Lemma:} Kartézský strom je mo¾né zkonstruovat v~lineárním èase. + +\s{Dùkaz:} 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¹imneme si, ¾e vzhledem +k~potenciálu urèenému hloubkou 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. + +\s{Dùkaz:} 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~konstatním èase na~dotaz +po~pøedzpracování v~lineárním èase. + \bye -- 2.39.2