在求解RMQ问题中,ST算法是一把利器,ST算法是倍增思想的产物.给定长度为N的序列A,ST算法可以在O(NlogN)时间的预处理后,用O(1)的时间查询得到答案,在线回答”序列A在下标l~r之间最大的数是多少”这样的问题.
我们用F[i,j]表示序列A中下标在子区间[i,i + 2^j - 1]里的数的最大值,也就是从i开始的2^j个数的最大值.显然递推的边界是F[i,0] = A[i],即在子区间[i, i]里的最大的数就是其本身.
有F[i,j] = max(F[i,j - 1], F[i + 2^j-1,j - 1]),就是把长度为2^j的区间划分成左右长度为2^j-1两个区间,
分别求最值然后得到最终的最值.

void ST()
{
    for(int i = 1; i <= n; i ++)   f[i][0] = a[i]; //递推边界
    for(int j = 1; (1 << j) <= n; j ++)//区间长度
        for(int i = 1; i + (1 << j) - 1 <= n; i ++)//区间左端点
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

接下来,要怎么查询区间最值呢?我们得先明白,我们得到的区间最值中区间的长度都是2的整数次幂,有时候我们求的区间长度可能不是2的整数次幂,我们可以用区间覆盖的方法得到答案.
首先,我们得到一个整数k,满足2^k <= (r - l + 1) <= 2^(k+1), 接着我们分别求出子区间[l, l + 2^k - 1]和[r - 2^k + 1, r]的最值,最后再得出最后的最值,因为这两个区间必定可以覆盖[l, r]所以一定可以得到结果

int ST_query(int l, int r)
{
    int k = log2(r - l + 1);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}