Improved proof of QH lemma.

[saga.git] / ram.tex

diff --git a/ram.tex b/ram.tex
index 1f8705e6661780db26b709a97208da3b8eea7af4..7cdf752c3c919d6aa55fe1cea71513fea5060ed0 100644 (file)
--- a/ram.tex
+++ b/ram.tex
@@ -839,17 +839,19 @@ The rank $R_X(x)$ can be computed in constant time from:
 \endlist
 
 \proof
-We know that the trie~$T$ is uniquely determined by the order of the $g_i$'s
+Let us prove that all ingredients of Lemma~\ref{qhdeterm} are either small
+enough or computable in constant time.
+
+We know that the shape of the trie~$T$ is uniquely determined by the order of the $g_i$'s
 and therefore by the function~$G$ since the array~$B$ is sorted. The shape of
-the trie together with the bits in $x[B]$ determine the leaf $T[x]$ visited
-when searching for~$x$. All this can be computed in polynomial time and it
+the trie together with the bits in $x[B]$ determine the leaf~$x_i$ found when searching
+for~$x$ using only the guides. This can be computed in polynomial time and it
 depends on $\O(k\log k)$ bits of input, so according to Lemma~\ref{qhprecomp}
 we can look it up in a~precomputed table.
 
-Similarly we will determine all other ingredients of Lemma~\ref{qhdeterm} in
-constant time. As we know~$x$ and all the $x_i$'s, we can immediately find
-the relation between $x$ and $x_{T[x]}$ and use the LSB/MSB algorithm (\ref{lsb})
-to find the topmost disagreeing bit.
+The relation between $x$ and~$x_i$ can be obtained directly as we know the~$x_i$.
+The bit position of the first disagreement can be calculated in constant time
+using the LSB/MSB algorithm (\ref{lsb}).
 
 All these ingredients can be stored in $\O(k\log k)$ bits, so we may assume
 that the rank can be looked up in constant time as well.