[极力推荐]RMQ问题ST算法

1、RMQ问题ST算法/*RMQ(RangeMinimum/MaximumQuery)问题：RMQ问题是求给定区间中的最值问题。当然，最简单的算法是0(n)的，但是对于查询次数很多(设置多大100万次)，O(n)的算法效率不够。可以用线段树将算法优化到O(logn)(在线段树中保存线段的最值)。不过，Sparse_Table算法才是最好的：它可以在O(nlogn)的预处理以后实现O(1)的查询效率。下面把SparseTable算法分成预处理和查询两部分来说明(以求最小值为例)。预处理：预处理使用DP的思想，f(i,j)表示i,i+2勺-1区间中的最小值，我们可以开辟一个数组专门来保存f(i,j)的

2、值。例如，f(0,0)表示0,0之间的最小值,就是num0,f(0,2)表示0,3之间的最小值，f(2,4)表示2,17之间的最小值注意,因为f(i,j)可以由f(i,j-1)和f(i+2人(j-1),j-1)导出,而递推的初值(所有的f(i,0)=i)都是已知的所以我们可以采用自底向上的算法递推地给出所有符合条件的f(i,j)的值。查询：假设要查询从m到n这一段的最小值,那么我们先求出一个最大的k,使得k满足2人k=(n-m+1).于是我们就可以把m,n分成两个(部分重叠的)长度为2k的区间：m,m+2人k-1,n-2人k+1,n;而我们之前已经求出了f(m,k)为m,m+2k-1的最小值,

3、f(n-2k+1,k)为n-2k+1,n的最小值我们只要返回其中更小的那个,就是我们想要的答案,这个算法的时间复杂度是0(1)的.例如，rmq(0,11)=min(f(0,3),f(4,3)L*/#include#includevcmathusingnamespacestd;#defineMAXN1000000#definemmin(a,b)(a)v=(b)?(a):(b)#definemmax(a,b)(a)=(b)?(a):(b)intnumMAXN;intf1MAXN100;intf2MAXN100;测试输出所有的f(i,j)voiddump(intn)曰田inti,j;Ifor(i=0

4、;ivn;i+)for(j=0;i+(1vvj)-1n;j+)白由printf(f%d,%d=%dt,i,j,f1ij);printf(n);for(i=0;ivn;i+)printf(%d,numi);printf(n);for(i=0;ivn;i+)for(j=0;i+(1vvj)-1vn;j+)printf(f%d,%d=%dt,i,j,f2ij);printf(n);for(i=0;ivn;i+)printf(%d,numi);printf(n);/sparsetable算法voidst(intn)曰田inti,j,k,m;k=(int)(log(double)n)/log(2.0);

5、for(i=0;ivn;i+)f1i0=numi;/递推的初值f2i0=numi;for(j=1;jv=k;j+)/自底向上递推for(i=0;i+(1vvj)-1vn;i+)m=i+(1vv(j-1);/求出中间的那个值f1ij=mmax(f1ij-1,f1mj-1);f2ij=mmin(f2ij-1,f2mj-1);查询i和j之间的最值，注意i是从0开始的voidrmq(inti,intj)日田intk=(int)(log(double(j-i+1)/log(2.0),t1,t2;用对2去对数的方法求出kt1=mmax(f1ik,f1j-(1vvk)+1k);t2=mmin(f2ik,f2j-(1vvk)+1k);printf(%dn,t1-t2);intmain()日田inti,N,Q,A,B;scanf(%d%d,&N,&Q);for(i=0;ivN;+i)scanf(%d,num