###
Asymptotically Optimal Encodings for Range Selection

####
Gonzalo Navarro, Rajeev Raman, and S. Srinivasa Rao.

We consider the problem of preprocessing an array *A[1..n]* to answer
*range selection* and *range top-k* queries. Given a query interval
*[i..j]* and a value *k*, the former query asks for the position of
the *k*th
largest value in *A[i..j]*, whereas the latter asks for the positions of all
the *k* largest values in *A[i..j]*. We consider the *encoding* version of
the problem, where *A* is not available at query time and a bound
*K* is
given
at construction time.
We obtain data structures with asymptotically optimal size and query time on
a RAM model with word size *Theta(lg n)*: our structures use
*O(n lg K)* bits and answer range selection queries in time
*O(1 + lg k / lg lg n)* and range top-*k* queries in time
*O(k)*,
for any *k <= K*.