Posted on 2011-03-26 10:13
Mato_No1 阅读(461)
评论(1) 编辑 收藏 引用 所属分类:
经典问题的模型
今天终于搞懂了RMQ问题无比神犇的ST算法……
【离线RMQ问题】
题意：对于一个序列A[1..N]，共有M次提问，每次都是问A[l..r]（1<=l<=r<=N)中的最值，求出每次提问的答案。
（1）纯暴力枚举：O(NM)；
（2）树状数组：O(M(logN)^2)【见
树状数组解决离线RMQ问题】
（3）ST算法：O(MlogN)……
ST算法是基于分块DP的。
设F[i][j]为A[i..(i+2^j-1)]（共2^j个元素）中的最值（前提是不能越界，即i+2^j-1 <= N），显然F可以通过DP的方式得到：
F[i][j] = min||max{F[i][j-1], F[i+2^(j-1)][j-1]}
边界：F[i][0]=A[i]。
DP求F的值的时间复杂度为O(NlogN)（一共只有NlogN个F值有意义）；
然后，对于求A[l..r]中的最值，只要将A[l..r]拆成若干连续的段，使得每段的长度都是2的整数次幂就行了，比如A[3..28]可以拆成A[3..18]、A[19..26]、A[27..28]三段，长度分别是16（2^4）、8（2^3）、2（2^1），所以min||max{A[3..28]} = min||max{F[3][4], F[19][3], F[27][1]}。
关键是怎么拆？方法：求出(r-l+1)（即A[l..r]的长度）的二进制形式，然后从高位到低位依次遍历，如果找到1位就加上目前的位对应的幂，如(28-3+1)=(11010)2，所以依次找到F[3][4]、F[3+2^4][3]、F[3+2^4+2^3][1]。注意此时需要预先设一个数组B，B[2^i]=i，以方便找到某个取出的幂对应的指数。
显然，最多只有logN段，所以一次提问的时间复杂度为O(logN)。
其实还有一种方法，就是先求出log(r-l+1)的值（下取整），设为x，然后F[l][x]和F[r-2^x+1][x]中的较大/较小值就是A[l..r]中的最值。这样，一次提问的时间复杂度就降到了O(1)。问题是，系统log函数灰常慢，也许算一次log函数值的时间已经超过了logN，这样显然得不偿失。所以仍然推荐上面的方法。
【核心代码（以求最小值为例，最大值类似）】
分段法：
int MIN(int l0, int r0)
{
int min = INF, h = l0, d0, b0;
for (int d = r0 - l0 + 1; d; d -= d0) {
d0 = d & -d; b0 = B[d0];
if (F[h][b0] < min) min = F[h][b0];
h += d0;
}
return min;
}
求log值法：
int MIN(int l0, int r0)
{
int v = (int)floor(log2(r0 - l0 + 1.0)), s1 = F[l0][v], s2 = F[r0 - (1 << v) + 1][v];
return s1 <= s2 ? s1 : s2;
}
求F数组值的预处理代码（注意，如果采用求log值的方法就不需要B数组了）：
void prepare()
{
re(i, n) F[i][0] = a[i];
int x;
re2(j, 1, MAXS) {
if ((1 << j) <= n) B[1 << j] = j;
x = n - (1 << j) + 1;
re(i, x) F[i][j] = min(F[i][j - 1], F[i + (1 << j - 1)][j - 1]);
}
}
【后经效率测试，发现当N=M=100000的随机数据中，两种方法都可以在0.4s以内得出正确结果，其中log值法比分段法略慢0.01s左右，相差不大，但考虑到“尽量少使用数学函数”的原则，仍推荐分段法】