RMQ - wyiu - C++博客

C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合

:: 管理

posts - 100, comments - 15, trackbacks - 0

RMQ

//Sparse Table(ST)，动态规划，<O(N logN), O(1)>

void 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

int 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

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 阅读(158) 评论(0) 编辑收藏引用所属分类: 算法

只有注册用户登录后才能发表评论。


相关文章: Pick定理（很牛的定理） [转] 计算几何常用算法概览计算几何常用算法概览关于“逆序数”[转] 并查集及其应用[转] RMQ 线段树入门(转) Bellman-Ford 算法[转]

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

随笔分类(84)