Succinct indexable dictionaries with applications to encoding k-ary trees and multisets

We consider the indexable dictionary problem, which consists of storing a set S ⊆ 0,. . . , m − 1 for some integer m, while supporting the operations of rank (x), which returns the number of elements in S that are less than x if x ∈ S, and −1 otherwise; and select (i) which returns the i-th smallest element in S. We give a data structure that supports both operations in O (1) time on the RAM model and requires B (n, m) + o (n) +O (lg lg m) bits to store a set of size n, where B (n, m) = ⌈ lg (m) ⌉ n is the minimum number of bits required to store any n-element subset from a universe of size m. Previous dictionaries taking this space only supported (yes/no) membership queries in O (1) time. In the cell probe model we can remove the O (lg lg m) additive term in the space bound, answering a question raised by Fich and Miltersen, and Pagh. We present extensions and applications of our indexable dictionary data structure, including: • an information-theoretically optimal representation of a k-ary cardinal tree that supports standard operations in constant time, • a representation of a multiset of size n from 0,. . . , m − 1 in B (n, m+n) + o (n) bits that supports (appropriate generalizations of) rank and select operations in constant time, and • a representation of a sequence of n non-negative integers summing up to m in B (n, m + n) + o (n) bits that supports prefix sum queries in constant time. 1