首页 > 代码库 > RMQ

RMQ

2024-10-18 17:28:02   210人阅读

也是一大神器，起码以后不用敲线段树的求区间的线段树了。

代码30行左右 ，效率肯定比线段书快不少

还有为以后写在线的LCA算法做个铺垫。

思路比较简单，这里引荐不少优秀的博文。

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Range_Minimum_Query_%28RMQ%29

topcoder也有不少介绍算法的优秀博文

http://dongxicheng.org/structure/lca-rmq/ 

还有这个博客

然后是模板： 1 #include<iostream>

 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<string>
 7 #include<vector>
 8 using namespace std;
 9 #define N 51111
10 int n,m;
11 int a[N];
12 int dp[N][20];
13 
14 void RMQ()
15 {
16    // int tmp=log((double)n)/log(2.0);
17     for (int i=1;i<=n;i++)
18     dp[i][0]=a[i];
19     for (int j=1;j<=log(n)/log(2);j++)
20     for (int i=1;i<=n;i++)
21     if (i+(1<<j)-1<=n)
22     dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
23 }
24 
25 int Min(int l,int r)
26 {
27     int k=log(r-l+1)/log(2.0);
28     return min(dp[l][k],dp[r-(1<<k)+1][k]);
29 }
30 
31 int main()
32 {
33     scanf("%d%d",&n,&m);
34     for (int i=1;i<=n;i++)
35     scanf("%d",&a[i]);
36     RMQ();
37     while (m--)
38     {
39         int x,y;
40         scanf("%d%d",&x,&y);
41         printf("%d\n",Min(x,y));
42     }
43     return 0;
44 }

RMQ


联系
我们