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.