一.概述
RMQ(Range Minimum/Maximum Query),即区间最值查询,是指这样一个问题:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j之间的最小/大值。这两个问题是在实际应用中经常遇到的问题,下面介绍一下解决这两种问题的比较高效的算法。当然,该问题也可以用线段树(也叫区间树)解决,算法复杂度为:O(N)~O(logN),这里我们暂不介绍
二.算法思路
1.首先利用dp预处理出从i点开始往后的2^j的最大值,dp的时候将其拆分成两段
2.查询出左端点以i开始,终点以j开始的最大值
一篇非常好的博客http://blog.csdn.net/liang5630/article/details/7917702
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 int a[2000001];
7 int minn[2000001][15];
8 int fastpow(int a,int p)
9 {
10 int base=a;
11 int ans=1;
12 while(p)
13 {
14 if(p%2)ans*=base;
15 base*=base;
16 p/=2;
17 }
18 return ans;
19 }
20 int main()
21 {
22 int n,m;
23 scanf("%d%d",&n,&m);
24 for(int i=0;i<=n;i++)
25 for(int j=0;j<=14;j++)
26 minn[i][j]=0x7ff;
27 for(int i=1;i<=n;i++)
28 scanf("%d",&minn[i][0]);// 第i个点跳1步能到达的点是其本身
29 for(int j=0;j<=14;j++)// 2^j
30 {
31 for(int i=1;i<=n;i++)// 根据dp的无后效性,要在j一定的情况下把每一个点跳完之后能到达的位置处理出来
32 {
33 if(i+(1<<j)-1<=n)// 第二段区间保证在范围之内
34 minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j]);
35 }
36 }
37 // 三段区间 i——i+2^(j-1)-1——i+2^j-1
38 printf("0\n");
39 int k=log(m)/log(2);// 保证求值区间的长度在要求的范围之内
40 // 带求区间 i-m to i
41 for(int i=2;i<=n;i++)
42 {
43 printf("%d\n",min(minn[i-m][k],minn[i-fastpow(2,k)+1][k]));
44 // 左端点 右端点
45 }
46 return 0;
47 }