• 1 Introduction
    • 1.1 Applications
    • 1.2 Range-minimum queries, Cartesian trees and lowest common ancestors
    • 1.3 Related Work
  • 2 Notation and Preliminaries
    • 2.1 Bit vectors
    • 2.2 Variable-cell arrays
    • 2.3 Compressed piecewise-constant arrays
  • 3 Random RMQ and random BSTs
  • 4 Lower bound
  • 5 An optimal encoding: subtree-size code
    • 5.1 Bounding the worst case
  • 6 Tree Covering
    • 6.1 Trees, mini trees, micro trees
    • 6.2 Tree decomposition
    • 6.3 Node ids: -names
    • 6.4 Lowest common ancestors
    • 6.5 Inorder rank and select
  • 7 Entropy trees
  • 8 Hyper-succinct trees
  • References