RMQ (Range Minimum/Maximum Query)问题是指:
对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在[i,j]里的最小(大)值,也就是说...query(1, 0, sizeof(a)/sizeof(a[0])-1, M, a, 0, 5)<<endl;
67 return 0;
68 }
ST算法(Sparse Table):它是一种动态规划的方法...这个算法的高明之处不是在于这个动态规划的建立,而是它的查询:它的查询效率是O(1).
假设我们要求区间[m,n]中a的最小值,找到一个数k使得2^k<n-m+1....这样,可以把这个区间分成两个部分:[m,m+2^k-1]和[n-2^k+1,n].我们发现,这两个区间是已经初始化好的.
前面的区间是f(m,k),后面的区间是f(n-2^k+1,k)....ST算法
12 *构造RMQ数组 makermq(int n,int b[]) O(nlog(n))的算法复杂度
13 *dp[i][j] 表示从i到i+2^j -1中最小的一个值(从i开始持续2^j