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
- binary search tree generated from random insertions (random BSTs) and
- for answering range-minimum queries (RMQ).
An average-case space-optimal data structure for the RMQ problem was posed as open problem by Davoodi et al (2014).