Range quantile queries: Another virtue of wavelet trees
Travis Gagie, Simon J. Puglisi, Andrew H. Turpin · 2009
Abstract. We show how to use a balanced wavelet tree as a data struc-ture that stores a list of numbers and supports efficient range quantile queries. A range quantile query takes a rank and the endpoints of a sub-list and returns the number with that rank in that sublist. For example, if the rank is half the sublist’s length, then the query returns the sub-list’s median. We also show how these queries can be used to support space-efficient coloured range reporting and document listing. 1