které u¾ umíme (obvykle vhodným kódováním èísly) øe¹it v~konstantním
èase.
-\h{Union-Find problem}
+\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>
jedné tøídy pod koøen druhé. Aby stromy nedegenerovaly, pøidáme dvì pravidla:
\itemize\ibull
-\:{\I Union by rank:} ka¾dý koøen $v$ si pamatuje svùj rank $r(v)$. Pokud spojujeme
+\:{\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 by size,} které pøipojuje men¹í
+\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 Path compression:} pokud z~vrcholu vystoupíme do~koøene (napøíklad
+\:{\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
-\s{Pozorování:} Samotné pravidlo Union by rank 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)$ v~nejhor¹ím pøípadì.%
-\foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila.}
+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ù.
-Amortizovanì se ale popsaná struktura chová daleko lépe:
+\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{Vìta:} (Tarjan, van Leeuwen \cite{tarjan84setunion}) 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.}
+\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 problemu, v~ní¾ dopøedu známe
+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
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 v~\cite{alstrup97optimal}
-a \cite{alstrup98marked}.
+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:
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øepokladu,
+\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
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{Cestová komprese:} Operace na~mikro/makro-stromech budeme následujícím zpùsobem
+\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)$:
\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:
+se více hodí následující my¹lenka:
-\s{Definice:} {\I (Fredericksonova clusterizace)} Nech» $G$ je graf s~vrcholy stupòù nejvý¹e~3
-a $c\ge 1$. Pak $c$-clusterizací grafu $G$ nazveme libovolný rozklad
-$G$ na~souvislé podgrafy {\I (clustery)} $C_1, C_2, \ldots, C_k$ takový, ¾e platí:
+\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
-\:Ka¾dý vrchol se nachází v~právì jednom clusteru (hrany mohou vést i mezi clustery).
-\:Ka¾dý cluster má nejvý¹e~$c$ vrcholù.
-\:Vnìj¹í stupeò ka¾dého clusteru (tj. poèet hran, které vedou mezi $C_i$ a zbytkem grafu)
-je 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.
+\: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{Vìta:} (Frederickson \cite{frederickson91ambivalent}) Ka¾dá $c$-clusterizace grafu $G$ má $\O(V(G)/c)$ clusterù. Existuje
-algoritmus, který jednu takovou najde v~lineárním èase.
+\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.
-\proof První èást rozborem pøípadù, druhá hladovì pomocí DFS. \qed
+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).
-\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},
+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.
\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¾ nav¹tívíme vrchol (v~inorderu),
-zapí¹eme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejhlub¹í vrchol mezi libovolnou
+\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
øí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.
+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
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ý 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$.
+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.
\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
projects / ga.git / blobdiff