OI Wiki 倍增法Binary Lifting全解析从二进制拆分的核心思想到 RMQ 与 LCA 实战【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki倍增法Binary Lifting是算法竞赛中一类极具普适性的优化范式当递推状态空间过大、线性递推无法满足时空限制时它通过只预处理 $k$ 的整数次幂位置上的代表值再利用「任意整数可拆成若干个 $k$ 的次幂项之和」这一性质拼出任意所需状态从而把海量递推压缩到对数级。本文以 OI Wiki 的倍增法文档 为骨架系统讲解其定义与成立前提完整展开 RMQST 表与树上倍增求 LCA 两大经典应用并以「环上多次跳跃求和」例题给出从递推式到完整可运行代码的实战推导读完后你将掌握倍增思想本身并能在涉及 $10^{18}$ 级步数的问题中独立设计出 $\Theta(n\log m)$ 预处理、$\Theta(\log m)$ 查询的解法。倍增法的定义成倍增长与次幂状态划分倍增法英语binary lifting顾名思义就是「成倍增长」。我们在进行递推时如果状态空间很大通常的线性递推无法满足时间与空间复杂度的要求那么可以通过成倍增长的方式只递推状态空间中在 $k$ 的整数次幂位置上的值作为代表。当需要其他位置上的值时我们通过「任意整数可以表示成若干个 $k$ 的次幂项的和」这一性质使用之前求出的代表值拼成所需的值。这里有两个关键前提需要吃透二进制k 进制拆分可行性任意整数 $m$ 都可以写成 $\sum 2^{i}$ 的形式且二进制表示中1的个数不超过 $\lceil\log_2(m1)\rceil$。因此一次「跳 $m$ 步」的操作可以等价替换为至多 $\lfloor\log_2 m\rfloor1$ 次「跳 $2^i$ 步」的子操作每次子操作的起点恰好是上一次子操作的终点「接力跳」。这是倍增算法能成立的根本数学事实。状态空间的可划分性使用倍增算法要求递推问题的状态空间关于 $k$ 的次幂具有可划分性——即「先跳 $2^{i-1}$ 步、再跳 $2^{i-1}$ 步」与「直接跳 $2^i$ 步」在结果上完全等价$2^{i-1}2^{i-1}2^i$。这也正是递推式能够成立的根基。通常情况下 $k$ 取 $2$这也是 binary lifting 名称的由来。原文档引用自李煜东《算法竞赛进阶指南》0x06「倍增」一节是竞赛界对倍增法的经典表述。这个方法在很多算法中均有应用其中最常用的是RMQ 问题和求LCA最近公共祖先下文将逐一展开。为什么「极少」砝码称重问题中的对数级直觉在进入正式应用之前先用一道经典思维题建立「倍增 对数级资源」的直觉。??? note 例题 如何用尽可能少的砝码称量出 $[0,31]$ 之间的所有重量只能在天平的一端放砝码??? note 解题思路 答案是使用1 2 4 8 16这五个砝码可以称量出 $[0,31]$ 之间的所有重量。同样如果要称量 $[0,127]$ 之间的所有重量可以使用1 2 4 8 16 32 64这七个砝码。每次我们都选择 2 的整次幂作砝码的重量就可以使用极少的砝码个数量出任意我们所需要的重量。为什么说是极少呢因为如果我们要量出 $[0,1023]$ 之间的所有重量只需要 10 个砝码需要量出 $[0,1048575]$ 之间的所有重量只需要 20 个。如果我们的目标重量翻倍砝码个数只需要增加 1。这叫「对数级」的增长速度因为砝码的所需个数与目标重量的范围的对数成正比。这正是倍增思想最朴素的模型用 $\log$ 个「代表值」次幂砝码就能组合出指数级范围里的任意目标。倍增算法中的所有复杂度收益都源于这个「个数与范围的对数成正比」的观察。倍增法的两大经典应用应用一RMQ 问题与 ST 表RMQ 是 Range Maximum/Minimum Query 的缩写表示区间最大最小值。使用倍增思想解决 RMQ 问题的方法是ST 表Sparse Table。OI Wiki 在 RMQ 专题 中详细比较了单调栈、ST 表、线段树、Four Russian 等多种解法ST 表的完整推导见 ST 表文档。ST 表基于倍增思想可以做到 $\Theta(n\log n)$ 预处理、$\Theta(1)$ 回答每个询问但不支持修改操作。其核心递推建立在「可重复贡献问题」之上对于满足 $x\operatorname{opt} xx$ 的运算如 $\max(x,x)x$、$\gcd(x,x)x$即便预处理区间相互重叠只要它们的并覆盖了询问区间答案依然正确。具体地令 $f(i,j)$ 表示区间 $[i,i2^j-1]$ 的最大值显然有初始状态 $f(i,0)a_i$第二维就相当于倍增时「跳了 $2^j-1$ 步」状态转移方程为$$ f(i,j)\max(f(i,j-1),f(i2^{j-1},j-1)) $$即「左半边」与「右半边」各用一次 $j-1$ 级的代表值拼接出 $j$ 级区间与 $2^{j-1}2^{j-1}2^j$ 的拆分区段一一对应。查询区间 $[l,r]$ 时取 $s\lfloor\log_2(r-l1)\rfloor$用 $[l,l2^s-1]$ 与 $[r-2^s1,r]$ 两个预处理区间覆盖询问区间即可 $O(1)$ 回答仓库中的参考实现见 sparse-table_1.cpp。应用二树上倍增求 LCA倍增算法是最经典的 LCA 求法是朴素算法的改进。朴素做法每次让深度较大的点向上跳一步直到相遇单次查询复杂度为 $\Theta(n)$倍增法则通过预处理 $\text{fa}_{x,i}$ 数组表示点 $x$ 的第 $2^i$ 个祖先让游标可以快速移动大幅减少跳转次数详见 最近公共祖先文档。倍增求 LCA 分为两个阶段调整深度计算 $u,v$ 的深度差 $y$对 $y$ 做二进制拆分把 $y$ 次单步跳转优化为「$y$ 的二进制表示所含1的个数」次跳转让较深的点跳到与另一个点相同的深度。共同上跳从最大的 $i$ 开始循环尝试到 $0$含 $0$如果 $\text{fa}{u,i}\ne\text{fa}{v,i}$则同时执行 $u\gets\text{fa}{u,i},v\gets\text{fa}{v,i}$结束时 LCA 即为 $\text{fa}_{u,0}$。倍增 LCA 的预处理时间复杂度为 $O(n\log n)$单次查询为 $O(\log n)$。实现上有一个重要优化通过交换fa数组的两维把较小的一维$\log n$放在前面可以减少 cache miss 次数、提高程序效率——这一条与 ST 表「一维大小 $\log n$ 的维度优先作为第一维」的建议完全一致。在 OI Wiki 仓库中lca_1.cpp 给出了带边权用于求树上两点距离的倍增 LCA 参考实现其 DFS 预处理部分与倍增递推式逐行对应// 初始化第 2^0 1 个祖先就是它的父亲节点dep 也比父亲节点多 1。 fa[root][0] fno; dep[root] dep[fa[root][0]] 1; // 初始化其他的祖先节点第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第 // 2^(i-1) 的祖先节点。 for (int i 1; i 31; i) { fa[root][i] fa[fa[root][i - 1]][i - 1]; cost[root][i] cost[fa[root][i - 1]][i - 1] cost[root][i - 1]; }可以看到fa[root][i] fa[fa[root][i-1]][i-1]正是「先跳 $2^{i-1}$ 步、再跳 $2^{i-1}$ 步」的接力式递推在树上的具体形态cost数组则把同样的倍增结构复用于路径权值求和这提示我们倍增不只适用于「位置」同样适用于随位置累积的「信息」如下一节的点权和。实战例题环上 $10^{18}$ 次跳跃的倍增解法以下例题完整展现了「预处理 $2^i$ 次幂信息 → 二进制拆分拼答案」的完整套路是 OI Wiki 原文档的核心实战内容。??? note 例题 给出一个长度为 $n$ 的环和一个常数 $k$每次会从第 $i$ 个点跳到第 $(ik)\bmod n1$ 个点总共跳了 $m$ 次。每个点都有一个权值记为 $a_i$求 $m$ 次跳跃的起点的权值之和对 $10^97$ 取模的结果。数据范围$1\leq n\leq 10^6$$1\leq m\leq 10^{18}$$1\leq k\leq n$$0\le a_i\le 10^9$。??? note 解题思路 这里显然不能暴力模拟跳 $m$ 次。因为 $m$ 最大可到 $10^{18}$ 级别如果暴力模拟的话时间承受不住。所以就需要进行一些预处理提前整合一些信息以便于在查询的时候更快得出结果。如果记录下来每一个可能的跳跃次数的结果的话不论是时间还是空间都难以承受。 那么应该如何预处理呢看看第一道例题。有思路了吗 回到本题。我们要预处理一些信息然后用预处理的信息尽量快的整合出答案。同时预处理的信息也不能太多。所以可以预处理出以 2 的整次幂为单位的信息这样的话在预处理的时候只需要处理少量信息在整合的时候也不需要大费周章。 在这题上就是我们预处理出从每个点开始跳 1、2、4、8 等等步之后的结果所处点和点权和然后如果要跳 13 步只需要跳 148 步就好了。也就是说先在起始点跳 1 步然后再在跳了之后的终点跳 4 步再接着跳 8 步同时统计一下预先处理好的点权和就可以知道跳 13 步的点权和了。 对于每一个点开始的 $2^i$ 步记录一个 go[i][x] 表示第 $x$ 个点跳 $2^i$ 步之后的终点而 sum[i][x] 表示第 $x$ 个点跳 $2^i$ 步之后能获得的点权和。预处理的时候开两重循环对于跳 $2^i$ 步的信息我们可以看作是先跳了 $2^{i-1}$ 步再跳 $2^{i-1}$ 步因为显然有 $2^{i-1}2^{i-1}2^i$。即我们有 sum[i][x] sum[i-1][x]sum[i-1][go[i-1][x]]且 go[i][x] go[i-1][go[i-1][x]]。 当然还有一些实现细节需要注意。为了保证统计的时候不重不漏我们一般预处理出「左闭右开」的点权和。亦即对于跳 1 步的情况我们只记录该点的点权和对于跳 2 步的情况我们只记录该点及其下一个点的点权和。相当于总是不将终点的点权和计入 sum。这样在预处理的时候只需要将两部分的点权和直接相加就可以了不需要担心第一段的终点和第二段的起点会被重复计算。 这题的 $m\leq 10^{18}$虽然看似恐怖但是实际上只需要预处理出 $65$ 以内的 $i$就可以轻松解决比起暴力枚举快了很多。用行话讲这个做法的 [时间复杂度](https://link.gitcode.com/i/885625ef6c2b27a1e8fbf75ed45b9b65) 是预处理 $\Theta(n\log m)$查询每次 $\Theta(\log m)$。参考代码与实现细节解读原文档给出的完整参考代码如下#include cstdio using namespace std; constexpr int mod 1000000007; int modadd(int a, int b) { if (a b mod) return a b - mod; // 减法代替取模加快运算 return a b; } int vi[1000005]; int go[75][1000005]; // 将数组稍微开大以避免越界小的一维尽量定义在前面 int sum[75][1000005]; int main() { int n, k; scanf(%d%d, n, k); for (int i 1; i n; i) { scanf(%d, vi i); } for (int i 1; i n; i) { go[0][i] (i k) % n 1; sum[0][i] vi[i]; } int logn 31 - __builtin_clz(n); // 一个快捷的取对数的方法 for (int i 1; i logn; i) { for (int j 1; j n; j) { go[i][j] go[i - 1][go[i - 1][j]]; sum[i][j] modadd(sum[i - 1][j], sum[i - 1][go[i - 1][j]]); } } long long m; scanf(%lld, m); int ans 0; int curx 1; for (int i 0; m; i) { if (m (1ll i)) { // 参见位运算的相关内容意为 m 的第 i 位是否为 1 ans modadd(ans, sum[i][curx]); curx go[i][curx]; m ^ 1ll i; // 将第 i 位置零 } } printf(%d\n, ans); }逐段拆解这段代码可以提炼出倍增算法的四个通用步骤初始化 $2^0$ 层go[0][i] (i k) % n 1表示第 $i$ 个点跳 1 步到达的下一位置注意 $(ik)\bmod n1$ 的写法把环的「从 1 编号」与「取模」正确衔接sum[0][i] vi[i]对应「左闭右开」约定——跳 1 步只统计起点权值不统计终点权值这是后面不重不漏的关键。取对数确定层数int logn 31 - __builtin_clz(n)是 GCC 内建函数__builtin_clzcount leading zeros统计前导零个数的快捷取对数写法等价于 $\lfloor\log_2 n\rfloor$。这里的循环上界也可以直接写死为常数原文档提示「只需预处理出 $65$ 以内的 $i$」即可覆盖 $m\le 10^{18}2^{60}$ 的全部情况若对 $n$ 取对数则保证 $2^{\log n}\ge n$环上最长的「去重后的跳跃状态」也不会越界。倍增递推go[i][j] go[i-1][go[i-1][j]]与sum[i][j] modadd(sum[i-1][j], sum[i-1][go[i-1][j]])正是「先跳 $2^{i-1}$ 步、再跳 $2^{i-1}$ 步」的接力递推。第一段的终点go[i-1][j]恰好是第二段的起点两段点权和直接相加由于 sum 是左闭右开第一段不含其终点、第二段含其起点相加时不会重复也不会遗漏。二进制拆分查询从低位到高位扫描 $m$ 的二进制位若第 $i$ 位为 1m (1ll i)就执行一次「跳 $2^i$ 步」累加sum[i][curx]并把游标推进到go[i][curx]同时用m ^ 1ll i把该位置零以推进循环。整个过程至多执行 $\lfloor\log_2 m\rfloor1$ 次跳转对应查询复杂度 $\Theta(\log m)$。两点工程细节值得注意模加优化由于 $ab2\bmod$ 恒成立两项都是取模后的余数modadd用一次比较与减法代替%运算符是竞赛代码中常见的常数优化数组维度顺序注释明确写到「小的一维尽量定义在前面」——把 $\log$ 级的一维放在第一维与 ST 表文档「注意点」一节、以及 LCA 文档 中交换fa两维的建议一脉相承都是为了提升 cache 局部性。倍增思想的通用化还能用于哪些场景从上面的推导可以看出倍增法是一种「框架级」的优化范式其通用套路可以抽象为三步把待求解的「大操作」拆解为幂次级「子操作」的接力要求状态空间关于 $2^i$ 可划分预处理每个状态在 $2^i$ 级子操作下的「去向」与「累计信息」本例题中的go与sumLCA 中的fa与costST 表中的f查询时对步数或深度差做二进制拆分用至多 $\log$ 次跳跃拼出完整答案。在 OI Wiki 仓库内这一框架被反复复用RMQ / ST 表f(i,j)\max(f(i,j-1),f(i2^{j-1},j-1))见 sparse-table.md树上倍增 LCAfa[root][i] fa[fa[root][i-1]][i-1]见 lca.md 与参考实现 lca_1.cpp跳跃类问题本例题go[i][x]go[i-1][go[i-1][x]]、sum[i][x]sum[i-1][x]sum[i-1][go[i-1][x]]。只要一个递推满足「结果可沿次幂步长拼接、拼接点信息不重不漏」就可以尝试用倍增把线性复杂度压到对数级——这也是「binary lifting」被广泛应用于树上第 $k$ 级祖先、函数图functional graph跳转、区间最值等问题的根本原因。小结倍增法的本质是用 $\Theta(\log)$ 个「$2^i$ 级代表值」换取对任意状态的对数级拼装能力预处理阶段用 $2^{i-1}2^{i-1}2^i$ 的接力递推以 $\Theta(n\log m)$ 的代价生成全部代表值查询阶段利用二进制拆分以 $\Theta(\log m)$ 的代价回答任意询问。本文从「砝码称重」的直觉模型出发完整覆盖了 OI Wiki 倍增法文档 中的定义、RMQ 与 LCA 两大应用以及环上跳跃例题的完整推导与代码并补充了仓库内 ST 表、LCA、复杂度记号 及 lca_1.cpp 的源码级佐证。掌握倍增思想后遇到「步数巨大、状态可拼接」类问题时不妨先问自己一句能不能只预处理 $2^i$ 次幂的代表值【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考