range minimum query

In general, the range minimum query problem,called RMQ in shortly. it descripes this problem “Give you an array,you need to answer the query what the minimum value is in segment[i:j]”. We can divide this problem into two categories,that’s whether the element in the array can be modify.If yes,we may need other algorithms to solve this,such as segement tree etc.But today,I’d like to discuss the another one,that’s the without modifying one.

We can solve the above problem with dynamic programming solution.

step 1: preprocessing.

Let’s $dp[i][k]: $ the begin element is $a_i$,and the length is $2^k$ ,the minimum element in this range.

We can get an equation:

​ $dp[i][k] = min(dp[i][k-1],dp[i+(1<<(k-1))][k-1])$

It’s certainly right,and the preprocessing complexity is$O(NlogN)​$.that’s for the maximum of k is $logN​$.

step 2: query.

Now,we can focus on how to answer the query.give the conclusion:

$query(l,r)=min{dp[i][L],dp[j-L+1][L]}​$

$L=2^t$ stands the length which can cover at lease half of the segment’s length.

Why?

the below diagram can account for this.