\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts}

\begin{document}

\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'12)} \\[1ex]
{Prof.~Erik Demaine \qquad TAs: Tom Morgan, Justin Zhang} \\[2ex]
\framebox{Problem 1} \quad {\em Due: Thursday, Feb.\ 23}
\end{center}

Be sure to read the instructions on the assignments section of the
class web page.

\paragraph{Creationist successor.}

Given an ordered universe $U$ of keys, develop and analyze a fully retroactive data structure that maintains $S \subseteq U$ and supports the following operations:
\begin{itemize}
\item \tt{insert}$(k)$ : Insert $k \in U$ into $S$
\item \tt{delete}$(k)$ : Remove $k \in U$ from $S$
\item \tt{successor}$(k)$ : Return $\min\{k' \in S \; | \; k' \geq k\}$
\end{itemize}
under the constraint that all $\tt{insert}$ operations must occur at time $-\infty$.  All operations should run in time $O(\log{m})$, where $m$ is the total number of updates performed in the structure (retroactive or not). Observe that such a structure is sufficient to answer the ``rightward ray shot'' queries needed for the nonoblivious retroactive priority queue.

A simple reference to the logarithmic time data structure for general retroactive successor is not a valid solution to this problem.  This is a special case of that problem, and a much simpler solution is desired.


\end{document}
