ST表 学习笔记
djwj233
2020-10-24 21:24:50
## ST表用来干什么
用来解决 `RMQ` 问题。
更一般地，一切 `可重复贡献` 的区间问题都可以用它 $\Theta(n\log n)- \Theta(1)$ 地 **在线** 解决。
~~大概只是个 PJ 知识点，拓展不到哪里去...~~
## ST表主过程
类似于 `DP` 的思想，有倍增的优化。
以下以区间最小值为例题。
- 设有数列 $A$，下标定义为 $1\cdots n$。
定义：
$$f(i,j)=\min\limits_{j\le k\le j+2^i-1} A_k$$
- 预处理 $f(i,j)$。
- 每次询问 $\min\limits_{l\le k\le r} A_k$ 的值，就寻找两个 **可能有重但不漏** 的区间取二者中的最小值。
详细地说：
**1. 预处理：**（共 $\Theta(n\log n)$，小常数）
可以类似于 `DP` 进行转移。
- 边界 $f(0,x)=A_x$。
- 令 $t=\left\lceil \log_2 n \right\rceil$
- $\forall 1\le i\le t,\ f(i,j)=\min\left\{ f(i-1,j),f(i-1,j+2^{i-1})\right\}$
**2. 询问：**（单次 $\Theta(1)$ ）
- 找到一个 $k=\left\lfloor \log_2 r-l+1 \right\rfloor$，
- 则 $ans=\min\{f(k,l),f(k,r-2^k+1)\}$
常数、码量均远小于线段树。
**在线** 但 **不支持带修**，如果需要修改可以使用 [猫树](https://immortalco.blog.uoj.ac/blog/2102)。
~~待填坑...~~
## 模板
随便放一个算了QAQ
```cpp
int t,f[LN][N];
void prework()
{
t=log(n)/log(2)+1;
fo(j,1,n)f[0][j]=a[j];
fo(i,1,t)
fo(j,1,n-(1<<i)+1)
f[i][j]=max(f[i-1][j],f[i-1][j+(1<<(i-1))]);
}
int query(int l,int r)
{
int k=log(r-l+1)/log(2);
return max(f[k][l],f[k][r-(1<<k)+1]);
}
```
## 二维 ST 表
主要是想学这个才写了这篇。
思想也差不多，代码更长一点。
大概和 `线段树` 扩展到二维有的一拼。
- [P2716 和谐的雪花](https://www.luogu.com.cn/problem/P2716)
定义：
$$f(i,x,y)=\min\limits_{x\le a\le x+2^i-1,\ y\le b\le y+2^i-1} A_{a,b}$$
由于是正方形，所以只需开三维，记录 $f(i,x,y)$ 即可。
可以发现答案具有单调性，于是转为 二分答案+判定。
Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v=a;v<=b;v++)
#define fo2(v,a,b) for(v=a;v<=b;v++)
#define fr(v,a,b) for(int v=a;v>=b;v--)
#define rg register
#define il inline
const int N=510,LN=15;
int n,m,k,a[N][N];
int t,f1[LN][N][N],f2[LN][N][N];
void prework()
{
t=log(max(n,m))/log(2)+1;
fo(x,1,n)
fo(y,1,m)
f1[0][x][y]=f2[0][x][y]=a[x][y];
fo(i,1,t)
fo(x,1,n-(1<<i)+1)
fo(y,1,m-(1<<i)+1)
{
f1[i][x][y]=max(
max(f1[i-1][x+(1<<(i-1))][y],f1[i-1][x][y+(1<<(i-1))]),
max(f1[i-1][x][y],f1[i-1][x+(1<<(i-1))][y+(1<<(i-1))])
);
f2[i][x][y]=min(
min(f2[i-1][x+(1<<(i-1))][y],f2[i-1][x][y+(1<<(i-1))]),
min(f2[i-1][x][y],f2[i-1][x+(1<<(i-1))][y+(1<<(i-1))])
);
}
}
int query_max(int lx,int ly,int len)
{
int k=log(len);
int rx=lx+len-1,ry=ly+len-1;
return max(
max(f1[k][lx][ry-(1<<k)+1],f1[k][rx-(1<<k)+1][ly]),
max(f1[k][lx][ly],f1[k][rx-(1<<k)+1][ry-(1<<k)+1])
);
}
int query_min(int lx,int ly,int len)
{
int k=log(len);
int rx=lx+len-1,ry=ly+len-1;
return min(
min(f2[k][lx][ry-(1<<k)+1],f2[k][rx-(1<<k)+1][ly]),
min(f2[k][lx][ly],f2[k][rx-(1<<k)+1][ry-(1<<k)+1])
);
}
bool check(int now)
{
int ans=0xcfcfcfcf;
fo(i,1,n-now+1)
fo(j,1,m-now+1)
ans=max(ans,
query_max(i,j,now)-query_min(i,j,now)
);
return ans>=k;
}
int main()
{
cin>>n>>m>>k;
fo(i,1,n)
fo(j,1,m)
scanf("%d",&a[i][j]);
prework();
int l=1,r=min(n,m),mid;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%d\n",check(l)?l:-1);
return 0;
}
```
对于任意长宽的 `ST` 表，也可以记录四维的 $f(i,j,x,y)$。
不过空间巨大，（时间允许的话）可以考虑用二维线段树代替。