CSP-S提高组里有一个让我又爱又恨的东西叫倍增算法。说爱是因为它几乎年年都出现在第二轮算法题里快速幂、ST表、LCA、第k级祖先全是它的地盘说恨是因为刚接触时死活想不通那个f[i][j]的状态数组到底在干嘛为什么跳完2的n次方步之后能那么快。这篇是系列的第4篇我想把它彻底讲透——倍增的底层思想、经典的三大应用、代码实现的坑以及考场上最容易被卡住的边界问题全部摊开揉碎了讲。不管你是刚学完基础语法、准备冲复赛的新手还是已经在刷真题、但遇到倍增题还是会卡壳的老选手这篇都值得花二十分钟细看。1. 倍增的底层逻辑二进制拆分思想是唯一核心1.1 从一次朴素查询说起理解倍增的动机先抛个最简单的场景有一个长度为n的序列每次询问“从第i个位置出发每次往后走a步走恰好k次之后到哪个位置”。如果n和k都是1e5级别朴素做法就是每一次查询都老老实实模拟走k次复杂度是O(nq)直接爆炸。倍增的做法很巧妙——它把“走k次”这个需求转换成“跳若干段2的幂次步数”的组合。比如k1313的二进制是1101也就是841那我只需要从起点先跳8步再跳4步再跳1步就完成了整个跳跃过程。关键点在于我可以预先算出“从任意位置出发跳2的0次方步、2的1次方步、2的2次方步……分别会到哪”这样每次查询最多只需要log2(k)次跳跃而且这个预处理是O(n log n)的一次搞定查询时每条询问就能做到O(log n)。这个思想本身就叫二进制拆分——任何一个正整数都能唯一表示成若干个2的幂的和这是最朴素却又最强大的数学基础。你不需要真的去“走”完所有步数而是把这个过程拆成几次大跳。用在考场上就是典型的“空间换时间”。1.2 状态转移方程f[i][j]到底在存什么倍增算法几乎都有一个核心状态定义f[i][j] 表示从位置i出发走2的j次方步到达的位置。预处理的时候最关键的就是状态转移公式f[i][j] f[ f[i][j-1] ][j-1]这句话的意思是想从i出发走2^j步可以先走2^(j-1)步到达某个中间位置再从那个位置继续走2^(j-1)步。因为2^(j-1) 2^(j-1) 2^j这是初中数学但正是这个拆分让整个算法成立。要注意顺序首先要初始化j0那一列也就是f[i][0]表示走1步能到的位置这通常是输入直接给的。然后从小到大枚举j每一层j依赖于上一层j-1的结果所以循环顺序必须是外层枚举j内层枚举i反过来就错了。我见过很多人在这一步把内外层写反结果预处理的f数组乱七八糟查出来全是错的还以为是数据结构的问题。这一层的复杂度是O(n log n)其中log的底是2。n1e5时大概1720层就够了所以这个预处理对时间的要求其实非常宽松真正的瓶颈往往是查询次数和你的常数。2. 三大经典应用快速幂、ST表、树上倍增家族2.1 快速幂你以为它和倍增无关其实同宗同源很多教程把快速幂单独讲但实际上快速幂就是倍增思想最纯粹的一种展现形式。求a的b次方模p朴素的循环乘b次b达到1e18时直接gg。快速幂的做法就是把b分解成二进制比如b13841那a^13 a^8 * a^4 * a^1。代码模板我直接贴出来long long quick_pow(long long a, long long b, long long p) { long long ans 1; while (b) { if (b 1) ans ans * a % p; a a * a % p; // a变成a^2相当于倍增加速 b 1; } return ans; }注意这里每次循环都会把a自身平方一次也就是从a^1到a^2再到a^4再到a^8每一步都是上一次的“翻倍”这正是倍增中“2倍2倍往上叠加”的核心动作。判断b的最低位是否为1来决定当前这个2的幂次项要不要乘进答案。考场上有一类题目会要求你用快速幂配合矩阵乘法做线性递推像斐波那契数列求第n项n到了1e18就只能走矩阵快速幂。那个套路和这个完全一样只是把普通整数的乘法换成了矩阵乘法。所以你把快速幂的板子滚熟等于同时掌握了矩阵快速幂的基础这是倍增组合技里性价比最高的一环。2.2 ST表区间最值查询的倍增玩法静态区间最值查询也就是RMQ问题用ST表是最经典的倍增应用。先看核心思路预处理一个st[i][j]数组表示从下标i开始、长度为2^j的区间内的最大值。预处理公式是st[i][j] max(st[i][j-1], st[i (1 (j-1))][j-1])意思是把长度为2^j的区间分成两段每段长度为2^(j-1)分别取最大值再合并。查询[L, R]的区间最大值时不需要把区间完整覆盖而是取两个可能重叠的2的幂次长度的区间来合并结果int query(int l, int r) { int k log2(r - l 1); // 用预处理的log表别直接调log2函数太慢 return max(st[l][k], st[r - (1 k) 1][k]); }这里有个很多人第一遍看不懂的地方为什么两个区间可以重叠因为最值运算有幂等性——同一个数被重复取两次不会影响结果。你取[l, l2^k-1]和[r-2^k1, r]两个区间它们可能交叠但并集覆盖了整个[l, r]范围而且每个元素至少出现在其中一个区间里所以取最大值后答案一定正确。如果换成求和这类运算重叠就会算重ST表就不适用了。ST表适合静态数据如果序列中的值会动态变化那就得改用线段树这一点是选手很容易踩的坑——考试时看到“区间查询单点更新”第一反应不应该是ST表而是线段树。2.3 LCA与第k级祖先树上倍增的高频考法树上求最近公共祖先LCA、求某个节点向上跳k步之后落在哪个节点是CSP-S真题里出镜率极高的考点。预处理up[u][i]表示从节点u向上走2^i步到达的祖先节点同样满足up[u][i] up[ up[u][i-1] ][i-1]跑一遍DFS或BFS先求出每个节点的深度同时把up[u][0]设为自己的父亲节点。然后预处理up表。查询LCA时先把两个节点深度对齐再让它们一起往上跳到LCA的正下方。写一个LCA的模板int lca(int u, int v) { if (depth[u] depth[v]) swap(u, v); int diff depth[u] - depth[v]; for (int i 0; i LOG; i) { if ((diff i) 1) { u up[u][i]; } } if (u v) return u; for (int i LOG; i 0; i--) { if (up[u][i] ! up[v][i]) { u up[u][i]; v up[v][i]; } } return up[u][0]; }第二段循环从大到小枚举i是很多新手最容易绕晕的地方。它的逻辑是我们从大步开始试如果能跳上去且两边跳到的祖先不同说明LCA还在上面就跳如果两边跳到的祖先相同说明可能已经跳过头或者刚好到了LCA就先不跳。这个策略保证最终u和v停留在LCA的两个不同子节点上最后只需返回up[u][0]即可。求第k级祖先就更直白了完全套二进制拆分的思路把k的每一位用循环判断能跳就跳。这套东西学好了树上的很多问题都能用比如树的重心、树上差分配合LCA算路径覆盖全是它的变体。3. 倍增优化DP专题把指数级的搜索变成log级3.1 跳楼梯问题的倍增版本有一个经典的DP问题是一条长度为n的路径每一步可以走的距离集合是S求从起点到终点最少要几步或者恰好走到终点的方法数。如果n很大、S又很复杂直接DP可能超时此时可以用倍增预处理跳2^i步后的位置状态把一次查询的复杂度压到O(log n)。这不是传统线性DP的思路而是RMQ式的“状态合并”思路。具体做法是把“跳一步”定义成一个变换预处理“跳2^i步”对应的变换结果。比如定义nxt[i][j]表示从位置j出发跳2^i步能到的最远位置转移形式仍然是nxt[i][j] nxt[i-1][ nxt[i-1][j] ]。然后查询时按照k的二进制位一路跳下去。我在实际做题中遇到这类题目最多的坑是不要把nxt[i][j]定义成“恰好跳2^i步”而应该定义成“不超过2^i步时能达到的最优状态”。因为很多题目里的最优策略是“尽量远跳”不超过反而更好写而且不改变复杂性。3.2 动态规划边界引用与溢出的经典误用写倍增DP时状态数组的下标经常涉及二维一旦n达到1e5、log层达到20数组大小就是2e6这还在内存接受范围内。但很多人习惯性地把数组定义为int st[100005][20]没问题。危险的是升级到三维或者开了vector套vector内存直接翻几倍可能MLE。另一个常见问题是1 j的溢出。如果j达到311 j已经超过int的范围必须用1LL j。很多人在LCA的深度差值计算中踩这个坑数据一大就WA得莫名其妙。我的建议是写一个常量LOG20或21因为2^201048576一般足够n2e5的题但如果是n1e5的树你要开到17层加一个冗余最稳妥是开20以上看数据范围灵活调整。还有就是下标从0开始还是从1开始。树上节点从1开始编号是竞赛惯例如果混着用预处理father数组时容易漏掉0号节点。我的偷懒办法是初始化up[0][i]0表示节点0的父节点是0这样就算跳出了树也不会越界而是跳到0号哨兵节点后续判断时只要排除0就行。4. 真题场景从“24年csp-s决斗”热词聊到倍增的实战扩展4.1 “决斗”这种游戏类题目的倍增化思考热词里频繁出现“csp-s决斗”很多人一脸懵其实就是那种带轮次模拟的对抗类题目。比如有n个人站成一圈每轮每个人和旁边的人决斗输的人退场赢的人继续问最后剩谁。这类题的朴素模拟复杂度是O(n^2)一旦n上了1e5就无解。但如果决斗规则是已知的、可预处理的就可以用倍增设计出“每2^i轮后谁会站着”的状态转移。每一轮根据相邻选手的胜负关系更新存活状态这本质上是一个可以复合的函数所以完全符合倍增的条件。这里的关键是决斗规则必须是“局部确定的”也就是当前轮次的胜负只取决于相邻两个人的能力值不会受全局状态影响。这个条件一旦满足就可以预处理出跳2^i轮后的情况查询和模拟就快得飞起。4.2 倍增与二分结合的套路倍增和二分经常是组合拳。有一种经典的题目类型是“求从某个点出发在满足条件的情况下最多能走多远”。暴力是从起点一步一步走二分是枚举终点然后判定倍增则可以直接尝试跳大步。比如我用倍增从大到小试跳如果能跳到某个位置且满足条件就跳过去直到再走一步就不满足条件为止最后停下来的位置就是最远合法位置。这种做法避开了二分的log常数在某些场景下甚至更自然。一个具体的应用场景是“在有序数组里找某个区间内最长的满足某种性质的子段”。倍增加一个check函数整体复杂度是O(n log n)思路清晰代码量还不大。我记得某年CSP-S的某道树上路径题就是先套了个倍增的最远跳跃预处理再配合一个双指针滑动区间把两条链的解法合到了一起。5. 倍增代码的工程化细节与调试经验5.1 外层循环顺序和数组大小的选择我把倍增代码的循环规则总结成一句话先枚举步数的指数层数再枚举位置。你永远不应该把位置放在外层、指数层放在内层否则f[i][j-1]的值还没算出来你就在用它推导f[i][j]了结果全是0。数组大小方面我习惯这样定义const int LOG 20; int f[100005][LOG 1];如果题目标明n最大是2e5那LOG取18就够用了2^18 262144但我一般会取20留出冗余。原因很简单比赛时不差这4层的内存但如果你LOG开小了diff的二进制位不够用查询时就会踩到下标越界这个bug非常隐蔽运行时不一定崩但答案肯定是错的。调试时有一个好用的技巧如果你怀疑自己的倍增预处理有问题先暴力验证小数据。随机生成n10以内的数据写一个朴素模拟对比你的倍增代码跑出来的结果逐条对拍。这个不过就是十分钟的事但能救回你一下午的瞎排查。5.2 位运算优先级与读入优化位运算的优先级比算术运算符低比比较运算符也低这是很多人踩过的坑。比如你写if (diff i 1)这个没问题因为比优先级高但如果你写if (diff (1 i))也别在这搞什么多余括号直接这样就行因为括号足够清楚了。如果你把条件写成if (diff 1 i)这里其实也能编译通过因为1 i先执行但我强烈不建议这样写——考试时越简单直观越好宁可多打一对括号也不要省这个功夫。读入优化强烈建议用快读。倍增类题目通常伴随大量查询每次都用cin读入1e5条询问时间直接翻倍。用scanf天然会快一点用我下面这个快读模板最稳inline int read() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; }在CSP-S这种时间卡得紧的考试里这个快读往往就是你能不能过最后一组的胜负手。5.3 常见问题速查表症状可能原因解决方向预处理后f数组全是0内外层循环顺序写反外层枚举j内层枚举i查询结果总是空跳一步位运算条件写错检查diff i 1是否正确出现莫名其妙的大数错误1 j溢出int改成1LL j或直接开long long递归爆栈DFS深度太深改用BFS预处理或开栈空间树上节点逃出树外up数组边界没处理定义哨兵节点0up[0][i]0LCA查询返回错误节点第二段从高到低循环写成了从低到高必须从LOG到0递减枚举这六个问题是我带学生和平时看群友求助时见到的高频错误你写之前先看完这张表能避开七成的低级失误。6. 考场上的倍增“三板斧”与我的个人习惯一年下来我刷了不少真题发现适用倍增的题不管表面上包装成什么样最终都会落到这三个框架之一快速幂式二进制拆分、RMQ跳表式合并、树上跳跃式祖先查询。拿到一道题先看数据范围如果n是1e5到2e5、查询次数也是1e5级别并且操作可以预处理、可以复合那倍增大概率是最优解之一。我的个人习惯是先写下状态定义用注释写在代码开头比如// f[i][j]: 从i出发走2^j步到达的位置然后把初始条件写在前面预处理循环写在后面查询函数单独写一个。这样代码结构很清晰查bug的时候也容易定位。还要提一下“C环境”这件事。有同学问VS Code怎么配置才能跑通这些代码其实信奥赛一般用的都是标准C环境编译选项常是g -O2 -stdc14。你不需要什么花哨的IDE一个顺手的环境加一个能单步调试的编译工具就够了。核心是你对模板代码的熟练度而不是工具的高级程度——当然这句话也只针对复习阶段的同学真到比赛用的都是考场统一系统平时练的就是手感和思路。7. 这套思想能继续扩展到的地方我一直觉得倍增之所以值得反复琢磨不只是因为高频考点而是它教会你一种“用空间换时间”的结构化思维。你会了倍增之后树链剖分里的跳链思路、并查集按秩合并的跳跃逻辑、字符串哈希的滚动思想都和倍增有千丝万缕的联系。如果你是在备战最近的CSP-S我建议你把快速幂、ST表、LCA这三个模板背到滚瓜烂熟然后去找历年真题里涉及树上路径、区间查询、跳跃模拟的题每道题先用暴力写一遍再用倍增优化写一遍对拍验证。这个过程非常痛苦但也是最有效的。记住考场上最怕的不是不会新算法而是拿着倍增模板却不知道什么时候用。多看题、多对拍、多总结这比背更多炫技的算法有用得多。 
长河君 · 2026/10/9 9:18:50 · 阅读 1.2k 倍增算法详解：从二进制拆分到快速幂、ST表与LCA实战
CSP-S提高组里有一个让我又爱又恨的东西叫倍增算法。说爱是因为它几乎年年都出现在第二轮算法题里快速幂、ST表、LCA、第k级祖先全是它的地盘说恨是因为刚接触时死活想不通那个f[i][j]的状态数组到底在干嘛为什么跳完2的n次方步之后能那么快。这篇是系列的第4篇我想把它彻底讲透——倍增的底层思想、经典的三大应用、代码实现的坑以及考场上最容易被卡住的边界问题全部摊开揉碎了讲。不管你是刚学完基础语法、准备冲复赛的新手还是已经在刷真题、但遇到倍增题还是会卡壳的老选手这篇都值得花二十分钟细看。1. 倍增的底层逻辑二进制拆分思想是唯一核心1.1 从一次朴素查询说起理解倍增的动机先抛个最简单的场景有一个长度为n的序列每次询问“从第i个位置出发每次往后走a步走恰好k次之后到哪个位置”。如果n和k都是1e5级别朴素做法就是每一次查询都老老实实模拟走k次复杂度是O(nq)直接爆炸。倍增的做法很巧妙——它把“走k次”这个需求转换成“跳若干段2的幂次步数”的组合。比如k1313的二进制是1101也就是841那我只需要从起点先跳8步再跳4步再跳1步就完成了整个跳跃过程。关键点在于我可以预先算出“从任意位置出发跳2的0次方步、2的1次方步、2的2次方步……分别会到哪”这样每次查询最多只需要log2(k)次跳跃而且这个预处理是O(n log n)的一次搞定查询时每条询问就能做到O(log n)。这个思想本身就叫二进制拆分——任何一个正整数都能唯一表示成若干个2的幂的和这是最朴素却又最强大的数学基础。你不需要真的去“走”完所有步数而是把这个过程拆成几次大跳。用在考场上就是典型的“空间换时间”。1.2 状态转移方程f[i][j]到底在存什么倍增算法几乎都有一个核心状态定义f[i][j] 表示从位置i出发走2的j次方步到达的位置。预处理的时候最关键的就是状态转移公式f[i][j] f[ f[i][j-1] ][j-1]这句话的意思是想从i出发走2^j步可以先走2^(j-1)步到达某个中间位置再从那个位置继续走2^(j-1)步。因为2^(j-1) 2^(j-1) 2^j这是初中数学但正是这个拆分让整个算法成立。要注意顺序首先要初始化j0那一列也就是f[i][0]表示走1步能到的位置这通常是输入直接给的。然后从小到大枚举j每一层j依赖于上一层j-1的结果所以循环顺序必须是外层枚举j内层枚举i反过来就错了。我见过很多人在这一步把内外层写反结果预处理的f数组乱七八糟查出来全是错的还以为是数据结构的问题。这一层的复杂度是O(n log n)其中log的底是2。n1e5时大概1720层就够了所以这个预处理对时间的要求其实非常宽松真正的瓶颈往往是查询次数和你的常数。2. 三大经典应用快速幂、ST表、树上倍增家族2.1 快速幂你以为它和倍增无关其实同宗同源很多教程把快速幂单独讲但实际上快速幂就是倍增思想最纯粹的一种展现形式。求a的b次方模p朴素的循环乘b次b达到1e18时直接gg。快速幂的做法就是把b分解成二进制比如b13841那a^13 a^8 * a^4 * a^1。代码模板我直接贴出来long long quick_pow(long long a, long long b, long long p) { long long ans 1; while (b) { if (b 1) ans ans * a % p; a a * a % p; // a变成a^2相当于倍增加速 b 1; } return ans; }注意这里每次循环都会把a自身平方一次也就是从a^1到a^2再到a^4再到a^8每一步都是上一次的“翻倍”这正是倍增中“2倍2倍往上叠加”的核心动作。判断b的最低位是否为1来决定当前这个2的幂次项要不要乘进答案。考场上有一类题目会要求你用快速幂配合矩阵乘法做线性递推像斐波那契数列求第n项n到了1e18就只能走矩阵快速幂。那个套路和这个完全一样只是把普通整数的乘法换成了矩阵乘法。所以你把快速幂的板子滚熟等于同时掌握了矩阵快速幂的基础这是倍增组合技里性价比最高的一环。2.2 ST表区间最值查询的倍增玩法静态区间最值查询也就是RMQ问题用ST表是最经典的倍增应用。先看核心思路预处理一个st[i][j]数组表示从下标i开始、长度为2^j的区间内的最大值。预处理公式是st[i][j] max(st[i][j-1], st[i (1 (j-1))][j-1])意思是把长度为2^j的区间分成两段每段长度为2^(j-1)分别取最大值再合并。查询[L, R]的区间最大值时不需要把区间完整覆盖而是取两个可能重叠的2的幂次长度的区间来合并结果int query(int l, int r) { int k log2(r - l 1); // 用预处理的log表别直接调log2函数太慢 return max(st[l][k], st[r - (1 k) 1][k]); }这里有个很多人第一遍看不懂的地方为什么两个区间可以重叠因为最值运算有幂等性——同一个数被重复取两次不会影响结果。你取[l, l2^k-1]和[r-2^k1, r]两个区间它们可能交叠但并集覆盖了整个[l, r]范围而且每个元素至少出现在其中一个区间里所以取最大值后答案一定正确。如果换成求和这类运算重叠就会算重ST表就不适用了。ST表适合静态数据如果序列中的值会动态变化那就得改用线段树这一点是选手很容易踩的坑——考试时看到“区间查询单点更新”第一反应不应该是ST表而是线段树。2.3 LCA与第k级祖先树上倍增的高频考法树上求最近公共祖先LCA、求某个节点向上跳k步之后落在哪个节点是CSP-S真题里出镜率极高的考点。预处理up[u][i]表示从节点u向上走2^i步到达的祖先节点同样满足up[u][i] up[ up[u][i-1] ][i-1]跑一遍DFS或BFS先求出每个节点的深度同时把up[u][0]设为自己的父亲节点。然后预处理up表。查询LCA时先把两个节点深度对齐再让它们一起往上跳到LCA的正下方。写一个LCA的模板int lca(int u, int v) { if (depth[u] depth[v]) swap(u, v); int diff depth[u] - depth[v]; for (int i 0; i LOG; i) { if ((diff i) 1) { u up[u][i]; } } if (u v) return u; for (int i LOG; i 0; i--) { if (up[u][i] ! up[v][i]) { u up[u][i]; v up[v][i]; } } return up[u][0]; }第二段循环从大到小枚举i是很多新手最容易绕晕的地方。它的逻辑是我们从大步开始试如果能跳上去且两边跳到的祖先不同说明LCA还在上面就跳如果两边跳到的祖先相同说明可能已经跳过头或者刚好到了LCA就先不跳。这个策略保证最终u和v停留在LCA的两个不同子节点上最后只需返回up[u][0]即可。求第k级祖先就更直白了完全套二进制拆分的思路把k的每一位用循环判断能跳就跳。这套东西学好了树上的很多问题都能用比如树的重心、树上差分配合LCA算路径覆盖全是它的变体。3. 倍增优化DP专题把指数级的搜索变成log级3.1 跳楼梯问题的倍增版本有一个经典的DP问题是一条长度为n的路径每一步可以走的距离集合是S求从起点到终点最少要几步或者恰好走到终点的方法数。如果n很大、S又很复杂直接DP可能超时此时可以用倍增预处理跳2^i步后的位置状态把一次查询的复杂度压到O(log n)。这不是传统线性DP的思路而是RMQ式的“状态合并”思路。具体做法是把“跳一步”定义成一个变换预处理“跳2^i步”对应的变换结果。比如定义nxt[i][j]表示从位置j出发跳2^i步能到的最远位置转移形式仍然是nxt[i][j] nxt[i-1][ nxt[i-1][j] ]。然后查询时按照k的二进制位一路跳下去。我在实际做题中遇到这类题目最多的坑是不要把nxt[i][j]定义成“恰好跳2^i步”而应该定义成“不超过2^i步时能达到的最优状态”。因为很多题目里的最优策略是“尽量远跳”不超过反而更好写而且不改变复杂性。3.2 动态规划边界引用与溢出的经典误用写倍增DP时状态数组的下标经常涉及二维一旦n达到1e5、log层达到20数组大小就是2e6这还在内存接受范围内。但很多人习惯性地把数组定义为int st[100005][20]没问题。危险的是升级到三维或者开了vector套vector内存直接翻几倍可能MLE。另一个常见问题是1 j的溢出。如果j达到311 j已经超过int的范围必须用1LL j。很多人在LCA的深度差值计算中踩这个坑数据一大就WA得莫名其妙。我的建议是写一个常量LOG20或21因为2^201048576一般足够n2e5的题但如果是n1e5的树你要开到17层加一个冗余最稳妥是开20以上看数据范围灵活调整。还有就是下标从0开始还是从1开始。树上节点从1开始编号是竞赛惯例如果混着用预处理father数组时容易漏掉0号节点。我的偷懒办法是初始化up[0][i]0表示节点0的父节点是0这样就算跳出了树也不会越界而是跳到0号哨兵节点后续判断时只要排除0就行。4. 真题场景从“24年csp-s决斗”热词聊到倍增的实战扩展4.1 “决斗”这种游戏类题目的倍增化思考热词里频繁出现“csp-s决斗”很多人一脸懵其实就是那种带轮次模拟的对抗类题目。比如有n个人站成一圈每轮每个人和旁边的人决斗输的人退场赢的人继续问最后剩谁。这类题的朴素模拟复杂度是O(n^2)一旦n上了1e5就无解。但如果决斗规则是已知的、可预处理的就可以用倍增设计出“每2^i轮后谁会站着”的状态转移。每一轮根据相邻选手的胜负关系更新存活状态这本质上是一个可以复合的函数所以完全符合倍增的条件。这里的关键是决斗规则必须是“局部确定的”也就是当前轮次的胜负只取决于相邻两个人的能力值不会受全局状态影响。这个条件一旦满足就可以预处理出跳2^i轮后的情况查询和模拟就快得飞起。4.2 倍增与二分结合的套路倍增和二分经常是组合拳。有一种经典的题目类型是“求从某个点出发在满足条件的情况下最多能走多远”。暴力是从起点一步一步走二分是枚举终点然后判定倍增则可以直接尝试跳大步。比如我用倍增从大到小试跳如果能跳到某个位置且满足条件就跳过去直到再走一步就不满足条件为止最后停下来的位置就是最远合法位置。这种做法避开了二分的log常数在某些场景下甚至更自然。一个具体的应用场景是“在有序数组里找某个区间内最长的满足某种性质的子段”。倍增加一个check函数整体复杂度是O(n log n)思路清晰代码量还不大。我记得某年CSP-S的某道树上路径题就是先套了个倍增的最远跳跃预处理再配合一个双指针滑动区间把两条链的解法合到了一起。5. 倍增代码的工程化细节与调试经验5.1 外层循环顺序和数组大小的选择我把倍增代码的循环规则总结成一句话先枚举步数的指数层数再枚举位置。你永远不应该把位置放在外层、指数层放在内层否则f[i][j-1]的值还没算出来你就在用它推导f[i][j]了结果全是0。数组大小方面我习惯这样定义const int LOG 20; int f[100005][LOG 1];如果题目标明n最大是2e5那LOG取18就够用了2^18 262144但我一般会取20留出冗余。原因很简单比赛时不差这4层的内存但如果你LOG开小了diff的二进制位不够用查询时就会踩到下标越界这个bug非常隐蔽运行时不一定崩但答案肯定是错的。调试时有一个好用的技巧如果你怀疑自己的倍增预处理有问题先暴力验证小数据。随机生成n10以内的数据写一个朴素模拟对比你的倍增代码跑出来的结果逐条对拍。这个不过就是十分钟的事但能救回你一下午的瞎排查。5.2 位运算优先级与读入优化位运算的优先级比算术运算符低比比较运算符也低这是很多人踩过的坑。比如你写if (diff i 1)这个没问题因为比优先级高但如果你写if (diff (1 i))也别在这搞什么多余括号直接这样就行因为括号足够清楚了。如果你把条件写成if (diff 1 i)这里其实也能编译通过因为1 i先执行但我强烈不建议这样写——考试时越简单直观越好宁可多打一对括号也不要省这个功夫。读入优化强烈建议用快读。倍增类题目通常伴随大量查询每次都用cin读入1e5条询问时间直接翻倍。用scanf天然会快一点用我下面这个快读模板最稳inline int read() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; }在CSP-S这种时间卡得紧的考试里这个快读往往就是你能不能过最后一组的胜负手。5.3 常见问题速查表症状可能原因解决方向预处理后f数组全是0内外层循环顺序写反外层枚举j内层枚举i查询结果总是空跳一步位运算条件写错检查diff i 1是否正确出现莫名其妙的大数错误1 j溢出int改成1LL j或直接开long long递归爆栈DFS深度太深改用BFS预处理或开栈空间树上节点逃出树外up数组边界没处理定义哨兵节点0up[0][i]0LCA查询返回错误节点第二段从高到低循环写成了从低到高必须从LOG到0递减枚举这六个问题是我带学生和平时看群友求助时见到的高频错误你写之前先看完这张表能避开七成的低级失误。6. 考场上的倍增“三板斧”与我的个人习惯一年下来我刷了不少真题发现适用倍增的题不管表面上包装成什么样最终都会落到这三个框架之一快速幂式二进制拆分、RMQ跳表式合并、树上跳跃式祖先查询。拿到一道题先看数据范围如果n是1e5到2e5、查询次数也是1e5级别并且操作可以预处理、可以复合那倍增大概率是最优解之一。我的个人习惯是先写下状态定义用注释写在代码开头比如// f[i][j]: 从i出发走2^j步到达的位置然后把初始条件写在前面预处理循环写在后面查询函数单独写一个。这样代码结构很清晰查bug的时候也容易定位。还要提一下“C环境”这件事。有同学问VS Code怎么配置才能跑通这些代码其实信奥赛一般用的都是标准C环境编译选项常是g -O2 -stdc14。你不需要什么花哨的IDE一个顺手的环境加一个能单步调试的编译工具就够了。核心是你对模板代码的熟练度而不是工具的高级程度——当然这句话也只针对复习阶段的同学真到比赛用的都是考场统一系统平时练的就是手感和思路。7. 这套思想能继续扩展到的地方我一直觉得倍增之所以值得反复琢磨不只是因为高频考点而是它教会你一种“用空间换时间”的结构化思维。你会了倍增之后树链剖分里的跳链思路、并查集按秩合并的跳跃逻辑、字符串哈希的滚动思想都和倍增有千丝万缕的联系。如果你是在备战最近的CSP-S我建议你把快速幂、ST表、LCA这三个模板背到滚瓜烂熟然后去找历年真题里涉及树上路径、区间查询、跳跃模拟的题每道题先用暴力写一遍再用倍增优化写一遍对拍验证。这个过程非常痛苦但也是最有效的。记住考场上最怕的不是不会新算法而是拿着倍增模板却不知道什么时候用。多看题、多对拍、多总结这比背更多炫技的算法有用得多。