# Optimal Space-Time Dictionaries over an Unbounded Universe with Flat Implicit Trees

In the classical dictionary problem, a set of $n$ distinct keys over
an unbounded and ordered universe is maintained under insertions and
deletions of individual keys while supporting search operations. An
implicit dictionary has the additional constraint of occupying the
space merely required by storing the~$n$~keys, that is, exactly $n$
contiguous words of space in total. All what is known is the
starting position of the memory segment hosting the keys, as the
rest of the information is implicitly encoded by a suitable
permutation of the keys. This paper describes the flat implicit
tree, which is the first implicit dictionary requiring $O(\log n)$
time per search and update operation.