From 58b3a55a24e6bcab408bd048c2221397df2c744d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 5 Mar 2008 14:36:33 +0100 Subject: [PATCH] Notation. --- PLAN | 1 - notation.tex | 1 + ram.tex | 4 ++-- 3 files changed, 3 insertions(+), 3 deletions(-) diff --git a/PLAN b/PLAN index c75cc05..9b562ec 100644 --- a/PLAN +++ b/PLAN @@ -66,7 +66,6 @@ Models: - mention in-place radix-sorting? - consequences of Q-Heaps: Thorup's undirected SSSP etc. - add more context from thorup:aczero, also mention FP operations -- update notation.tex Ranking: diff --git a/notation.tex b/notation.tex index 4b15cad..bbf7a53 100644 --- a/notation.tex +++ b/notation.tex @@ -47,6 +47,7 @@ \n{$\(x)$}{number~$x\in{\bb N}$ written in binary \[bitnota]} \n{$\(x)_b$}{$\(x)$ zero-padded to exactly $b$ bits \[bitnota]} \n{$x[i]$}{when $x\in{\bb N}$: the value of the $i$-th bit of~$x$ \[bitnota]} +\n{$x[B]$}{when $x\in{\bb N}$: the values of the bits at positions in the set~$B$ \[qhnota]} \n{$\pi[i]$}{when $\pi$ is a~sequence: the $i$-th element of~$\pi$, starting with $\pi[1]$ \[brackets]} \n{$\pi[i\ldots j]$}{the subsequence $\pi[i], \pi[i+1], \ldots, \pi[j]$} \n{$\sigma^k$}{the string~$\sigma$ repeated $k$~times \[bitnota]} diff --git a/ram.tex b/ram.tex index ef84a21..824382e 100644 --- a/ram.tex +++ b/ram.tex @@ -799,7 +799,7 @@ must lie in the left subtree of the root and $x_{i+1},\ldots,x_n$ in its right subtree. Both subtrees can be then constructed recursively.\foot{This construction is also known as the \df{cartesian tree} for the sequence $g_1,\ldots,g_n$ and it is useful in many other algorithms as it can be -constructed in $\O(n)$ time. A~nice application on the Lowest Common Ancestor +built in $\O(n)$ time. A~nice application on the Lowest Common Ancestor and Range Minimum problems has been described by Bender et al.~in \cite{bender:lca}.} \qed @@ -808,7 +808,7 @@ Unfortunately, the vector of the $g_i$'s is also too long (is has $k\log W$ bits and we have no upper bound on~$W$ in terms of~$k$), so we will compress it even further: -\nota +\nota\id{qhnota}% \itemize\ibull \:$B = \{g_1,\ldots,g_n\}$ --- the set of bit positions of all the guides, stored as a~sorted array, \:$G : \{1,\ldots,n\} \rightarrow \{1,\ldots,n\}$ --- a~function mapping -- 2.39.2