LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations
Jérémy Barbay, Johannes Fischer, and Gonzalo Navarro
LRM-Trees are an elegant way to partition a sequence of values into
sorted consecutive blocks, and to express the relative position of
the first element of each block within a previous block. They were
used to encode ordinal trees and to index integer arrays in order to
support range minimum queries on them. We describe how they yield
many other convenient results in a variety of areas: compressed
succinct indices for range minimum queries on partially sorted
arrays; a new adaptive sorting algorithm; and a compressed succinct
data structure for permutations supporting direct and inverse
application in time inversely proportional to the permutation's
compressibility.