Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets

Rajeev Raman, Venkatesh Raman, Srinivasa Rao Satti

We consider the {\it indexable dictionary} problem, which consists of storing a set $S\subseteq \{0,...,m-1\}$ for some integer $m$, while supporting the operations of $\Rank(x)$,…