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.