st算法――RMQ的一个简单可行的算法 - QuarterGeek
RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。――百度百科
求出数组中任意区间[l,r]的最值，朴素的算法需要O(n)的时间。当询问特别多时，效率十分低。 st算法可以在O(nlogn)的时间内做完预处理，然后用O(1)的时间回答每一个问题。具体实现方法如下：（其实是一个动规^_^） 以求最大值为例。 用f[i,j]表示区间[i,i+2j-1]中的最大值。那么： f[i,j]=max(F[i,j-1],F[i+2j-1,j-1]) 预处理完后，对于询问求[a,b]的最大值。我们首先需要求出一个最大的整数x满足2x <=r-l+1那么，答案就是max(f[a,x],f[b+1-2x,x])。
由于pascal中，log2函数在math库中，使用还需uses math; 而ln则不需要使用任何的库，所以可以考虑换底公式： log a(b)=log c(b)/log c(a) 也就是log2(a)=ln(a)/ln(2)
例题如：Balanced Lineup,USACO 2007 January Silver（即PKU3264）。求区间的最大值-最小值。程序如下：
Read full article from st算法――RMQ的一个简单可行的算法 - QuarterGeek
No comments:
Post a Comment