基于ST表的RMQ算法

作者: zqqian 分类: ACM,算法 发布时间: 2017-08-09 23:46

基于ST表的RMQ算法可以在O(1)的时间复杂度内计算出一个区间内的最值。

基本思想是将一段长度中的最值保存下来。查询的时候直接返回。避免了常规算法中的一次一次比较的操作。

详细请参考书籍:《算法竞赛入门经典训练指南》–刘汝佳

这里仅谈论我自己的理解。


对于长度为n的数组,我们可以知道其二叉树深度不会超过log2 n。

此时就可以创建一个二维数组d[n][logn]。

d[i][j]代表以i为起点,长度为2^j区间上的最值。

在输入进数组之后,首先将d[i][0]赋值为a[i],

然后使用循环

 

以上就是预处理操作。

for(int j=1;n-(1<<j)>=0;j++){// warning! this is j ! 

for(int i =1; i<=(n-(1<<j));i++){

d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);

}

}

 

而查询[l,r)区间内的最大值的操作为

 

 

int query(int l,int r){

int x=0;

while(l+(1<<x)<r+1){ // find the max of x which 2^x <= r-l+1;

x++;

}

return max(d[l][x],d[r-(1<<x)+1][x]);// warning ! this must  is r-(1<<x)+1 ! 

}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注