$$\mathcal{ST}$$

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

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

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

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

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

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

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

$$\mathcal{STEP}\mathcal{.}\mathcal{1}$$

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

$$\underset{i=l}{\overset{r}{min}}a[i]=min\{\underset{i=l}{\overset{k\le r}{min}}a[i],\underset{k\ge l}{\overset{r}{min}}a[i]\}$$

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

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

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

理由如上。

$$\mathcal{STEP}\mathcal{.2}$$

查询操作。

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

其中 $k={\log }_2(r-l+1)$

理由还是如上。

$$\mathcal{STEP}\mathcal{.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}\mathcal{,}\mathcal{MAX}\mathcal{,}\mathcal{OR}\mathcal{,}\mathcal{LCM}$ 之类的东西。

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