\documentclass{article}
\input{6897-preamble}

\begin{document}
\psetnum{5}
\date{2005/03/08}

\begin{pset}
  Suppose we are given a data structure with query time $t_q =
  \bigO{T}$, update time $t_u = \bigO{\text{poly}(n)}$ and space $S =
  \bigO{\text{poly}(n)}$. Assume \WLOG{} that $t_u = S = \bigO{n^k}$
  for some $k$. We will use it to construct a data structure with
  parameters $t_q' = \bigO{T \lg \lg n}, t_u' = \bigO{T \lg \lg n}, S'
  = \bigO{n}$.
  
  Our approach is to maintain a tree where the values are stored in
  the leaves (as in a B+ tree), and each internal node contains a
  predecessor data structure of representative elements used to index
  the subtree. More precisely, the tree is recursively defined as
  follows: a tree of size $m$ consists of a root with between
  $m^{\nicefrac1k}$ and $2m^{\nicefrac1{2k}}-1$ children, each of which
  is a subtree of size $\bigTheta{m^{1-\nicefrac{1}{2k}}}$ (or a leaf).
  As with $y$-fast trees, each subtree contains elements in a certain
  range, and some arbitrary representative element is chosen for
  indexing in the parent's index data structure. Since the size of the
  tree at each level decreases exponentially, $\bigTheta{\lg \lg n}$
  levels are required to reduce the size of the subtree to 1 and
  give a leaf.  So this recurrence guarantees that the tree has height
  $\bigTheta{\lg \lg n}$.

  To perform a query for some element $x$, we descend through the
  tree, performing queries on the predecessor data structure to find
  the two closest representative elements and thus identify which
  two subtrees to search (in much the same way as $y$-fast trees). Since
  the size of each predecessor structure is no more than $n$,
  performing the query requires $t_q = \bigO{T}$ time, and $\bigO{\lg
    \lg n}$ such queries are performed. So the new query time is
  $\bigO{T \lg \lg n}$.

  We now analyze the space requirement. Notice that the space
  $\mathscr{S}(n)$ of a tree with size $n$ is
  $\bigO{n^{{\nicefrac{1}{2k}}^k}} = \bigO{n^{\nicefrac12}}$ for the
  predecessor data structure, plus at most $2m^{\nicefrac1{2k}}$
  children of size at most $m^{1-\nicefrac{1}{2k}}$. This gives the
  recurrence
  \begin{equation}
    \mathscr{S}(n) = \bigO{n^{\nicefrac12}} + 2n^{\nicefrac1{2k}}
    \mathscr{S}\left(n^{1-\nicefrac{1}{2k}}\right)
    \label{eq:rec}
  \end{equation}
  Substituting $n = \left(\frac{2k}{2k-1}\right)^m$ and
  $\mathfrak{S}(m) = \mathscr{S}(n)$ and applying case 3 of the master
  theorem (details omitted), we find that $S(n) = \bigO{n}$. This
  gives the desired space bound.

  Now consider inserting a new element into the data structure. We
  begin by creating a new leaf for this element, and performing a
  query on its value to find the height-1 subtree (call it $x$) into
  which the new leaf should be inserted. This requires $\bigO{T \lg
    \lg n}$ time. We then insert the leaf, adding it as a
  representative element in $x$'s predecessor structure. This may
  cause $x$ to have more than $2m^{\nicefrac1{2k}}-1$ children. If so,
  we split $x$ into two subtrees, and update the predecessor structure
  in $x$'s parent with the appropriate representative elements, and
  recurse upward if necessary. A split for a tree of size
  $\bigTheta{w}$ requires $\bigTheta{w}$ time, as in $y$-fast trees.
  We amortize this cost away with charging: as each element is
  inserted, we place two tokens of potential on each node in the path
  from the root to the new leaf.  When a split is performed, we use
  the potential that has been placed on the root node to pay for the
  split. Since $m^{\nicefrac1{2k}}$ insertions to the root are
  required between splits, this provides potential linearly
  proportional to the size of the subtree, which is sufficient for the
  split. Since potential has to be placed on one node at each level
  for each insert, this adds $\bigO{\lg \lg n}$ cost per insert.

  If the size of the root exceeds the maximum, instead of splitting
  it, we rebuild the entire data structure. Note that since the update
  cost is the same $\bigO{n^k}$ as the space bound, the same
  recurrence in Equation~\ref{eq:rec} for space applies to the cost
  for rebuilding the structure. So the cost required for the
  rebuilding is linear in the size of the structure. This is
  acceptable, since the potential argument described above places this
  amount of potential on the root node. So the overall amortized
  update cost is only $\bigO{T \lg \lg n}$.
\end{pset}
\end{document}