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 would not be useful when your list contains 100,000,000 numbers. For this reason, you may use only up to 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 and query of , your answer should be
Clarification : denotes the factorial function.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Let's take a look at each runtime:
O ( n ! ) :
I suppose you could take a subsection of a list and permute it until you find the smallest element at position 1; this would indeed be O ( n ! ) .
O ( n ) :
The naive solution to this problem uses no preprocessing, and simply iterates over the range of elements given. This is O ( n ) per query.
O ( lo g n ) :
Many of you may be familiar with the data structure known as the "Segment Tree." Segment trees are a very good solution to the RMQ problem, and work by splitting the total list up into progressively smaller intervals. This will run in O ( lo g n ) , the time to traverse the tree from the top to the bottom.
O ( 1 ) :
The downfall of the segment tree is that it has capability for updates. If we ignore the need to update the list, and focus only on queries, we can solve the problem in O ( 1 ) , using a data structure known as the "Sparse Table". If you are interested on implementation, a quite good overview is given in chapter 9 of "Competitive Programming" by Steven and Felix Halim.