$$ \mathcal{ST}$$

像某个 $Cbh$ 一样 $st$ 表都不会写还是不好的。所以写一篇 $st$ 表。

$ST$ 表支持维护区间问题，并且要求静态。可以达到预处理 $O(n\log n)$，而单词查询 $O(1)$ 的恐怖效率。空间复杂度 $O(n\log n)$ ，想比于线段树其应用范围稍显狭窄。

$\mathcal{But...}$ $\mathcal{ST}$ 的单词查询是 $O(1)$ 的。

下面主要以 $\min$ 操作为例介绍

$\mathcal{ST}$ 的思想主要基于倍增。

先要 $Init(log2)$ 当然如果你不嫌弃 $C++$ 的大常数 $\log_2$ 的话也不是不行。

只需要 $Init([1-n])$ 的 $\log_2$ 就好了。这一步主要是为了应付后面倍增要求。显然，$\log_2(x)=log_2(\left[\frac{x}{2}\right])+1$ 理由不想多说。按照这个步骤初始化即可。

$$\mathcal{STEP . 1}$$

然后就是预处理。可以得到一个 $\min$ 特有的关系式，大概就是这个相貌：

$$\min_{i=l} ^r a[i] = \min\{\min _{i=l} ^{k\leq r} a[i],\min_{k\geq l} ^r a[i]\}$$

等式右边的两项可以通过刚刚的方法求得。

这样就可以开始推导推导了：设 $dp[i][j]$ 表示 $\min _{k=l} ^{l+2^j} a[k]$，这里就可以出来一个转移方程：

$$dp[i][j]=\min\{dp[i][j-1],dp[i+2^{j-1}][j-1]\}$$

理由如上。

$$\mathcal{STEP.2}$$

查询操作。

$$\min_{i=l} ^r a[i] = \min\{dp[l][k],dp[r-2^k][k]\}$$

其中 $k=\log_2(r-l+1)$

理由还是如上。

$$\mathcal{STEP.3}$$

吸取了某个叫 $\mathcal{CBH}$ 同学的教训，我们可以知道 $k$ 就是 $k$ ，不要 $k-1.$

上代码。

// here is Init
void init(){
    lg[0]=-1;
    FOR(i,1,n) lg[i]=lg[i>>1]+1;
    FOR(i,1,n) dp[i][0]=a[i];
    int lim=lg[n];
    FOR(k,1,lim)
        FOR(s,1,n+1-(1<<k))
            dp[s][k]=max(dp[s][k-1],dp[s+(1<<(k-1))][k-1]);
}
// here is Query
l=read();r=read();
int k=lg[r-l+1];
cout<<max(dp[l][k],dp[r-(1<<k)+1][k])<<'\n';

那么除了 $\min$ 之外 $\mathcal{ST}$ 还可以维护 $\mathcal{GCD,MAX,OR,LCM}$ 之类的东西。

$$\mathcal{O(n\log n)+O(n \log n)+O(1)}$$