ST求RMQ

思路f[i][k]表示一个从i起始、长度为$2^k$的区间中的最值
易得一个状态转移方程：

$$f[i][k]=max \left \{ \begin{aligned} f[i][k-1]\\ f[i+2^{k-1}][k-1] \end{aligned} \right.$$
查询[l,r]区间最值：
$$ans=max \left \{ \begin{aligned} f[l][k]\\ f[r+1-2^k][k] \end{aligned} \right.$$
时间复杂度：

• 初始化$O(Nlog_2N)$
• 查询$O(1)$

int f[MAXN + 1][MAXM + 1];
int a[MAXN + 1];
int n;
void Init()
{
    for(int i = 1; i <= n; i ++)
        f[i][0] = a[i];
    for(int k = 1; (1 << k) <= n; k ++)
        for(int i = 1; i + (1 << k) - 1 <= n; i ++)
            f[i][k] = max(f[i][k - 1], f[i + (1 << (k - 1))][k - 1]);
}
int RMQ(int l, int r)
{
    int k = 0;
    while( (1 << (k + 1)) <= r - l + 1 ) k ++;
    return max( f[l][k], f[r + 1 - (1 << k)][k] );
}