Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space

Mar 2019 (Written: Feb 2019)

J. Ian Munro, and Sebastian Wild:

arxiv preprint 1903.02533

In this paper, we start the study of distribution-succinct data structures, i.e., data structures that have (asymptotically) optimal expected space usage (as opposed to only optimal worst case) for a certain data-structuring task.

We give such a distribution-succinct data structure for representing

An average-case space-optimal data structure for the RMQ problem was posed as open problem by Davoodi et al (2014).