RMQ问题.ppt

RMQ问题 引例 【题目描述】 输入N个数和M次询问，每次询问一个区间[L,R],求第L个数到R个数之间的最大值。 【数据范围】 对于30%的数据，N=5000,M=5000; 对于100%的数据，N=106,M=106; 分析 【方法1】：朴素算法。时间复杂度为O(mn)，显然时间效率太低。 【方法2】：Sparse_Table算法（简称ST算法）才是最好的：它可以在O(nlogn)的预处理以后实现O(1)的查询效率，即整体时间复杂度为O(nlogn)-O(1)。 RMQ的定义 RMQ：Range Maximum(Minimum) Query的缩写，顾名思义是用来求某个区间内的最大值或最小值，通常用在需要多次询问一些区间的最值的问题中。 1.RMQ的预处理 【RMQ的原理】是动态规划 用 a[1..n]表示一组数，F[i,j]表示从a[i]到a[i+2^j-1]这个范围内的最大值，也就是以a[i]为起点连续2^j个数的最大值，由于元素个数为2^j个，所以从中间平均分成两部分，每一部分的元素个数刚好为2^(j-1)个，如下图： a[i] a[i+2^(j-1)] 很明显，整个区间的最大值一定是左右两部分最大值中的较大值，满足动态规划的最优性原理： 状态转移方程：F[i,j]=max(F[i,j-1],F[i+2^(j-1),j-1]) 边界条件为：F[i,0]=a[i] 我们可以采用自底向上的算法递推出所有符合条件的f[i,j]的值，就可以在O(nlogn)的时间复杂度内预处理F数组。 例如：f[2,3]保存的是a[2],a[3],a[4],……,a[9]中的最小值，而f[2,3]= min(f[2,2],f[6,2])=min((a[2],a[3],a[4],a[5]),(a[6],a[7],a[8],a[9])) 1.RMQ的预处理 预处理F数组代码： for(i=1;i=n;i++)f[i][0]=a[i]; //初始化 for(j=1;j=int(log(n)/log(2));j++) //递推 for(i=1;i+(1j)-1=n;i++) f[i][j]=max(f[i][j-1],f[i+(1(j-1))][j-1]); 1.RMQ的预处理 2.RMQ的查询 对于询问[L,R],求出最大的x,满足2^x=R-L+1,即x=int(log(R-L+1)/log(2)) [L,R]=[L,L+2^x-1] ∪[R+1-2^x,R]，两个子区间元素个数都是2^x个，如图 RMQ(L,R)=max(F[L,x],F[R+1-2^x,x]) 区间[L,L+2^x-1] 区间[R+1-2^x,R] 询问操作代码： int Ask(int L,int R) { int k; k=int(log(R-L+1)/log(2)); return max(f[L][k],f[R+1-(1k)][k]); } 该问题总时间复杂度为O(NlogN+M) 2.RMQ的查询 【例题1】区间问题1939 #includeiostream #includecmath #includecstdio using namespace std; int RMQ[1000001][23],n,m; int ASK(int L,int R) { int x=(int)(log(R-L+1)/log(2)); return max(RMQ[L][x],RMQ[R-(1x)+1][x]); } void ST() { int i,j; for(i=1;i=n;i++)cinRMQ[i][0]; for(j=1;j=(int)(log(n)/log(2));j++) for(i=1;i+(1j)-1=n;i++) RMQ[i][j]=max(RMQ[i][j-1],RMQ[i+(1j-1)][j-1]); } int main() { int i,x,y; cinnm; ST(); for(i=1;i=m;i++) { scanf(%d%d,x,y); printf(%d\n,ASK(x,y)); } } 【例题2】排队2591 【样例输入】 　6 3 　1 　7 　3 　4 　2 5 　1 5 　4 6 　2 2 【样例输出】 　6 　3 　0 题目大意:给你一串数字，然后问你从第i个到第j个中最大的数减去最小的数的值是