当前位置：首页 > news >正文

倍增算法与应用（倍增优化之ST表、LCA、功能图、树上差分、贪心、二分）

news 2025/7/23 5:11:43

1. 倍增的思想

1.1 什么是倍增

1.2 倍增的常用实现过程

2. 倍增作为解决问题的主体的应用

2.1 ST表解决RMQ问题

2.1.1 什么是RMQ

2.1.2 暴力求解RMQ问题

2.1.3 ST表求解RMQ问题

2.1.4 ST表求解RMQ问题的算法复杂度及ST表的特性

2.1.5 例题及标准实现

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

2.2 倍增优化LCA

2.2.1 什么是LCA

2.2.1 求LCA的过程

2.2.2 倍增优化求LCA的过程

2.2.3 倍增优化的算法复杂度

2.2.4 倍增优化求LCA的代码

2.3 倍增优化之树上问题扩展

2.3.1 求树上节点 u 和节点 v 间的距离

2.3.2 求树上节点 u 和节点 v 间的路径上的最大或最小边权

2.3.3 例题

2.4 功能图求 k 步后继

2.4.1 功能图的定义

2.4.2 倍增优化功能图的 k 步后继问题

3. 倍增作为优化工具的应用

4. 题目

1. 倍增的思想

1.1 什么是倍增

倍增是一种算法思想，为了优化时间复杂度。本质是利用指数爆炸，将原问题抽象出来的非负整数分解为2的幂次的和，每个2的幂次长度的是一个子问题，最后合并子问题得到原问题的解，还是划分子问题。

使时间复杂度从 O(n) 降成 O(log n)。

倍增算法基于定理“任何整数都可唯一分解成k的幂次和”，即

（n, m, a $\in$ $\mathbb{Z}$ ，k $\in \mathbb{N}$ ，m ≥ 0，0 ≤ ai < k，k > 1）

该定理是倍增算法能够正确应用的依据，也是k进制计数的基础。

1.2 倍增的常用实现过程

倍增是首先划分子问题，再求各个子问题的解，最后合并原问题的过程。

实现步骤：

判断原问题抽象出来的长度之类的是否是非负整数，是非负整数且操作符合结合律才能用倍增。
预处理原问题划分成的子问题（每个子问题的长度是2 ^ i（i ≥ 0））的解，子问题可用动态规划求解。
合并子问题的解得到原问题的解，如果操作不可重复贡献，就按原问题的2的幂次和进行合并，如果操作可重复贡献，只要保证子问题覆盖了原问题且没有超出原问题的解即可。

操作可重复贡献是指：

如最小值操作，min(a1, a2, ……, an) = min(a1, a1, a2, ……, an)，ai可出现多次，出现多次结果相同，这是可重复贡献。

操作不可重复贡献是指：

如加法操作，a1 + a2 + …… + an ≠ a1 + a1 + a2 + …… + an，ai只能出现一次，出现多次结果不同，这是不可重复贡献

2. 倍增作为解决问题的主体的应用

倍增经常作为优化时间复杂度的工具使用，所以先考虑暴力解法，再看暴力解的某个部分可否用倍增优化。

2.1 ST表解决RMQ问题

2.1.1 什么是RMQ

给定一段区间a，查询区间a的子区间[L, R]的最大值或最小值，就是RMQ问题。

2.1.2 暴力求解RMQ问题

每次查询，暴力枚举求子区间[L, R]的最大或最小值，单次查询时间复杂度O(n)。

2.1.3 ST表求解RMQ问题

子区间[L, R]的长度 len 是非负整数，且求的是最大或最小值，符合结合律，可用倍增优化。

先将子区间的长度 len 分解为2的幂次和，每个2的幂次为一个子问题（子问题即子区间的子区间）的区间长度。

因为最大或最小值可重复贡献，直接合并[L, L + 2^log(len) - 1]和[R - 2^log(len) + 1, R]这两个子问题，有重叠不影响结果。2^log(len) ≤ len，所以要合并两端的子问题，直接求[L, L + 2 ^ log(len) - 1]可能遗漏元素。

求解：

1. 预处理用动态规划求每个子问题的解

状态：st[i][j] = 区间起点为i，整个区间长度为 2^j 的最大或最小值。
状态转移方程：st[i][j] = op(st[i][j - 1], st[i + (1 << j)][j - 1])
边界：st[i][0] = a[i]，st[i][j] 由 st[x][j - 1] 求出，外层循环为j。

2. 每次查询，合并子问题，得出原问题的解

res = min(st[L][log(len)], st[R - 2^log(len) + 1][log(len)])

st数组就是ST表。

2.1.4 ST表求解RMQ问题的算法复杂度及ST表的特性

时间复杂度：

预处理O(n log n)
查询O(1)
总时间复杂度O(n log n)

空间复杂度：

st数组占O(n log n)的空间
空间复杂度只记算法实现需要的空间，其余例如保存输入的a数组不计入在内、

st表的特性：

适合可重复贡献的场景，不可重复贡献需利用2的幂次和拼凑原问题的解，时间复杂度O(log n)，这时适合用线段树、树状数组优化。
尽量不修改a数组，每次修改a数组都要再预处理一遍ST表，这时适合用线段树、树状数组等修改方便不占用时间的来优化。

2.1.5 例题及标准实现

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

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

C++ 的 log2 函数比较费时间，所以定义Lg[i] = log(i)，递推预处理Lg即可。

#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 1e5 + 5;
const LL Maxk = 20;LL st[Maxn][Maxk], Lg[Maxn];void init_Lg(LL n) {Lg[1] = 0;for (LL i = 2; i <= n; ++i)  Lg[i] = Lg[i / 2] + 1;return;
}void init_st(LL n) {for (LL j = 1; j < Maxk; ++j) {for (LL i = 1; i + (1 << j) - 1 <= n; ++i)st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);}return;
}LL getRes(LL L, LL R) {LL len = Lg[R - L + 1];return max(st[L][len], st[R - (1 << len) + 1][len]);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m, L, R;cin >> n >> m;for (LL i = 1; i <= n; ++i)  cin >> st[i][0];init_Lg(n);init_st(n);while (m--) {cin >> L >> R;cout << getRes(L, R) << '\n';}return 0;
}

2.2 倍增优化LCA

2.2.1 什么是LCA

LCA即在有根树上求节点u和v的最近公共祖先。

最近公共祖先：节点u和v的深度最大的祖先节点。

2.2.1 求LCA的过程

深度大的上跳，使u和v在同一深度，如果u是v的祖先或v是u的祖先，此时u == v，已找到LCA(u, v)。
u和v同步上跳，直到u和v重叠，即找到LCA(u, v)。

2.2.2 倍增优化求LCA的过程

路径可看做一段区间，上跳 len 步，len为非负整数，上跳的过程相当于每次节点深度+1，加法符合结合律，可用倍增优化。

将上跳的路径划分子问题，每个子问题是一段子路径，长度为2^i，上跳不可重复贡献，必须按照len的2的幂次和合并子问题。

求解：

1. 动态规划预处理子问题的解

状态：关键是求从当前节点 x 跳了 2^i 次后跳到哪个节点，所以 father[x][i] = 节点 x 上跳 2^i 步后到达的节点编号
状态转移方程：father[x][i] = father[father[x][i - 1]][i - 1]，即从 x 上跳 2^(i - 1) 步到达 father[x][i - 1]，再从 father[x][i - 1] 上跳 2^(i - 1) 步到达 father[x][i]，基本原理：2^i = 2^(i - 1) + 2^(i - 1)。
边界：father[x][0] = x的父节点编号。
遍历顺序：father[x][i] 由 x 的祖先节点的信息求出，dfs遍历本身符合这样的递推关系，无后效性。

2. 求 LCA(u, v)

① 需要明确对整数 n 进行 k 的幂次和的分解过程，这样才明白如何合并子问题，如下。

要分解成，其中 a_m > 0。

设 ni （1 ≤ i ≤ m）为整数。

n0 = n，n0 = k × q0 + r0（0 ≤ ri < k，ri, qi $\in \mathbb{Z}$ ），a0 = r0。

n1 = q0，n1 = k × q1 + r1，a1 = r1。

……

n_m = q_{m - 1}，n_m = k × q_m + r_m，a_m = r_m，此时 q_m == 0。

n_{m + 1} = q_m = 0，停止分解。

将 ni 替换为 k × n_{i + 1} + ri，替换完毕，化简即为。

证明：

因为ni = k × qi + ri，而且根据分解的结束条件有 ri > 0 || qi > 0 绝对成立，n_{i + 1} = q_i，那么有|ni| > |n_{i + 1}|，即|n0| > |n1| > …… > |n_m| > |n_{m + 1}|，严格递增，所以 n_{m + 1} 一定为0，一定会结束分解。

|x| = x 的绝对值，|| 表示逻辑或，&& 表示逻辑与，n_{t} 表示 n 的下角标为 t 的量。

这个分解过程非常重要，是短除法的基础也是k进制数能够成立的基础，k进制数本质是对整数n进行k的幂次和的分解，再把 ai 按 i 从大到小写再一起。

根据分解过程，假设k = 2，那么要先分解大的2^i，即 i 从大到小分解。

② 求 LCA(u, v) 的过程

设depth[x] = 节点x的深度。

设 depth[u] ≥ depth[v]，要使depth[u] == depth[v]，u 需上跳k = depth[u] - depth[v] 步。上跳 k 步用倍增优化，根据 father 数组上跳，每次上跳 2^i（k的二进制第 i 位为1）步。如此相当于对 k 进行2的幂次和的分解，那么从大的 2^i 开始跳，直到 depth[u] == depth[v]。若u == v，直接返回u。
u 和 v 同步上跳 f 步，上跳 f 步用倍增优化，每次上跳 2^i（f的二进制第 i 位为1）步，相当于对 f 进行2的幂次和的分解，那么从大的 2^i 开始跳。只有 father[u][i] != father[v][i] 时才上跳，如此可保证u 和 v 同步上跳 i 步到的节点深度始终大于LCA，不超过LCA，那么出了循环 u ≠ v，所以要返回 u 和 v 的父节点，u 和 v 再上跳会在 u 和 v 的父节点重合。

2.2.3 倍增优化的算法复杂度

时间复杂度：

预处理 father 数组，时间复杂度 O(n log n)
求LCA时间复杂度 O(log n + log n)，相当于 O(log n)，时间复杂的估算忽略值小的项。
总的时间复杂度 O(n log n)

空间复杂度：

father 数组占 O(n log n) 的空间
depth 数组占 O(n) 的空间
总的空间复杂度 O(n log n)

2.2.4 倍增优化求LCA的代码

#include <iostream>
#include <vector>
using namespace std;typedef long long LL;const LL Maxn = 5 * 1e5 + 5;
const LL Maxk = 20;vector<LL> tree[Maxn];
LL father[Maxn][Maxk], depth[Maxn];void dfs(LL u, LL fa) {depth[u] = depth[fa] + 1;father[u][0] = fa;for (LL i = 1; depth[u] >= (1 << i) + 1; ++i) {father[u][i] = father[father[u][i - 1]][i - 1];}for (auto v : tree[u]) {if (v != fa)  dfs(v, u);}return;
}LL LCA(LL u, LL v) {if (depth[u] < depth[v])  swap(u, v);for (LL i = Maxk - 1; i >= 0; --i) {if (depth[father[u][i]] >= depth[v])  u = father[u][i];}if (u == v)  return u;for (LL i = Maxk - 1; i >= 0; --i) {if (father[u][i] != father[v][i]) {u = father[u][i];v = father[v][i];}}return father[u][0];
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m, s, x, y, a, b;cin >> n >> m >> s;for (LL i = 1; i < n; ++i) {cin >> x >> y;tree[x].emplace_back(y);tree[y].emplace_back(x);}dfs(s, 0);while (m--) {cin >> a >> b;cout << LCA(a, b) << '\n';}return 0;
}

题目：P3379 【模板】最近公共祖先（LCA） - 洛谷

2.3 倍增优化之树上问题扩展

路径的长度是非负整数，且一般的操作符合结合律，所以求路径的某个信息一般可用倍增优化。

2.3.1 求树上节点 u 和节点 v 间的距离

定义 dis(x, y) = 节点 x 和节点 y 之间的距离。

有两种求法：

1. 根据容斥原理求，较易理解

定义 dis[x] = 节点 x 到根节点 root 间的距离（无根树自己定义根节点）。

dis(u, v) = dis[u] + dis[v] - 2 × dis[LCA(u, v)]，倍增优化求LCA(u, v)。

2. 通过倍增优化直接求

dis(u, v) = u 到 LCA(u, v) 的距离 + v 到 LCA(u, v) 的距离，分步求。

① 动态规划预处理

状态：sum[x][i] = 节点 x 到节点 x 上跳 2^i 步的节点的距离
状态转移：sum[x][i] = sum[x][i - 1] + sum[father[x][i - 1]][i - 1]
边界：sum[x][0] = 节点 x 到节点 x 的父节点的边的长度
遍历顺序：在求LCA时顺便求

② 求dis(u, v)

节点 u（或v）类似LCA的做法上跳到 LCA(u, v)，上跳过程中res累加sum[u][i]
相加 u 和 v 的 res 得到dis(u, v)

2.3.2 求树上节点 u 和节点 v 间的路径上的最大或最小边权

有两种做法

用类似2.3.1的做法做
类似2.3.1的预处理，min或max可重复贡献，合并结果时用类似ST表的思想。

2.3.3 例题

给定一棵n个节点的树，求任意两个节点的路径里的最大边权。

类似2.3.1的做法如下：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 1e5 + 5;
const LL Maxk = 20;
const LL Inf = 1e18;struct node {LL to, val;
};
vector<node> tree[Maxn];LL father[Maxn][Maxk], maxDis[Maxn][Maxk], depth[Maxn];void dfs(LL u, LL fa, LL w) {depth[u] = depth[fa] + 1;father[u][0] = fa;maxDis[u][0] = w;for (LL i = 1; depth[u] >= (1 << i); ++i) {father[u][i] = father[father[u][i - 1]][i - 1];maxDis[u][i] = max(maxDis[u][i - 1], maxDis[father[u][i - 1]][i - 1]);}for (auto& v : tree[u]) {if (v.to != fa)  dfs(v.to, u, v.val);}return;
}LL LCA(LL u, LL v) {if (depth[u] < depth[v])  swap(u, v);for (LL i = Maxk - 1; i >= 0; --i) {if (depth[father[u][i]] >= depth[v])  u = father[u][i];}if (u == v)  return u;for (LL i = Maxk - 1; i >= 0; --i) {if (father[u][i] != father[v][i]) {u = father[u][i];v = father[v][i];}}return father[u][0];
}LL query_path(LL fa, LL u) {LL res = -Inf;for (LL i = Maxk - 1; i >= 0; --i) {if (depth[father[u][i]] >= depth[fa]) {res = max(res, maxDis[u][i]);u = father[u][i];}}return res;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m, x, y, w, LCAId = 0, res1 = 0, res2 = 0;cin >> n;for (LL i = 1; i < n; ++i) {cin >> x >> y >> w;tree[x].push_back({y, w});tree[y].push_back({x, w});}dfs(1, 0, 0);cin >> m;while (m--) {cin >> x >> y;LCAId = LCA(x, y);res1 = query_path(LCAId, x);res2 = query_path(LCAId, y);cout << max(res1, res2) << '\n';}return 0;
}

2.4 功能图求 k 步后继

2.4.1 功能图的定义

功能图是一个有向图，每个节点都只有一条出边。

因为每个节点都只有一条出边，所以任意两点间只有一条路径或没有路径。

2.4.2 倍增优化功能图的 k 步后继问题

k 步后继问题，即求 n 个节点的有向图，有向图的节点 u 向后 k 步后到达的节点。

k是非负整数，向后移动符合结合律，可用倍增优化。

代码：

#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 1e5 + 5;
const LL Maxk = 35;
const LL Inf = 1e18;LL father[Maxn][Maxk], v_sum[Maxn][Maxk], minDis[Maxn][Maxk];void init(LL n) {for (LL j = 1; j < Maxk; ++j) {for (LL i = 0; i < n; ++i) {father[i][j] = father[father[i][j - 1]][j - 1];v_sum[i][j] = v_sum[i][j - 1] + v_sum[father[i][j - 1]][j - 1];minDis[i][j] = min(minDis[i][j - 1], minDis[father[i][j - 1]][j - 1]);}}return;
}void output(LL u, LL m) {LL rsum = 0, rminVal = Inf;for (LL i = 0; i < Maxk; ++i) {if (((m >> i) & 1) != 0) {rsum += v_sum[u][i];rminVal = min(rminVal, minDis[u][i]);u = father[u][i];}}cout << rsum << ' ' << rminVal << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m;cin >> n >> m;for (LL i = 0; i < n; ++i)  cin >> father[i][0];for (LL i = 0; i < n; ++i) {cin >> v_sum[i][0];minDis[i][0] = v_sum[i][0];}init(n);for (LL i = 0; i < n; ++i) {output(i, m);}return 0;
}

题目：CF 702E