# Looking for a succinct dynamic sorted dictionary

I was digging through research articles to find a data structure that solves the dynamic sorted dictionary problem (representing any subset $S$ of a universe $U = \{0, \ldots, u\}$ with member/predecessor/successor queries), but sadly I was able to find none. I did find succinct solutions to the following problems:

• Dynamic non-sorted dictionary
• Dynamic indexable bitvector (which is no good if the universe, say $[2^{64} - 1]$ is too big to store), not to mention storing a simple set, $\{u\}$ uses up the maximum amount of space
• Static indexable dictionaries

Dynamic succinct sorted/indexable dictionaries, however, do not seem to exist. (I do not actually need indexable dictionaries, just sorted ones with predecessor/successor queries, but it looks like this isn't really any easier to solve, either.)

What are some viable succinct data structures for solving this problem? Time bounds are not too important as long as they're not overly large (like $O(|U|)$). If there's no such data structure (yet), what is the second best option? Exponential search trees? Dynamic fusion trees? Multiple underlying data structures based on sparseness? (I prefer data structures with worst-time operation guarantees to those with amortized ones.)

• van Emde Boas trees? Oct 9, 2017 at 23:48
• What's wrong with a straightforward balanced search tree data structure? They support all of your operations, I think.
– D.W.
Oct 11, 2017 at 14:20
• The internal pointers take up lots of space, especially in the binary case. Oct 12, 2017 at 12:57

If you can tolerate $O(\sqrt{n})$ time complexity, I'd go for bi-parental heaps by Munro and Suwanda. This seems like an elegant implementation that should have $O(\sqrt{n})$ memory overhead in practice.
Theoretically, a solution with $O(\log n)$ time per operation is possible. See this extended abstract by Franceshini and Grossi, and my bachelor's thesis that goes into greater detail and fixes some of the bugs.