  We consider the problem of maintaining a dynamic set of integers and
answering queries of the form: report a point (equivalently, all points) in a
given interval. Range searching is a natural and fundamental variant of integer
search, and can be solved using predecessor search. However, for a RAM with
w-bit words, we show how to perform updates in O(lg w) time and answer queries
in O(lglg w) time. The update time is identical to the van Emde Boas structure,
but the query time is exponentially faster. Existing lower bounds show that
achieving our query time for predecessor search requires doubly-exponentially
slower updates. We present some arguments supporting the conjecture that our
solution is optimal.
  Our solution is based on a new and interesting recursion idea which is "more
extreme" that the van Emde Boas recursion. Whereas van Emde Boas uses a simple
recursion (repeated halving) on each path in a trie, we use a nontrivial, van
Emde Boas-like recursion on every such path. Despite this, our algorithm is
quite clean when seen from the right angle. To achieve linear space for our
data structure, we solve a problem which is of independent interest. We develop
the first scheme for dynamic perfect hashing requiring sublinear space. This
gives a dynamic Bloomier filter (an approximate storage scheme for sparse
vectors) which uses low space. We strengthen previous lower bounds to show that
these results are optimal.
