###
Fully-Functional Static and Dynamic Succinct Trees

####
Gonzalo Navarro and Kunihiko Sadakane

We propose new succinct representations of ordinal trees, and match various
space/time lower bounds. It is known that any *n*-node
static tree can be represented in *2n + o(n)* bits so that a number of
operations on the tree can be supported in constant time under the
word-RAM model. However, the data structures are complicated and
difficult to dynamize.
We propose a simple and flexible data structure, called the range min-max
tree, that reduces the large number of relevant tree operations considered in
the literature to a few primitives that are carried out in constant time on
polylog-sized trees. The result is extended to trees of arbitrary size,
retaining constant time and reaching *2n + O(n/polylog(n))* bits of
space. This space is optimal for a core subset of the operations supported,
and significantly lower than in any previous proposal.
For the dynamic case, where insertion/deletion (indels) of nodes is allowed,
the existing data structures support a very limited set of operations.
Our data structure builds on the range min-max tree to achieve
*2n + O(n/log n)* bits of space and *O(log n)* time for all the
operations supported in the static scenario, plus indels.
We also propose an improved data structure using
*2n + O(n log log n / log n)* bits and improving the time to the optimal
*O(log n / log log n)* for most operations. We extend our support to
forests, where whole subtrees can be attached to or detached from others, in
time *O(log^(1+e) n)* for any *e>0*. Such operations had
not been considered before.

Our techniques are of independent interest. An immediate derivation yields an
improved solution to range minimum/maximum queries where consecutive elements
differ by *+-1*, achieving *n + O(n/polylog(n))* bits of space. A second
one stores an array of numbers supporting operations *sumw* and
*search*
and
limited updates, in optimal time *O(log n / log log n)*. A third one
allows representing dynamic bitmaps and sequences over alphabets of size
*s*, supporting rank/select and indels, within zero-order entropy bounds
and time *O(log n log s / (log log n)^2)* for all operations.
This time is the optimal *O(log n / log log n)* on
bitmaps and polylog-sized alphabets.
This improves upon the best existing bounds for
entropy-bounded storage of dynamic sequences, compressed full-text
self-indexes,
and compressed-space construction of the Burrows-Wheeler transform.