posts - 100,  comments - 15,  trackbacks - 0
RMQ
//Sparse Table(ST),动态规划,<O(N logN), O(1)>
 1void rmq_init()
 2{
 3    int i,j;
 4    for(j=1;j<=n;j++) mx[j][0]=d[j];
 5    int m=floor(log((double)n)/log(2.0));
 6    for(i=1;i<=m;i++)
 7        for(j=0;j+(1<<(i-1))<=n;j++)
 8            mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
 9}

10
11int rmq(int l,int r)
12{
13    int m=floor(log((double)(r-l+1))/log(2.0));
14    int a=max(mx[l][m],mx[r-(1<<m)+1][m]);
15    return a;  
16}

17
18

RMQ介绍:http://baike.baidu.com/view/1536346.htm
摘自某人文章:http://blog.sina.com.cn/s/blog_4d88e9860100cthl.html
posted on 2009-04-14 00:40 wyiu 阅读(167) 评论(0)  编辑 收藏 引用 所属分类: 算法

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