From 8fb8460d99c2c0b46df0625109156650ed2ec61b Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Mon, 12 Jan 2009 21:39:47 +0100
Subject: [PATCH] Q-haldy: Vysvetleni u kodovani tvaru stromu bylo spatne.

k*log w nemusi byt obecne O(k^2).
---
 8-qheap/8-qheap.tex | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex
index 0047f31..dae9242 100644
--- a/8-qheap/8-qheap.tex
+++ b/8-qheap/8-qheap.tex
@@ -129,13 +129,15 @@ stromu.
 (je to toti¾ kartézský strom nad tìmito hodnotami -- blí¾e viz kapitola o~dekompozicích
 stromù), hodnoty v~listech jsou $x_1,\ldots,x_r$ v~poøadí zleva doprava.
 
-Kdykoliv chceme indexovat tvarem stromu, mù¾eme tedy indexovat pøímo vektorem
-$(c_1,\ldots,c_r)$, který má pouze $k\log w=\O(k^2)$ bitù. Pro zjednodu¹ení ostatních
-operací ale zvolíme trochu jinou, ekvivalentní reprezentaci:
+Kdykoliv chceme indexovat tvarem stromu, mù¾eme místo toho pou¾ít pøimo vektor
+$(c_1,\ldots,c_r-1)$, který má $k\log w$ bitù. To se sice u¾ vejde do vektoru,
+ale pro indexování tabulek je to stále pøíli¹ (v¹imnìte si, ¾e $\log w$ smí být
+vùèi~$k$ libovolnì vysoký -- pro~$w$ známe pouze dolní mez). Proto reprezentaci
+je¹tì rozdìlíme na dvì èásti:
 
 \itemize\ibull
 \:$B := \{c_1,\ldots,c_r\}$ (mno¾ina v¹ech pozic bitù, které trie testuje, ulo¾ená ve~vektoru setøídìnì),
-\:$C: \{1,\ldots,r\} \to B: B[C(i)]=c_i$.
+\:$C: \{1,\ldots,r\} \to B$ taková, ¾e $B[C(i)]=c_i$.
 \endlist
 
 \s{Lemma R':} $\rank_X(x)$ lze spoèítat v~konstantním èase~z:
-- 
2.39.2