倍增

任意一个数可以由二进制表示，如31 = 2^0 + 2^1+ 2^2 + 2^3 + 2^4，且最少是由这五个数表示的。 倍增就是说用最少的步骤（五个数字）得到最大的范围（31）的思想。 这与二分是相反的。

ST表

基于倍增思想实现的区间最值查询优化方法。

预处理O(nlogn)，查询O(1)。

这里以查询最大值为例。

先开一个二维的数组 st[n][n]，st[i][j] 代表从第 i 位开始，len=2^j 的区间的最大值。

第 0 列用来记录这个数组。（其实也可以用来表示len=2^0=1的区间的最值，即本身）

后续记录最值都是查询上一列的目标区间段的最值，需要用到dp。

st[i][j]表示从第 i 位开始，len=2^j 的区间的最大值，不难发现st[i][j]只能为len=2^(j-1)的相邻两个区间的最大值，即：

dp[i][j] = max(dp[i][j-1], dp[i+1<<(j-1)][j-1])

以此构建ST表

vector<vector<ll>> st(N, vector<ll>(N));

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>st[i][0];
    for(int j=1;j<=log2(n);j++)
    {
        for(int i=1;i<=n-(1<<j);i++)
        {
            st[i][j]=max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
        }
    }
    return 0;
}

查询便是dp，[l, r]的最小值位覆盖住[l, r]的两个小区间的最小值。

这里用log2(l-r+1)，一是两个log2(len)可以覆盖住区间，二是由于倍增的缘故，log2(len)套用ST表可以很快得出对应的最值，复杂度为O(1)。

int query(int l, int r)
{
    int j=log2(r-l+1);
    return max(st[l][j], st[r-(1<<j)+1][j]);
}

查询最小值只用将max换为min即可