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