#创作计划# 倍增与ST表

AAA逃离森林湖的蔡锡龙批发

2026-05-23 16:16:05

发布于：广东

12阅读

0回复

0点赞

前言

噢我的天哪倍增正在摧毁我的脑细胞。
阅读前记住：在 C++ 中表示 $2^i$ 的方式为1<<i。

前置-倍增

倍增的基础思想

首先我们用惊人的注意力发现，任意一个整数都能表示成一堆 $2$ 的幂表示。
比如要表示 $(10100)_2 = (20)_{10}$ ，可以表示为 $2^2+2^4$ 。
显然对于一个数字，可以表示为以其二进制表示下为 $1$ 的位数 $-1$ 为指数的 $2$ 的幂的和。~~大概就这个意思，语言系统不好~~

如何操作倍增

ST表会给你讲解的。

正文-ST表篇

ST表的定义和作用

ST表是一种可以解决可重复贡献问题（如最大公约数，RMQ）的数据结构。

ST表的思想

现在有一个数组 $a$ ，要求区间 $[l,r]$ 的最大值，而且有很多区间，显然无法暴力。

建表

我们创建二维数组 $F$ ，令 $F_{i,j}$ 表示以 $i$ 为起点，长度为 $2_j$ 的区间的区间最大值。
显然这个区间就是 $[i,i+2^j-1]$ 。那么在实际操作的时候就要注意令 $i+2^j-1\leq n$ 。
考虑初始情况，当 $j=0$ 时这个区间只包含一个数就是 $a_i$ ，那么 $F_{i,0}=a_i$ 。
然后对于长度更长的区间，我们可以利用倍增思想把 $F_{i,j}$ 拆成两个长度折半的区间处理。
(图画的不好致歉)

显然， $F_{i,j}=max(F_{i,j-1},F_{i+2^{j-1},j-1})$ 。

这就是为啥ST表只能解决可重复贡献问题，详见 OI-Wiki。

这样先遍历 $j$ 再遍历 $i$ ，就可以建立ST表。

查询

假设我们要查询 $[l,r]$ 区间内的最大值。
首先我们求出区间长度 $len=r-l+1$ 。
然后，求出 $k=floor(log_2len)$ （下取整不会写）。
显然如果区间长度刚好是 $2$ 的幂，那么可以直接得到答案为 $F_{i,k}$ 。
但是不是呢？
这个过程我语言无法描述，看图吧。

两个区间的长度均为 $2^k$ 。
注意到对两个区间取 $max$ 的话，一定可以取到最大值。
发现对于黑色区间，其最大值为 $F_{l,k}$ ；
而对于蓝色区间，我们要先求出其左端点。由于蓝色区间的右端点为 $r$ ，长度为 $2^k$ ，那么蓝色区间的左端点就是 $r-2^k+1$ 。
那么蓝色区间最大值就是 $F_{r-2^k+1,k}$ 。
最终答案：

$max(F_{l,k},F_{r-2^k+1,k})$

实现ST表

例题：洛谷 P3865 【模板】ST 表 & RMQ 问题

$M=18$

首先是建表，按照上面的操作：

for(int i = 1;i <= n;i++){
    a[i]=read();                                     //read是题目给的快读
}
for(int i = 1;i <= n;i++){
    f[i][0]=a[i];                                    //初始化
}
for(int j = 1;j < M;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]); //按公式转移
    }
}

然后是操作：

while(m--){
    int l=read(),r=read();
    int len = r-l+1;
    int k = log(len)/log(2);                         //有一个log2()函数，也可以用这样的方法（对数换根）求。
    printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k]));    //公式
}

完整的代码：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int N=200010,M=18;
int a[N],f[N][M],n,m;
int main(){
    cin.tie(0);
    cout.tie(0);
    //ios::sync_with_stdio(0);
    n=read();m=read();
    for(int i = 1;i <= n;i++){
        a[i]=read();
    }
    for(int i = 1;i <= n;i++){
        f[i][0]=a[i];
    }
    for(int j = 1;j < M;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]);
        }
    }
    while(m--){
        int l=read(),r=read();
        int len = r-l+1;
        int k = log(len)/log(2);
        printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k]));;
    }
}

加练

板子

洛谷 P2251 质量检测
 洛谷-USACO P2880 [USACO07JAN] Balanced Lineup G
洛谷 P1816 忠诚

进阶

正在寻找……

引申-ST表求最近公共祖先（LCA）

洛谷 P3379 【模板】最近公共祖先（LCA） / ACGO A47208.最近公共祖先（LCA）
关于LCA的定义和性质请查看https://oi-wiki.org/graph/lca/。

前置知识-欧拉序

对于任意一棵树，对这棵树进行 DFS 遍历，每经过（注意，不是第一次经过）一个节点就把该节点加入到序列里，所得的序列就是欧拉序列。
对于欧拉序列，任一节点在序列中出现的次数为子树数量 $+1$ 。

ST表求解LCA的原理

考虑这样的一个树：

其欧拉序为1 2 3 2 4 2 1 5 6 5 1。
同时，我们处理一下这个序中出现的点的深度（根节点深度为1）：1 2 3 2 3 2 1 2 3 2 1。
还有每个节点在序列中第一次出现的位置：1 2 3 5 8 9。
然后我们瞪眼一下，可以瞪出来区间内最浅的点就是LCA，显然可以做区间最小值ST表解。
详见代码，代码不是我写的，是老师写的，注释不是老师写的，是我写的。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
//邻接表
vector<int> g[N];
//欧拉序列，深度，第一次出现，欧拉序列长度，st表
int eulra[2 * N], depth[2 * N], first[N], cnt = 0, st[2 * N][20];
//求欧拉序列，深度和第一次出现的位置
void dfs(int u, int fa, int dep) {
    //cnt同时用作计数和新的下标
    eulra[++cnt] = u, depth[cnt] = dep, first[u] = cnt;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(v == fa) continue;
        dfs(v, u, dep + 1);
        //走完以后回溯要再记录一次，也是和DFS序的不同之处。
        eulra[++cnt] = u, depth[cnt] = dep;
    }
}
//按照节点深度比较，x y 是下标，返回的是深度更浅的
int cmp(int x, int y) { return (depth[x] < depth[y] ? x : y); }
int query(int l, int r) {
    //保证左小右大
    if(l > r) swap(l, r);
    int k = log2(r - l + 1);
    return cmp(st[l][k], st[r - (1 << k) + 1][k]);
}
//解编号为u，v的节点的lca
int lca(int u, int v) {
    //把求解的节点转换为第一次出现的欧拉序列下标
    int l = first[u], r = first[v];
    //求解最近公共祖先在欧拉序列的出现下标，然后转回编号
    return eulra[query(l, r)];
}
int main() {
    //节点数，询问数，根编号
    int n, m, s;
    cin >> n >> m >> s;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        //不确定方向，建无向边
        g[u].push_back(v);
        g[v].push_back(u);
    }
    //处理三个序列的值
    dfs(s, 0, 1);
    //建st表
    for(int i = 1; i <= cnt; i++) st[i][0] = i;
    int k = log2(cnt);
    for(int j = 1; j <= k; j++)
        for(int i = 1; i + (1 << j) - 1 <= cnt; i++)
            //注意这里的比较是自定义比较
            st[i][j] = cmp(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    while(m--) {
        int u, v;
        cin >> u >> v;
        //lca函数求解lca
        cout << lca(u, v) << '\n';
    }
    return 0;
}

引用

所有内容来自老师的教程和 OI-Wiki。

有帮助，赞一个

去预览

0/2000

全部评论 3

AAA逃离森林湖的蔡锡龙批发
置顶
补充，first的唯一作用是帮助你找到求解区间。

昨天来自广东
0
- Eucatastrophe‌
  回复
  AAA逃离森林湖的蔡锡龙批发
  置顶
  
  昨天来自浙江
  0
Eucatastrophe‌
我 st 都没学好，只会打模板

昨天来自浙江
0
- Eucatastrophe‌
  回复
  Eucatastrophe‌
  都是用线段树水过的，我觉得线段树比 st 好理解
  
  昨天来自浙江
  0
- 🥥
  回复
  Eucatastrophe‌
  我觉得st表好理解得多
  
  14小时前来自上海
  0
AAA逃离森林湖的蔡锡龙批发
dinn.

昨天来自广东
0