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 kth 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.