RMQ问题ST算法 POJ 3264

ST算法O(nlogn)预处理,O(1)的查询指定区间的最值(以最小值为例)

基本上是把待求区间[l,r]分为两段长为len的区间

左边一段为[l,l+len-1],右边一段为[r-len+1,r]

len必须使得两段区间覆盖待求区间

设所求数组为w

那么,所求最小值就是两个区间的最小值间的最小值

即min(min{w[i],l<=i<=l+len-1},min{w[j],r-len+1<=j<=r})

若都在预先处理中先求得两个区间的最小值

则每次查询的复杂度都是O(1)

---

对len做一个限制:只能为2的幂

在预处理中求出所有mi[b][t] : 以b为起点,长为2^t的区间的最小值.

则求解min(min{w[i],l<=i<=l+len-1},min{w[j],r-len+1<=j<=r})

就变成min(mi[l][t],mi[r-2^t+1][r]),其中t可以由此得出,以保证两段区间可以覆盖待求区间:

t=ln(r-l+1)/ln(2)

---

可以看到mi[b][t]=min(mi[b][t-1],mi[b+2^(t-1)-1][t-1])

特别地对于所有mi[i][0],其值都是w[i];

由此自底向上推出所有的mi[b][t]

mi大小为n*logn,预处理时间复杂度为O(nlogn),查询时间复杂度为O(1)


#include <iostream>
 #include <math.h>
 #define max(a,b) ((a>b)?a:b)
 #define min(a,b) (a<b?a:b)
 
using namespace std;
 
const int maxn=50001;
 int h[maxn];
 int mx[maxn][16],mn[maxn][16];
int n,q;
 
 void rmq_init()
 {
     int i,j;
     for(j=1;j<=n;j++) mx[j][0]=mn[j][0]=h[j];
     int m=floor(log((double)n)/log(2.0));
     for(i=1;i<=m;i++){
         for(j=n;j>0;j--){
             mx[j][i]=mx[j][i-1];
             if(j+(1<<(i-1))<=n) mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
         }
    }
    for(i=1;i<=m;i++){
         for(j=n;j>0;j--){
            mn[j][i]=mn[j][i-1];
             if(j+(1<<(i-1))<=n) mn[j][i]=min(mn[j][i],mn[j+(1<<(i-1))][i-1]);
         }
     }
 }
 
 int rmq(int l,int r)
 {
     int m=floor(log((double)(r-l+1))/log(2.0));
    int a=max(mx[l][m],mx[r-(1<<m)+1][m]);
     int b=min(mn[l][m],mn[r-(1<<m)+1][m]);
    return a-b;  
 }
 
 int main()
 {
     int i,l,r;
     scanf("%d%d",&n,&q);
     for(i=1;i<=n;i++) scanf("%d",&h[i]);
     rmq_init();
     for(i=0;i<q;i++){
         scanf("%d%d",&l,&r);
         printf("%d\n",rmq(l,r));
     }

 }

posted on 2008-05-19 20:52 Victordu 阅读(2545) 评论(2)  编辑 收藏 引用

评论

# re: RMQ问题ST算法 POJ 3264 2008-09-18 19:52 刘刘牛

"就变成min(mi[l][t],mi[r-2^t+1][r]),其中t可以由此得出,以保证两段区间可以覆盖待求区间:

t=ln(r-l+1)/ln(2) "


是不是有点问题呢?


  回复  更多评论   

# re: RMQ问题ST算法 POJ 3264 2009-04-11 14:22 Wei Quan Min

Great.....

Can u write sth about suffix array + lcp in the next thread....

I am not really clear about suffix array. Clear about the O(n^2 log n)..
but I'm curious about O(n log n) which is solved by using lcp..

Thx  回复  更多评论   


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


导航

<2008年5月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

统计

常用链接

留言簿(5)

随笔档案(46)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜