Range Minimum Query basics

Question

I read the wikipedia link on Range Minimum Queries, looked at a couple more tutorials (topcoder and other links) but I have a very basic question:

Formal definitino of RMQ is : Given an array of objects taken from a well-ordered set (such as numbers), a Range Minimum Query (or RMQ) from to asks for the position of a minimum element in the sub-array .

What I don't understand is that why can't we solve the problem by linear search? In an array A[0...n], if we need RMQ(i,j)

min = A[i]
index = i
for iter=i; iter <j; iter ++
if A[iter] <= min
min = A[iter]
index = iter;

by the end of the loop, we know the min and the index where the min lies.

I am definitely missing something here...can someone help me understand why we need RMQ?

Answer 1

RMQ is meant to solve the problem you describe but way faster then your approach. There are two approaches - a static version where you do some precomputation(the most opitmized version that is really sophisticated takes linear precomputation) and after that answers constantly for each query, and dynamic apporach where you have log(n) time for each query.

In the static case you can not change the initial array, while in the dynamic it is permitted that its values change in time.

Note that in both cases you are meant to answer A LOT of queries. This means that answering in constant or logarithmic time will be way faster then your linear approach and thus will work in cases your idea is too slow. Hope this explains the idea.

Answer 2

Speed. Linear search is slow.

The same reason we use quick sort (or merge sort,...) and not a naive insertion sort for sorting large data bases.

Assume you have a huge data base, and you are going to query for RMQ millions of times. A linear search for each query is not efficient, it will require millions of linear searches, while the more advanced algorithms requires small pre-processing and then fast retrieval of the desired information.