RMQ入门解析

参照大佬博客：https://www.cnblogs.com/yoke/p/6949838.html

RMQ(Range Minimum/Maximum Query),  是一种问题，即 查询给定区间的最大值或最小值。

ST算法可在线处理RMQ问题，主要分为两步， 初始化 和 查询。

ST算法的思想是将一个区间平均分成两个子区间，分别查询两个子区间的最值，再求这两个最值的最值。因此是DP的思想。

F[i,j] 代表以con[i]为区间左值，长度为 2^j 的区间的最大(小)值。

初始化：

　　DP初始状态为

　　for(int i = 0; i < n; i++)

　　　　F[i,0] = con[i];  // 此时的最值是他本身 

　

　　状态转移方程为

　　　　

void RMQ(int num) //预处理->O(nlogn)
{
    for(int j = 1; j < 20; ++j)    // 这里j的范围根据具体题目数据定义
        for(int i = 1; i <= num; ++i)    // num为数组内整数的个数
            if(i + (1 << j) - 1 <= num)
            {
                maxsum[i][j] = max(maxsum[i][j - 1], maxsum[i + (1 << (j - 1))][j - 1]);
                minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]);
            }
}

　　注意只有长度为2^(j - 1)的区间最值查询出来后，才可以查询长度为 2^j 的区间，因此代码中两个for循环的位置不可交换。

  查询为   

　　RMQ(A, i, j)=max{F[i , k], F[ j - 2 ^ k + 1, k]}。 

　　为什么第二个子区间是从j减，因为允许分成的两个子区间有重叠的部分(解决了有的区间不能分成两个互不重叠的 长度为 2^j 的区间的问题 )。