Encoding Range Minima and Range Top-2 Queries
Pooya Davoodi, Gonzalo Navarro, Rajeev Raman, and S. Srinivasa Rao.
We consider the problem of encoding range minimum
queries (RMQs): given an array A[1..n] of distinct
totally ordered values, to pre-process A and create a
data structure that can answer the query RMQ(i,j),
which returns the index containing the smallest
element in A[i..j], without access to the array A at query
time. We give a data structure whose space usage
is 2n + o(n) bits, which is asymptotically optimal for
worst-case data, and answers RMQs in O(1) worst-case time.
This matches the previous result of Fischer
and Heun, but is obtained in a more natural way.
Furthermore, our result can encode the RMQs of a
random array A in 1.919n + o(n) bits in expectation,
which is not known to hold for Fischer and Heun's
result. We then generalize our result to the encoding
range top-2 query (RT2Q) problem, which is like
the encoding RMQ problem except that the query
RT2Q(i,j) returns the indices of both the smallest and
second-smallest elements of A[i..j]. We introduce a
data structure using 3.272n + o(n) bits that answers
RT2Qs in constant time, and also give lower bounds
on the effective entropy of RT2Q.