ST 表学习笔记
linxuanrui
·
·
算法·理论
目录
-
概述
-
原理
-
实现
3.1. 预处理
3.2. 查询
-
拓展
4.1 处理不可重复贡献问题
4.2 末尾添加元素
-
参考文献
1.概述
ST 表，是一种能以 \mathcal{O}(n\log n) 预处理，\mathcal{O}(1) 查询的数据结构。
ST 表用于处理可重复贡献的问题{}^{[1]}。
## 2.原理
下面的部分都以 $\max$ 举例。
ST 表的实现是基于倍增和 dp。
设 $f_{i,j}$ 为 $[i,i + 2^j-1]$ 区间的 $\max$ 值。
换一种说法，$f_{i,j}$ 就是以 $a_i$ 开始，长度为 $2^j$ 的区间 $\max$ 值。
显然，$f_{i,0}=a_i$。
接下来，考虑状态转移方程。
从上图可以看出，$f_{i,j}=\max(f_{i,j-1},f_{i+2^{j-1},j-1})$。
这个状态转移方程的意思，就是在上图中的红色左半部分和右半部分的最大值。
接下来就是查询了。
我们可以把区间拆分成左边的红色区间和右边的蓝色区间，长度显然就是 $\log_{2}\text{区间长度}$。
因为 $\max$ 是可重复的问题，所以重复并不会对答案产生影响。
设区间左端点是 $l$，右端点是 $r$，$k=\lfloor\log_{2}(r-l+1)\rfloor$。
那么 $\max(a_l,a_{l+1},a_{l+2}\cdots a_r)=\max(f_{l,k},f_{r-2^k+1,k})$。
因为 $2^k\times2=2^{k+1}>n$，所以肯定能覆盖所有区间。
就这样，我们实现了 $\mathcal{O}(n\log n)$ 预处理，$\mathcal{O}(1)$ 询问的算法——ST 表。
## 3.实现
### 3.1.预处理
```cpp
for(int i = 1;i <= n;i++)f[i][0] = a[i];//边界条件
for(int j = 1;j <= log2(n);j++){
for(int i = 1;i + (1 << j) - 1 <= n;i++){
f[i][j] = max(f[i][j - 1],f[i + (1 << j - 1)][j - 1]);//状态转移方程
}
}
```
但实际上，由于待会要用到很多次 `log`，可以用 $\log(i)=\log(\lfloor i\div2\rfloor)+1$ 的公式来预处理。
优化过后的代码：
```cpp
for(int i = 1;i <= n;i++)f[i][0] = a[i],LOG[i] = LOG[i >> 1] + 1;//多了 log 的预处理
for(int j = 1;j <= LOG[n];j++){//这里也要改
for(int i = 1;i + (1 << j) - 1 <= n;i++){
f[i][j] = max(f[i][j - 1],f[i + (1 << j - 1)][j - 1]);
}
}
```
### 3.2.查询
这里只给出优化过后的代码。
```cpp
int ask(int l,int r){
int k = LOG[r - l + 1];
return max(st[l][k],st[r - (1 << k) + 1][k]);
}
```
## 4.拓展
这两条都是 @[rainygame](/user/804607) 教我的，快去膜拜 ta。
### 4.1.处理不可重复贡献问题
如果你还不知道什么是“可重复贡献问题”，可以看一下前面的[概述](https://www.luogu.com.cn/blog/linxuanrui/st-biao-xue-xi-bi-ji#:~:text=1.概述)，里面有提一嘴。
如果你有仔细看这篇博客的话，你可能会有疑问：你不是说过 ST 表只能处理可重复的贡献问题吗？为什么又可以处理不可重复贡献问题呢？
我们回忆一下 ST 表的原理。ST 表是基于倍增 + DP 实现的。
说到倍增，大家可以看一下 [OI-wiki 的介绍](https://oi-wiki.org/basic/binary-lifting)。
看完之后，我们很自然的可以想到：既然 ST 表已经处理出了长度是 $2^x$ 的区间运算，那么我们可以把询问的区间做二进制拆分。这样就可以做到 $\mathcal{O}(\log n)$ 询问了。
这里的代码用区间按位与来举例子。
```cpp
//q 次询问，求区间按位与。
#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
int n,q,l,r,a[N],st[N][31],LOG[N];
int ask(int l,int r){
int k = LOG[r - l + 1],now = l,ans = INT_MAX;
for(int i = k;i >= 0;i--){
if((1 << i) & (r - l + 1)){
if(ans == INT_MAX)ans = st[now][i];
else ans &= st[now][i];
now = now + (1 << i);
}
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i = 1;i <= n;i++)cin >> a[i],st[i][0] = a[i],LOG[i] = LOG[i >> 1] + 1;
for(int j = 1;j <= LOG[n];j++){
for(int i = 1;i + (1 << j) - 1 <= n;i++){
st[i][j] = (st[i][j - 1] & st[i + (1 << j - 1)][j - 1]);
}
}
while(q--)cin >> l >> r,cout << ask(l,r) << endl;
}
```
### 4.2.末尾添加元素
这个比 [4.1. 处理不可重复贡献问题](https://www.luogu.com.cn/blog/linxuanrui/st-biao-xue-xi-bi-ji#:~:text=4.1.处理不可重复贡献问题)要简单一点。
考虑向末尾添加时，`st` 数组的变化。
发现只有 $st_{n-2^j + 1,j}$（$0\le j\le \lfloor\log_{}n\rfloor$）会发生改变。一个一个更新即可。时间复杂度为 $\mathcal{O}(\lfloor\log_{}n\rfloor)
代码：
//q 次询问，每次询问格式如下：
//1 x 在数组后面添加一个数
//2 l r 输出 a_l ~ a_r 的最大值
#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
const int N = 2e5 + 5;
int n,q,opt,x,l,r,a[N],st[N][31],LOG[N];
int ask(int l,int r){
int k = LOG[r - l + 1];
return max(st[l][k],st[r - (1 << k) + 1][k]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i = 1;i <= n;i++)cin >> a[i],st[i][0] = a[i],LOG[i] = LOG[i >> 1] + 1;
for(int j = 1;j <= LOG[n];j++){
for(int i = 1;i + (1 << j) - 1 <= n;i++){
st[i][j] = max(st[i][j - 1],st[i + (1 << j - 1)][j - 1]);
}
}
while(q--){
cin >> opt;
if(opt == 1){
cin >> x;
a[++n] = x;
LOG[n] = LOG[n >> 1] + 1;
st[n][0] = x;
for(int i = 1;i <= LOG[n];i++)st[n - (1 << i) + 1][i] = max(st[n - (1 << i) + 1][i - 1],st[n - (1 << (i - 1)) + 1][i - 1]);
}else{
cin >> l >> r;
cout << ask(l,r) << endl;
}
}
}
5.参考文献
-
ST 表 - OI Wiki
-
liangbob 巨佬的博客