How Fast Can You RMQ?

The "range minimum query" (RMQ) is the problem of finding the index in a range [A, B] such that the value of the array at that index is the least of any in [A, B].

There exist numerous algorithms for RMQ. Which is the fastest possible runtime for querying.

Note: Your algorithm must be applicable to large data easily. The solution of storing every interval [A, B] in a table, and preprocessing in $$O(n^3)$$ would not be useful when your list contains 100,000,000 numbers. For this reason, you may use only up to $$O(n \log n)$$ preprocessing time for the purposes of this problem.

Note 2: In general, problems like RMQ are split into two chunks: preprocess, and query. This problem concerns itself only with the query time as the answer. If you have an algorithm with preprocess of $$O(1)$$ and query of $$O(n)$$, your answer should be $$O(n)$$

Clarification: $$!$$ denotes the factorial function.

×