【转】RMQ-ST算法详解

RMQ(Range Minimum/Maximum Query)问题就是求区间最值问题。这里要仔细分析的是ST算法，它可以做到O(nlogn)的预处理，O(1)回答每个询问。

网上看了好多关于ST算法的文章，还算是有点理解了。

st算法，本质就是一个DP。

有一个数字序列记为L,比如这里给了

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

35 13 65 99 88 75 64 51 42 55 66 83 12 44 65 12

f[i,j]表示的是从i开始的2^j个数里面的最值。以最大值来举例说明。

f[1,0]就是从第一个开始的1个里最大值，那么就是第一个自己本身，f[1,0]=35;

f[2,2]就是从第二个开始的4个里最大值，那么是13,65,99,88里面的最大值，明显是f[2,2]=99；

以此类推。

先前说了，是DP。状态转移方程就是。

f[i,j]=max(f[i,j-1],f[i+2^(j-1),j-1]);

比如f[5,3],包含的值有88 75 64 51 42 55 66 83。

求它的最大值，用二分的思想，就是[88 75 64 51],[42 55 66 83]的最大值中较大的。

即f[5,2] 和 f[9,2]。

以此类推，求i至其后2^j个数的最大值，即把2^j 分成前后两个2^(j-1)，分别取其最大值，再通过比较获得此状态最大值。

以上是f数组的构造。

以下才回归到RMQ问题。

貌似，对于任意的i至j之间的最值，和之前构造的f数组有什么关系呢?

我们可以知道，任意的i至j之间的j-i+1个连续的值，一定可以分成两个2^n个数的两个区域（可以重合）。

比如说要求3到11之间的最值。

那么可以通过3到10之间的最值和4到11之间的最值求得3到11之间的最值，那么就可以和之前的f数组联系在一起了。

有j-i+1是个数，p=2^( (int) (log(2,j-i+1)) )就是可以连续分的最大2^n大小的块（不难理解）。

比如3到11之间的9个元素，最大可以分8大小的块。

3～10，4～11(从头开始数8个，从尾开始数8个)

那么就是计算 i~i+p-1，j-p+1~j的最值，每一个区域的个数是p个。

那么可以转化为f数组的f[i,log(2,p)]，f[j-p+1,log(2,p)]两个范围。

即是计算

k=(int)(ln(j-i+1)/ln(2));

rmq(i,j)=max(f[i,k],f[i-2^k+1,k]);

理解为主，不然很容易搞错其中的+1 -1；

巴特西