st 表的学习总结
_Cheems
·
·
个人记录
基础概念
需以 O(nlogn) 的时间复杂度构造 st 表。
可以用 O(1) 的时间复杂度，查询区间最大、最小值。但广义地说，满足结合律即可，如 gcd、异或等。
但 st 表是静态的，难以再修改。
st 表 vs 线段树
线段树的优势是：可以动态修改。
### 实现
首先，$st$ 表是用动态规划实现的，用到了倍增的思想。
定义 $st[i][j]$ 表示：一段以 $i$ 为起点，长度为 $2^j$ 的区间的最值。
容易推出转移方程：$st[i][j]=max(st[i][j-1],st[i+2^{j-1}][j-1])$ 。
怎么查询？不妨设 $len=log2(r-l+1)$，向下取整，用两段长为 $len$ 区间覆盖即可：$max(st[l][len],st[r-2^{len}+1][len])$。
### 代码
[模板题](https://www.luogu.com.cn/problem/P3865)
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],d[100005],l,r,len,f[100005][30];
void st()
{
for(int j=0; j<=25;j++)
for(int i=1; i+(1<<j)-1<=n;i++)
{
if(j==0) f[i][j]=a[i];
else f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
int main(){
cin>>n>>m;
for(int i=1; i<=n;i++)
{
scanf("%d",&a[i]);
if(i>=2) d[i]=d[i>>1]+1;
}
st();
for(int i=1; i<=m;i++)
{
scanf("%d%d",&l,&r);
len=d[r-l+1];
printf("%d\n",max(f[l][len],f[r-(1<<len)+1][len]));
}
return 0;
}
```
### 几道好题
#### P1198 [JSOI2008] 最大数
[链接](https://www.luogu.com.cn/problem/P1198)
一开始看到：这不是单调队列模板吗？
后来由空线段树的思想，联想到边读边建表，过了。
#### P7244 章节划分
[链接](https://www.luogu.com.cn/problem/P7244)
很好的一道题。
首先想到：答案一定是最大数的因子。
于是可以对最大数进行分解质因数，枚举每个因子：把它作为答案是否可行？就转化为了判定问题。
可求出在满足条件的情况下，区间最多被分为几段。因为，假如最多分为 $k$ 段，那么可以把其中两段合在一起，变为 $k-1$ 段，还是满足条件，以此类推。
下面给出一种巧妙的递归写法：
要求 $(l,r)$ 这段区间至多可被为多少段，不妨设 $ma$ 为区间最大值。
那么可分为两种情况：
1. $ma$ 整除答案，那为了使段数最多，不妨把 $ma$ 独立出来，则：$(l,r)=(l,ma-1)+(ma+1,r)+1$ 。
2. 不整除，考虑把 $ma$ 纳入它上面一级的区间，因为上一级一定满足条件。因此：若 $l>1$，不用考虑 $l$ 到 $ma$ 这段区间 （$l<1$ 的话没法覆盖住 $ma$）。若 $r<n$，同理。
#### P7009 [CERC2013] Magical GCD
[链接](https://www.luogu.com.cn/problem/P7009)
显而易见，$st$ 表可求出区间 $gcd$ 的值。
上手枚举下 $gcd$ 的值，可发现：一段区间，左端点固定，$gcd$ 的值随着右端点右移而单调不增。
由于题目时限为 $8s$，很容易想出一种暴枚的做法。
固定区间左端点，用二分求出 $gcd$ 值相等时，右端点最远在哪，然后统计最大值即可。
#### P2048 [NOI2010] 超级钢琴
[链接](https://www.luogu.com.cn/problem/P2048)
题目要求 $k$ 段序列最大值，贪心地想，就是求 $k$ 次最大值。
那不妨固定住区间左端点 $i$，对于每个 $1≤i≤n$，都能找到使该区间和最大的 $j$，把它们存入堆。我用的是优先队列 + 重载运算符的做法，因为相对简单。
然后要用到前缀和，每个区间可表示为 $s[j]-s[i]$ 的形式，既然要求最大且已知 $s[i]$ 的值，那么只需找到最大的 $s[j]$，可以用 $st$ 表预处理。
接着循环 $k$ 次，每次取最大的区间，把它拆分为次小区间（最多 $2$ 个），因为之后可能取到它们。
那么如何拆分？设 $l$、$r$ 分别最大区间左右端点，我们已知 $ma$ 的值，使得 $s[ma]-s[i]$ 的值最大，因此次大 $m_1$ 一定在 $l$ 到 $ma-1$ 之间；当然，前提是 $l<ma$。$m_2$ 同理。