RMQ问题

Posted on 2011-03-26 10:13 Mato_No1 阅读(447) 评论(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左右,相差不大,但考虑到“尽量少使用数学函数”的原则,仍推荐分段法】


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理