本文主要是介绍POJ 3264(ST实现RMQ)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题目大意：给一个n和q，n代表有n个数，q代表q次查询。每次查询输入两个数字a,b，问你从第a个数字到第b个数字间的最大值减去最小值的值是多少。
题目思路：如果直接搜，查一次就O（n），铁定爆炸。这里线段树和ST算法都可以，线段树好像挺麻烦先学一波ST解法一会儿去学线段树，美滋滋。不过像这种单纯的求区间最值的问题，还是用ST比较好，因为ST算法预处理nlogn，查询都是O（1），非常强悍，线段树构树nlogn，查询logn，而且有很大的常数，所以本题用ST更好一些。本题代码参考kuangbin大神本题代码，非常感谢！
ST算法：
ST算法是求解RMQ问题的一种经典算法，RMQ问题就是求一个区间内的最值的问题。上面已经简单的说明了ST算法的优越性，nlogn预处理后就可以O1查询。这里讲一下他是怎么实现的。
ST算法的预处理用到了DP的思想。这里以求区间最小值为例子，mn[i][j]表示从第i个数字开始2^j个数字中的最小值大小。其动态转移方程为mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1])。介绍一下，由上，mn[i][j]是从第i个数字开始，2^j个数字钟的最小值，我们把它分为两部分，比如mn[1][2]，就是从1开始2^2=4个数字，1,2,3,4中的最小值，由于j不断变大，所以此时两个数字的情况我们已经知道了，也就是求mn[1][1],mn[3][1]我们已经了解了，我们知道1 2中的最小值，3 4中的最小值，俩比一下就知道了1 2 3 4中的最小值，是不是很棒呢..
接下来说ST算法的查询，其实也是把它分成两半，要是不能正好分成两半咋办呢..没事啊，有重叠部分也不会影响结果的呀..所以比如我们求1~6的区间最小，我们可以吧1~4(mn[1][2])和3~6(mn[3][2])拿出来就可以算出来了，非常强势。怎么分呢？两个数字之间一共有y-x+1个数字，然后+1取对数log2(y-x+1)就可以啦，这样2^k就肯定可以满足把这俩分成两半后没有数字落下，很棒
以下是代码：
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
#define MAXN 50005
int n,q,dpMax[MAXN][20],dpMin[MAXN][20],a[MAXN];
void makeMax(){for(int i=1;i<=n;i++){dpMax[i][0]=a[i];}for(int j=1;(1<<j)<=n;j++){for(int i=1;i+(1<<j)-1<=n;i++){dpMax[i][j]=max(dpMax[i][j-1],dpMax[i+(1<<(j-1))][j-1]);}}
}
int getMax(int x,int y){int k=(int)(log(y-x+1.0)/log(2.0));return max(dpMax[x][k],dpMax[y-(1<<k)+1][k]);
}
void makeMin(){for(int i=1;i<=n;i++){dpMin[i][0]=a[i];}for(int j=1;(1<<j)<=n;j++){for(int i=1;i+(1<<j)-1<=n;i++){dpMin[i][j]=min(dpMin[i][j-1],dpMin[i+(1<<(j-1))][j-1]);}}
}
int getMin(int x,int y){int k=(int)(log(y-x+1.0)/log(2.0));return min(dpMin[x][k],dpMin[y-(1<<k)+1][k]);
}
int main(){while(~scanf("%d%d",&n,&q)){int x,y;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}makeMax();makeMin();for(int i=0;i<q;i++){scanf("%d%d",&x,&y);printf("%d\n",getMax(x,y)-getMin(x,y));}}return 0;
}这篇关于POJ 3264(ST实现RMQ)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
