倍增算法详解：从二进制拆分到ST表与LCA实战

倍增这词第一次听到的时候不少人心里会咯噔一下觉得这是不是某个高深的数学公式。实际上它就是我们平时说的步子迈大一点只不过它是按2的幂来迈。你不需要一步步往上爬而是手里提前备好1格、2格、4格、8格的跳板遇到要走多少步的问题拆成几个二进制块一蹦就到位。这套思想在算法竞赛、面试题、甚至工业级组件里出现频率极高。快速幂、ST表、最近公共祖先、跳表背后都是同一个底子。可以说把倍增吃透等于一次性解锁了至少五六个高频算法题型的核心思路。这篇文章不搞玄乎推导用大白话把来龙去脉讲清楚代码、边界、坑点都给你拆开看完能自己手写那种。1. 倍增算法的核心逻辑与设计思路1.1 一切源于二进制拆分先说一个最基础的数学事实任何正整数都能写成若干个2的幂之和而且写法唯一。比如13这个数二进制是1101展开就是841也就是2³2²2⁰。再比如27二进制11011展开是16821也就是2⁴2³2¹2⁰。这句话看起来平平无奇但它是倍增算法的命根子。因为能用二进制拆就意味着当我们需要执行一段长度为x的连续操作时不需要把x从头到尾一步步来一遍。只要预先准备好长度为1、2、4、8、16……的操作结果就能把这些块拼接起来快速得到最终答案。这里有一个容易忽略的细节二进制的每个位上要么是0要么是1所以每个2的幂块要么用一次要么不用。不存在用半块的情况。这一点保证了算法在拼接过程中不会出现拆分不干净的问题。1.2 预处理 跳跃把线性变对数倍增算法的标准形态通常长这样先预处理一张表记录从每个位置出发走2^j步之后的状态。然后面对任意一个步数x把x按二进制拆开用若干个2的幂步长组合完成目标。举个例子如果你想从某个节点往上跳13次13拆成841你只需要三次跳跃先跳8步再跳4步再跳1步。三次操作完事而不是循环13次。这里的核心转变是把线性推进变成了跳跃式推进。单次查询的复杂度从O(x)降到O(log x)。x哪怕达到10⁹量级二进制位也就30位左右30次操作就能搞定性能提升是指数级的。用大白话打比方你在玩跳棋普通棋子一格一格走现在给你装备了1格、2格、4格、8格的跳板。走13格你直接跳841而不是走13次。数据结构语境里这些跳板就是预处理出来的表。1.3 复杂度真相时间预处理一般O(n log n)单次查询O(log n)空间额外O(n log n)对比暴力方法比如树上单次查询LCA的朴素做法最坏情况下要O(n)一次查询还好但如果有10⁵次查询暴力就跑不动了。倍增的意义不在于单次有多快而在于把预处理成本均摊到大量查询上换取每个查询对数级的速度这在竞赛和工程里都非常划算。很多人第一次学倍增会陷入一个误区以为它是某种记忆化搜索。其实记忆化是算过的不重复算倍增是提前把所有2的幂步长结果都算好查询时拼凑。两者是不同层面的优化思想不要混在一起。2. 从快速幂入手理解倍增的第一现场2.1 朴素乘方为什么慢如果让你算2¹⁰你自然会写一个循环乘10次。如果让你算2^{10⁹}还要对某个大质数取模循环10⁹次就非常痛苦了。快速幂的思路非常直白把指数按二进制拆开。比如求2¹⁰指数1082所以2¹⁰ 2⁸ × 2²。问题就变成怎么不循环10次拿到2⁸和2²这两个数答案是不断让底数自平方。底数a每次平方得到的序列是a¹、a²、a⁴、a⁸、a¹⁶……每一次平方指数翻倍。这本身就是倍增的过程。遍历指数n的二进制位遇到某一位是1就把对应的那一个平方结果乘到最终答案里去。2.2 核心代码实现C写法long long fast_pow(long long a, long long n, long long mod) { long long res 1; while (n 0) { if (n 1) { res res * a % mod; } a a * a % mod; n 1; } return res; }Python写法def fast_pow(a, n, mod): res 1 while n: if n 1: res res * a % mod a a * a % mod n 1 return res初学者最容易卡住的地方是为什么a每次都自平方因为指数向左移动一位意味着当前需要追踪的底数幂次翻倍。n的二进制位里如果当前最低位是1说明这一位对应的2^k块需要用到就把当前自平方得到的a累乘进res。这里有一个实用小技巧如果mod设为0或不传底数和指数又可能很大中间乘法很容易溢出。C里建议直接用long long承接乘法结果如果模数接近10⁹级别乘法两边都可能接近10⁹乘积就超出long long范围了。这种情况要改用快速乘或者用__int128临时过渡。快速幂看起来简单但它完整演示了倍增的三大步骤二进制拆分、步长倍增预处理、查询时按需组合。后面所有倍增算法本质都逃不出这个框架。3. ST表解决区间最值查询的高效方案3.1 RMQ问题是什么给定一个静态数组反复询问某个区间[l, r]里的最大值或最小值。数组只读不修改要求快速响应大量查询。暴力做法很好理解每次查询从l遍历到r复杂度O(len)。如果数组长度10⁵查询次数10⁵最坏情况下就变成了10¹⁰次操作直接卡死。ST表就是为静态区间最值查询这种场景量身定做的。它只用O(n log n)预处理就能做到每次查询O(1)。ST表的核心定义是st[i][j]表示从下标i开始长度为2^j的区间里的最大值。初始状态j0区间长度为1st[i][0]就是数组本身arr[i]。递推关系是st[i][j] max(st[i][j-1], st[i2^(j-1)][j-1])。为什么递推式长这样因为长度为2^j的区间可以拆成两半每一半长度恰好是2^(j-1)。前半段从i开始后半段从i2^(j-1)开始。两个子区间取最大值就是整个区间的最大值。这个递推本身是标准的倍增思路步长从1变2、2变4、4变8不断翻倍。3.2 查询时的重叠覆盖查询[l, r]区间长度len r - l 1。我们取k floor(log2(len))然后求max(st[l][k], st[r - 2^k 1][k])这里让不少初学者困惑的是这两个区间明明可能重叠为什么还能保证答案正确因为最大值操作是幂等的两个区间有重叠部分也不影响取max。左区间覆盖从l开始的长2^k段右区间覆盖从r-2^k1结束的长2^k段。2^k不超过len因此这两段一定能覆盖整个[l, r]。重叠是允许的且重叠区域只是被重复考虑了而已。所以用max、min这类操作时ST表可以O(1)查询。如果是求和这类不支持重复计算的操作就不能这样直接重叠覆盖。另外需要注意这里的k必须是整数。直接用log2()函数计算浮点数再取整容易因为精度问题拿错值。比如log2(8)在某些环境下可能因为浮点误差返回2.9999999向下取整成2那就错了。正确做法是预计算一个整数log数组lg[i]lg[1] 0lg[i] lg[i/2] 1。这样可以严格保证lg[len]等于floor(log2(len))。3.3 参考代码const int N 100005; int a[N]; int st[N][18]; int lg[N]; void build(int n) { lg[1] 0; for (int i 2; i n; i) { lg[i] lg[i / 2] 1; } for (int i 1; i n; i) { st[i][0] a[i]; } // 枚举步长倍增 for (int j 1; (1 j) 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]); } } } int query(int l, int r) { int len r - l 1; int k lg[len]; return max(st[l][k], st[r - (1 k) 1][k]); }代码里的第二层循环i的右边界是n - 2^j 1。这个下标处理是ST表最容易写错的地方一不留神就越界。写代码时推荐先算一下边界公式再动手别凭感觉。3.4 ST表 vs 线段树很多人在学会线段树之后会想那还要ST表干什么这里做一个对比维度ST表线段树预处理复杂度O(n log n)O(n)建树单次查询复杂度O(1)O(log n)单点更新不支持需重建O(log n)实现难度简单中等偏上适用场景静态数组大量区间查询动态修改加查询所以ST表的定位很明确数组完全静态、查询特别高频的场景。它用固定的预处理成本换取每次查询的极致速度。线段树则适合要频繁修改数组的场景。按照实际需求选择不要为了炫技硬选。4. 树上倍增求LCA从0到1的完整实战4.1 LCA是什么朴素做法为什么慢LCA全称Lowest Common Ancestor最近公共祖先。给定一棵根确定的树对任意两个节点u和v找到离它们最近的、同时是两者祖先的节点。比如树里节点u在左子树很深的地方节点v在右子树它们的LCA往往是某个中间层的根节点。朴素做法从u一路向上标记到根再从v向上走遇到的第一个被标记过的节点就是LCA。最坏情况下比如一条链每次查询要向上走O(n)步查询一多直接爆炸。倍增法LCA的思路就是每次让你少走几步用预处理好的2的幂步长来完成深度对齐和共同攀爬。4.2 预处理阶段搞清depth和up表先通过一次DFS或BFS遍历整棵树记录两个东西第一个是depth[u]节点u的深度。根节点深度设为0或1都可以但全代码要保持一致。第二个是up表up[u][j]表示从u向上跳2^j步到达的节点。初始j0时up[u][0]就是u的父节点。根节点的父节点可以设成自己这样往上跳再多也不会跳到不存在的空指针能大大简化边界处理。关键在于递推up[u][j] up[up[u][j-1]][j-1]这个递推的含义是从u跳2^(j-1)步到up[u][j-1]然后再从这个节点跳2^(j-1)步总共跳了2^(j-1) 2^(j-1) 2^j步到达up[u][j]。这里最底层的逻辑依然是倍增步长翻倍信息逐层构建。预处理阶段的DFS代码框架void dfs(int u, int parent) { up[u][0] parent; for (int j 1; j LOG; j) { up[u][j] up[up[u][j - 1]][j - 1]; } for (int v : adj[u]) { if (v parent) continue; depth[v] depth[u] 1; dfs(v, u); } }如果树的规模很大比如10⁶个节点递归DFS容易爆栈建议改成显式栈的迭代写法。C竞赛环境可以加大栈空间但工程代码里尽量用迭代这个后面会说。4.3 查询LCA的完整流程查询LCA(u, v)分三步走第一步深度对齐。如果depth[u] depth[v]就交换u和v保证u更深。然后算出差值diff depth[u] - depth[v]把u向上跳diff步让u和v处于同一深度。这里就用到二进制拆分diff的二进制位里哪些位是1就跳到对应的2^k步。参考写法int diff depth[u] - depth[v]; for (int j 0; j LOG; j) { if (diff j 1) { u up[u][j]; } }如果对齐后u等于v说明v本来就是u的祖先直接返回uLCA查询结束。第二步从高位往低位枚举跳跃。初始从大到小看up[u][j]和up[v][j]是否不同。如果不同说明这两个节点在第2^j步内的祖先有分叉那就把u和v同时向上跳2^j步缩小它们与LCA的距离。这里有个极易踩的坑为什么从高位往低位因为高位跳跃的影响大先跳大块再跳小块能保证最终停在LCA的下方。如果从低位往高位跳你可能会跳过LCA或者跳到公共祖先之上最后得不到正确结果。第三步最终u和v是LCA的两个子节点返回up[u][0]即可。查询函数int lca(int u, int v) { if (depth[u] depth[v]) swap(u, v); int diff depth[u] - depth[v]; for (int j 0; j LOG; j) { if (diff j 1) { u up[u][j]; } } if (u v) return u; for (int j LOG - 1; j 0; --j) { if (up[u][j] ! up[v][j]) { u up[u][j]; v up[v][j]; } } return up[u][0]; }这里有一个细节可以留意在第二步高位枚举时条件判断只用up[u][j] ! up[v][j]没有判断深度。因为此时u和v已经深度相同同时跳2^j步后它们的深度仍然相同所以不会出现一个跳到上面、一个还在下面的情况。这个性质保证了对齐过程的有效性。如果树有可能是一个森林多棵独立的树查询前需要先判断两个节点是否在同一棵子树里通过并查集或者预处理时给每棵树打不同编号都能实现。4.4 关于LOG大小的确定LOG要取多大直接决定up数组能不能装下。一般取ceil(log2(n)) 1。n是节点数。2^18 2621442^19 524288如果n是10⁵级别LOG取18或19就够。稳妥起见我会把LOG取到20甚至21多出来的空间用来防止边界溢出。贪省空间的危害是当树退化成一条链最深的深度接近n如果LOG太小up[u][j]在遍历时访问到越界下标导致结果错乱。建议养成习惯额外2。4.5 换根树的LCA变形有些场景不是固定根而是每次动态换根。这时候不能直接套用上述DFS的父节点关系。常见的处理技巧是仍然以某个固定根做预处理然后通过深度和祖先关系判断。比如当前根是r要查u和v的LCA可以拆成三对固定根LCA再取深度最大的那个。这个技巧叫三点LCA在很多树上问题里非常实用。5. 倍增思想的更多应用场景5.1 跳表链表上的倍增跳表就是一个典型的链表倍增结构。普通链表找某个元素只能从头遍历复杂度O(n)。跳表在原始链表之上增加多层索引每一层索引的节点数量是下一层的一半相当于层数越高步长越大。带了一层一层向下逼近的过程本质就是在用不同大小的2的幂步长搜索。Redis有序集合的底层实现就用了跳表。它的插入、删除、查找复杂度都能做到O(log n)而且比平衡树更容易实现和理解。行业里称之为链表二分思想的产物实际上就是倍增思想在数据结构上的经典应用。5.2 后缀数组的倍增构造法后缀数组求所有后缀的字典序排序。朴素做法是直接对所有后缀排序每次比较需要O(n)整体O(n² log n)完全无法接受。倍增构造法的思路是第一轮先按照每个位置长度为1的子串排序下一轮把长度翻倍用上一轮的排序结果作为两个关键字排序每轮排序长度翻倍。这样需要的轮数只有O(log n)配合基数排序总复杂度可以做到O(n log n)。这里把倍增二字体现得淋漓尽致每次需要处理的信息长度翻倍利用已有信息避免重复计算。5.3 倍增DP与跳跃游戏很多从某点出发走k步到达哪里的问题都可以用倍增预处理。比如图上每个点有唯一出边问走k步到哪个点这就是经典的倍增跳表。预处理f[i][j]表示从i出发走2^j步到达的点然后任意k都能在O(log k)时间内分解。这类题在关于环和函数图的问题中经常出现思路和树上的LCA高度相似。5.4 应用场景汇总应用解决的问题步长来源快速幂大指数幂次计算指数二进制位ST表静态区间最值查询区间长度翻倍树上倍增LCA最近公共祖先查询树的深度差、祖先链跳表有序链表的查找多层索引间隔翻倍后缀数组倍增法后缀排序子串长度翻倍递增跳表DP图走向问题行走步数翻倍这么多场景共用同一个底子说明倍增不是一个孤立算法而是一类算法思想。遇到单次操作需要连续执行多次且结果可以阶段性复用的问题都应该往倍增方向想一想。6. 实战中的常见问题与排查技巧6.1 数组边界和空节点处理这是做题时最常见的错误来源。up数组第二维开多大刚才说了LOG永远多取一点。u往上跳到根之后怎么办最优雅的方式是把根节点的父节点设成它自己这样无论怎么继续跳最后都落在根节点上不会出现越界。根从1编号up[1][j]1即可。如果你习惯用0表示空逻辑上也能通但每次模拟跳跃时都必须多加一道判断往上跳是不是跳到空了代码冗长且容易漏。实战经验是用自环根处理代码干净很多。6.2 整型log计算的精度坑计算log2时用log2()函数再强制转int极大概率出现精度问题。比如log2(8)可能返回2.999999999向下取整变成2。这不是特定编译器的问题而是浮点数的固有误差。SAFE的做法是预计算lg数组前面ST表已经给过代码。如果是Java可以用31 - Integer.numberOfLeadingZeros(x)。C里用__lg(x)或者自写循环都行。6.3 递归爆栈树太长的隐患树退化成一条链时DFS递归深度可能达到10⁵量级。C默认栈空间往往撑不住。解决方式有几个一是用系统命令调大栈空间这在算法竞赛中常用但工程化不推荐二是把DFS改成显式栈的迭代写法三是用BFS先求出深度和父节点再倒序计算up表因为up依赖父节点BFS的顺序天然保证父节点先于子节点处理。BFS做法里取up[u][j]的时候up父节点相关数据已经算好了不需要递归很稳妥。6.4 常见错误速查现象可能原因解决办法LCA查询结果错误深度对齐时diff二进制拆分写错检查diff j 1的判断数组越界或段错误LOG开太小跳到了临界值LOG ceil(log2(n)) 1永远多开浮点数log精度问题用了log2()再取整改为预计算整数lg数组结果始终是根节点根节点的父节点没有正确设置将up[根][j]设为自己递归爆栈树退化成链用BFS或迭代栈替代递归DFS查询时目标节点之间的深度不同没有先做深度对齐先交换保证u更深再按diff跳6.5 如何正确调试倍增代码我调试这类代码的经验是先写一个小数据暴力验证比如一棵7个节点的树所有节点对都算一遍LCA拿朴素方法对拍。只要小数据全对大数据基本不会有逻辑错误剩下的问题多半是数组越界或者内存。如果直接在大数据上跑错了也定位不了。学会对拍是算法题的基本功尤其在倍增这种预处理和查询分离的代码里暴力对拍能最快揪出哪里逻辑不对。7. 我的个人实操体会学习倍增的过程中我自己最深的一点体会是不要死背代码而是抓住三个关键词——2的幂、预处理、按位拼接。你只要理解任意步数都能拆成2的幂之和倍增算法就已经掌握了一半。写代码的时候建议从快速幂开始练习。它代码最短但把倍增的框架完整体现了一遍。写熟了之后再看ST表你会发现ST表只是把倍增用在了区间上。最后再挑战树上LCA这个时候你已经知道怎么处理步长跳跃剩下的就是对树结构的理解了。还有一个经验调试树相关问题最好自己画一棵小树7个节点就够了把每个节点的depth和up表手工算出来再拿代码去跑。纸上能算明白代码就一定能写明白。倍增最怕的就是脑子里一团浆糊就上手写出来的代码往往边界错漏百出。先把小例子吃透再上规模效率反而最高。如果你后续还要接触树上差分、重链剖分这些进阶内容倍增LCA更是绕不开的基础。它不只是一个算法模板更是一把打开树上路径问题的钥匙。看懂它后面很多东西学起来会顺畅很多。