All Publications

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

| read herePDFarXivslides |

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).

Connection of RMQ and LCA queries
An example illustrating the close connection of range-maximum queries on an array and lowest common ancestor queries in binary trees.