How Fast Can You RMQ?Computer Science Level 3
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.