资源描述：
《rmq问题地st算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、实用文案ST算法求解RMQ问题 RMQ(RangeMinimum/MaximumQuery)问题是求区间最值问题。可以写一个线段树，但是预处理和查询的复杂度都是O（logn)。这里有更牛的算法，就是ST算法，它可以做到O(nlogn)的预处理，O(1)！！！地回答每个询问。 来看一下ST算法是怎么实现的(以最大值为例）： 首先是预处理，用一个DP解决。设a[i]是要求区间最值的数列，f[i,j]表示从第i个数起连续2^j个数中的最大值。例如数列3245681297,f[1，0]表示第1个数起，长度为2^0=1的最大值，其实就
2、是3这个数。f[1，2]=5，f[1，3]=8，f[2，0]=2，f[2，1]=4……从这里可以看出f[i,0]其实就等于a[i]。这样，Dp的状态、初值都已经有了，剩下的就是状态转移方程。我们把f[i，j]平均分成两段（因为f[i，j]一定是偶数个数字），从i到i+2^(j-1)-1为一段，i+2^(j-1)到i+2^j-1为一段(长度都为2^（j-1）)。用上例说明，当i=1，j=3时就是3,2,4,5和6,8,1,2这两段。f[i，j]就是这两段的最大值中的最大值。于是我们得到了动规方程F[i,j]=max（F[i，j-1],F[i+2^(j
3、-i)，j-1]）. 接下来是得出最值，也许你想不到计算出f[i，j]有什么用处，一般毛想想计算max还是要O(logn)，甚至O(n)。但有一个很好的办法，做到了O（1）。还是分开来。如在上例中我们要求区间[2，8]的最大值，就要把它分成[2,5]和[5,8]两个区间，因为这两个区间的最大值我们可以直接由f[2，2]和f[5，2]得到。扩展到一般情况，就是把区间[l，r]分成两个长度为2^n的区间（保证有f[i，j]对应）。直接给出表达式： f[i,j]表示从第i个数数2^j中最小的数那么： 最大值f[i,j]=max(
4、f[i,j-1],f[i+2^(j-1),j-1]); 最小值f[i,j]=min(f[i,j-1],f[i+2^(j-1),j-1]);RMQ问题ST算法与模板2007-07-1515:48-------------------------------------算法简述-----------------------------------------ST算法O(nlogn)预处理,O(1)的查询指定区间的最值(以最小值为例)基本上是把待求区间[l,r]分为两段长为len的区间左边一段为[l,l+len-1],右边一段为[r-len+
5、1,r]len必须使得两段区间覆盖待求区间设所求数组为w标准文档实用文案那么,所求最小值就是两个区间的最小值间的最小值即min(min{w[i],l<=i<=l+len-1},min{w[j],r-len+1<=j<=r})若都在预先处理中先求得两个区间的最小值则每次查询的复杂度都是O(1)--- 对len做一个限制:只能为2的幂在预处理中求出所有mi[b][t]:以b为起点,长为2^t的区间的最小值.则求解min(min{w[i],l<=i<=l+len-1},min{w[j],r-len+1<=j<=r})就变成min(mi[l][t],mi[
6、r-2^t+1][r]),其中t可以由此得出,以保证两段区间可以覆盖待求区间:t=ln(r-l+1)/ln(2)--- 可以看到mi[b][t]=min(mi[b][t-1],mi[b+2^(t-1)-1][t-1])特别地对于所有mi[i][0],其值都是w[i];由此自底向上推出所有的mi[b][t]mi大小为n*logn,预处理时间复杂度为O(nlogn),查询时间复杂度为O(1)-----------------------------------------------------代码---------------------------
7、---------------------------在POJ上测试,反应良好~不知道怎么样把函数指针指向任意类型的<操作符,只能总是提供一个"小于"函数查询指定区间的最小值标准文档实用文案模板：#include #include #define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b)) using namespace std; const int maxn=50001; int h[maxn]; int mx[maxn][16],m
8、n[maxn][16];int n,q; void rmq_init() { int i,j; for(
