倍增算法详解：从快速幂到ST表与LCA的编程实践

经常有同学来问我“老哥我一看到题目里要查询最近公共祖先、要快速求幂、要高效区间最值就知道要用什么算法但不知道原理看大佬代码能看懂个大概自己一写就懵。这个叫‘倍增’的东西到底是啥”那今天我就把这层窗户纸捅破用大白话把倍增算法从头到尾掰开揉碎了讲清楚。既然是白话系列我尽量不讲一堆吓人的数学符号而是从最朴素的直觉出发讲明白它到底是什么思路、解决什么问题、代码为什么那么写。你学完之后会发现这玩意真的没那么玄乎就是一层窗户纸的事。这篇文章适合刚接触算法竞赛、正在学数据结构或者刷 LeetCode 遇到“求 LCA”“RMQ 问题”时一脸蒙圈的读者。我保证你看完之后至少能看懂 90% 的倍增代码在干什么自己也能根据模板改出一版能跑的代码。1. 倍增算法到底是个啥先别急着看代码这一步是最重要的。很多人学算法卡住不是因为后面的步骤有多难而是第一层概念就没有建立起来。1.1 从一个最简单的问题说起问你一个纯数学问题计算 2 的 13 次方2^13你会怎么算我猜正常人会这样在计算器里连续乘 13 次 2得出 8192。确实没错。但如果问题是计算 2 的一亿次方呢总不能写个循环乘一亿次吧程序会慢到怀疑人生。这时候就该换个思路了。我们先把 13 这个次数用二进制拆开来看13 8 4 1写作二进制就是 1101也就是 1 个 8、1 个 4、0 个 2、1 个 1 拼起来的。既然指数能拆成这样那原来的幂运算就可以这么分解2^13 2^8 × 2^4 × 2^1而其它的 2^1、2^2、2^4、2^8 怎么来很简单后一个是前一个自己乘自己2^2 (2^1)^22^4 (2^2)^22^8 (2^4)^2看到了吗我只需要循环把底数不断平方同时在二进制位上是 1 的位置把结果累乘进去。循环次数不再是 13 次而是 log2(13) ≈ 4 次。这就是“倍增”最朴素的一种体现我每次要做的事情都是基于上一次的结果直接翻倍得到而不是重新从头遍历一遍。1.2 倍增思想的本质把刚才的直觉总结成一句话倍增算法就是先把所有大小为 2 的幂次的“步长”信息提前预处理出来然后在真正查询时用待查询数字的二进制表示把我们需要的若干个 2 的幂次“拼”起来从而把原本 O(n) 甚至 O(n^2) 的复杂度降到 O(log n) 甚至 O(1)。为什么能拼因为任意一个正整数都可以用若干个 2 的幂相加表示这是二进制的基本性质。这个性质是整个倍增算法赖以成立的基石。为了更好理解你可以想象成跳台阶。普通方法是一步一步往上迈每次迈 1 格要走 13 格就得迈 13 次。倍增的方法是我给自己准备好“1 格跳板”“2 格跳板”“4 格跳板”“8 格跳板”……每个跳板都是上一块的两倍长。这样一来想到达第 13 格只需要用 8 4 1 的组合跳 3 次就到位了。这就是为什么它叫“倍增”——每一步跳跃的距离都是前一次的 2 倍而不是固定长度。1.3 倍增和二分有什么不同这里我特别想掰扯一个容易混淆的点。很多初学者喜欢把倍增和二分混在一起因为它们都长着一张“一半一半”的脸但本质上是完全不同的思路。二分的思路是“逐步缩小”我拿着一把尺子先量总长度然后不断取中点根据条件判断目标是左半还是右半每次都把搜索范围砍掉一半。它的核心是“减治”需要先知道一个边界条件然后逼近答案。倍增的思路是“逐步扩大”我拿着一摞长短不一的跳板从长往短试能跳就跳最后拼出一个精确的距离。它的核心是“累加凑合”不需要预先知道答案在哪只需要保证“跳过头之后能回头重试”。打个比方二分猜数字你每次猜中间对方告诉你是大了还是小了。倍增跳台阶你直接从第 8 格开始跳跳完发现还剩 5 格再补一个 4 格的跳板还剩 1 格再补一个 1 格的跳板落点刚好。这个区别在代码里很明显二分是一个 while 循环里不断更新 mid倍增则是一个 for 循环从大到小尝试 2^k 的步长。两者不能混为一谈。2. 倍增的经典应用ST 表前面的快速幂只能算热身真正能体现倍增威力的是数据结构里的应用。第一个要讲的就是 ST 表它能在 O(1) 时间内回答任意区间的最大值/最小值查询解决的是经典的 RMQ 问题。2.1 ST 表能解决什么问题假设你有一个长度为 10 万的数组然后程序会不停问你第 3 个位置到第 7 个位置的最大值是多少第 100 个位置到第 99999 个位置的最小值是多少一共问 10 万次。最笨的办法每次查询都从 l 到 r 循环扫一遍。如果区间平均长度是 5 万那么总复杂度就是 O(n × q) 10^5 × 5 × 10^4 5 × 10^9这在普通机器上至少要跑几十秒直接超时。ST 表就是来解决这个问题的。它通过预处理把所有长度为 2 的幂次方的区间最值都算好查询时只需要把任意区间拼成两段长度为 2 的幂次的区间取最值一步到位。这里有一个天然的前提条件我用你最好注意ST 表只适用于静态数组。也就是说数组建立之后就不会再修改。如果有人这时说“我改一下某个位置的值你再帮我查一下”那 ST 表就直接抓瞎了因为预处理的任何一次修改都可能影响很多个区间值。如果是“带修改的区间最值查询”请老老实实用线段树。2.2 预处理的核心逻辑ST 表的预处理其实特别简单就是一张二维表 st[i][k]表示从数组第 i 个位置开始长度为 2^k 的子区间的最值。比如 st[3][2] 就是从下标 3 开始长度为 2^2 4 的区间 [3, 6] 的最大值。那么区间 [3, 6] 可以拆成两半[3, 4] 和 [5, 6]。这两半长度都是 2正好可以分别用 st[3][1] 和 st[5][1] 表示。于是st[3][2] max(st[3][1], st[5][1])推广成一般公式就是st[i][k] max(st[i][k-1], st[i 2^(k-1)][k-1])这个公式看起来啰嗦但理解起来很简单长度为 2^k 的区间拆成两个长度为 2^(k-1) 的区间取最大值就行。这就是倍增思想的“合并”环节——因为我只需要把两个等大的子区间拼起来后一半的起点正好是前一半的起点往后挪 2^(k-1) 个位置。预处理时k 从 1 开始逐渐增大每一层都要用到上一层的计算结果。这个“依赖关系”决定了循环的顺序我们后面写代码时要特别注意。注意预处理的循环必须把 k 放在外层i 放在内层。这是因为计算长度为 2^k 的区间时依赖的是长度为 2^(k-1) 的所有位置的结果。如果 i 在外层 k 在内层那么还没有算出来的 2^(k-1) 层就会变成垃圾值。2.3 查询为什么要重叠取最值预处理做完了查询就非常简单了。假设你要查询区间 [l, r]区间长度 len r - l 1。我们先找到小于等于 len 的最大 2 的幂次假设为 2^k。然后答案 max(st[l][k], st[r - 2^k 1][k])你可能发现一个问题这两个区间长度都是 2^k但它们加起来可能比 [l, r] 更长会有一部分重叠。这没关系因为我们求的是最大值或者最小值重叠并不影响结果。你只需要保证这两个区间的并集能够完全覆盖住 [l, r] 就行。想象一下你要在几间连在一起的房间里找最重的箱子你搬来两块大木板左侧木板从左墙一直盖到中间右侧木板从中间一直盖到右墙。两块木板在中间确实重叠了但你只需要看两块木板的交集并集——反正每块木板自己区域内的最大值已经知道了两个最大值再比一下覆盖区域的最大值不就是答案吗这个“重叠没关系”的特性是 ST 表能够 O(1) 查询的关键。如果是求和问题这种重叠就会出大问题因为你等于把重叠区域的数算了两遍。所以 ST 表一般只用来处理最大值、最小值、最大公约数这类满足“可重复贡献”性质的运算。“可重复贡献”这个词看起来高大上其实意思就是同一个数被算两遍不会影响结果。最大值、最小值、gcd 都是这样的运算但“区间和”就不是。2.4 代码实现与 log 数组的预处理下面给出一个完整的 ST 表代码。我写代码有个习惯就是先把每个变量是什么意思注释出来免得三个月后自己都看不懂。#include bits/stdc.h using namespace std; const int N 100005; const int LOG 20; // 因为 2^20 1e6所以 20 层足够覆盖 10^5 级别的数组 int a[N]; // 原始数组下标从 1 开始 int st[N][LOG]; // st[i][k] 表示从 i 开始长度为 2^k 的区间最大值 int lg[N]; // lg[i] 表示 i 取以 2 为底的对数向下取整 void build(int n) { // 第 0 层长度为 1 的区间最大值就是自己 for (int i 1; i n; i) st[i][0] a[i]; // 预处理 log 数组方便查询时 O(1) 找 k lg[1] 0; for (int i 2; i n; i) lg[i] lg[i 1] 1; // 核心预处理从小的区间长度逐步翻倍到大的 for (int k 1; (1 k) n; k) { for (int i 1; i (1 k) - 1 n; i) { st[i][k] max(st[i][k - 1], st[i (1 (k - 1))][k - 1]); } } } int query(int l, int r) { int k lg[r - l 1]; // 找到不超过区间长度的最大 2 的幂 return max(st[l][k], st[r - (1 k) 1][k]); } int main() { int n 10; int arr[] {0, 3, 9, 1, 4, 7, 2, 8, 5, 6, 1}; // 下标 1 到 10 for (int i 1; i n; i) a[i] arr[i]; build(n); printf(区间 [2, 7] 的最大值: %d\n, query(2, 7)); // 应该是 max(9,1,4,7,2,8) 9 printf(区间 [4, 9] 的最大值: %d\n, query(4, 9)); // 应该是 max(4,7,2,8,5,6) 8 return 0; }这里我额外说明一下 lg 数组的处理。lg[i] lg[i 1] 1这其实就是i 的对数等于 i/2 的对数加 1。因为 i 和 i/2 在二进制上只是右移了一位对数值正好相差 1。你背不下这个公式也没关系直接调用系统的 log2 再取整也行不过预处理一个数组肯定比每次调库函数快得多。这段代码里查询时的r - (1 k) 1是关键它算的是右侧区间的左端点。你画个图就理解了左侧区间是 [l, l2^k-1]右侧区间的长度也是 2^k为了让它覆盖到 r它的左端点必须满足左端点 2^k - 1 r所以左端点 r - 2^k 1。这一步稍微绕一点但以后写多了就顺手了。3. 倍增算法在树结构中的应用LCA如果说 ST 表是倍增在“线性结构”上的应用那 LCA 就是倍增在“树形结构”上的经典之作。这也是算法竞赛里考得最频繁的一个点。3.1 为什么要用倍增求 LCA先介绍一下背景。LCA 全称是 Lowest Common Ancestor中文叫最近公共祖先。给你一棵树和两个节点问你这两个节点往上走到根的过程中第一次碰头的节点是谁。最朴素的思路是先让深度比较深的一个节点一直往上爬到根把路径上经过的所有节点都记录下来形成一张“标记表”。然后让另一个节点也往上爬每爬到一格就查一下表格第一个在表格里出现的节点就是答案。这个方法听起来可行但最坏情况下如果这棵树退化成一条链想象你把一棵树拉直成一根面条的样子两个节点分别在链的两端那么前一个节点爬完整条链是 O(n)另一个节点可能也要爬 O(n)。如果查询特别多这个复杂度就爆炸了。倍增的思路是我提前在树上做点手脚把每个节点往上走 2^0、2^1、2^2……步分别能走到哪个节点都算出来。等到真正查询时我直接利用这些“跳板”大幅跨越而不是一格一格地跳。3.2 预处理如何安排每个节点的“祖先跳板”预处理时我们先让每个节点记下自己的父节点第 2^0 级祖先然后再用递推的方式一层层往上推算。假设 up[u][k] 表示从节点 u 出发向上走 2^k 步到达的节点编号。那么up[u][0] 节点 u 的父节点up[u][1] up[ up[u][0] ][0] 也就是爷爷节点up[u][2] up[ up[u][1] ][1] 也就是往上走 4 步要到达的节点写成通式就是up[u][k] up[ up[u][k-1] ][k-1]这个公式的美妙之处在于从 u 向上走 2^k 步可以拆成先向上走 2^(k-1) 步再继续向上走 2^(k-1) 步。第一部分用 up[u][k-1] 得到中间节点第二部分就是 up[中间节点][k-1]。你看这个思路和 ST 表如出一辙都是拿“长度为上一半的区间拼出整个区间”只不过这里把“区间”换成了“树上的祖先路径”。具体实现上一般用 DFS 遍历整棵树。遍历到一个子节点时子节点的父节点是已知的就是当前节点 u然后再用上面那个公式把子节点的 up 数组其它层全部算出来。过程中需要特别注意DFS 深度如果达到 10 万级别在有些平台上递归可能爆栈。我一般会把递归深度设为至少 20 万或者改用 BFS/迭代的方式来避免问题。这一点很多新手到线上评测时会突然遇到“栈溢出”的报错半天找不到原因。3.3 查询过程从大树根往上跳的两种姿势预处理完 up 数组之后查询 lca(a, b) 的过程就是重头戏了。我习惯分两步走。第一步让深度深的那个节点先往上跳直到它的深度和另一个节点一样。这里就用到刚才说的二进制拆分假设 a 比 b 深深度差是 d我们不需要一步一步跳只需要从大到小枚举 k如果 d 的二进制某一位是 1就让 a up[a][k]一次性跳 2^k 步。第二步两个节点深度相同了开始一起向上跳。这里有一个特别容易写错的细节我们从大到小枚举 k只有在 up[a][k] ! up[b][k] 的时候才跳。为什么因为我们不希望直接跳到公共祖先上去那样没法判断是不是最近的那个。我们要做的是让 a 和 b 跳到它们最近公共祖先的下面一层然后再取它们的父节点那才是答案。这个过程可以用一句不太好听但特别形象的话概括既不能跳到同一个祖先上也不能跳过头把答案丢了所以每次都试探着跳发现跳上去之后俩人的祖先还是不同的那就说明还没到位可以继续跳如果发现一样了就说明这一跳可能会跳过头不跳试试更小的步长。有点绕是吧我画个场景你就懂了。假设 a 和 b 站在一棵树的两个分支上它们的公共祖先是根节点下面的一个分叉点。我们让 a 和 b 同时往根的方向跳从 2^20 步开始试跳完发现俩人还在不同的分支上祖先不同那就放心跳继续试 2^19 步发现还是不同的分支再跳一直试到 2^1 步跳完发现俩人已经到了同一个分支点这时就不能再跳了。最后答案就是两人当前的父节点。int lca(int a, int b) { // 第一步把深度深的 a 往上调到和 b 同一深度 if (depth[a] depth[b]) swap(a, b); int diff depth[a] - depth[b]; for (int k 0; k LOG; k) { if (diff (1 k)) { a up[a][k]; } } // 如果跳完刚好重合那这个节点就是 LCA if (a b) return a; // 第二步一起向上跳跳到 LCA 的下一层 for (int k LOG - 1; k 0; k--) { if (up[a][k] ! up[b][k]) { a up[a][k]; b up[b][k]; } } return up[a][0]; }这段代码是标准的 LCA 倍增写法。有几个小点我提醒一下第一步用的是从小到大枚举 k因为要根据 diff 的二进制位决定跳不跳。你也可以写成从大到小判断以及判断if (depth[a] - (1k) depth[b])两种写法都对。第二步一定要从大到小枚举并且判断的是up[a][k] ! up[b][k]。这个条件和第一步的判断逻辑完全不同很多初学者第一次自己写都会在这上面栽跟头。LOG 层数要开够。如果树有 10^5 个节点那么 2^17 131072所以 LOG 取 18 就够。保守一点取 20甚至 25都不会错。但是不能开 40 还不注意内存因为 up 数组是 n × LOG 的大小节点数一多内存就上去了。3.4 LCA 预处理代码实例这里我给出一个完整可运行的 LCA 倍增代码建树采用邻接表根节点定为 1。#include bits/stdc.h using namespace std; const int N 100005; const int LOG 20; vectorint tree[N]; // 树的邻接表 int depth[N]; // 每个节点的深度根节点深度为 1 int up[N][LOG]; // up[u][k] 表示 u 向上走 2^k 步到达的节点 void dfs(int u, int parent) { depth[u] depth[parent] 1; up[u][0] parent; // 利用递推公式一次性算完 u 的所有 2^k 级祖先 for (int k 1; k LOG; k) { up[u][k] up[up[u][k - 1]][k - 1]; } for (int v : tree[u]) { if (v parent) continue; dfs(v, u); } } int main() { int n; scanf(%d, n); for (int i 0; i n - 1; i) { int u, v; scanf(%d %d, u, v); tree[u].push_back(v); tree[v].push_back(u); } // 从根节点 1 开始它的父节点设置为 0哨兵节点 // 这样 up[1][k] 最终都会是 0表示已经到了树的外面 dfs(1, 0); int q; scanf(%d, q); while (q--) { int a, b; scanf(%d %d, a, b); printf(%d\n, lca(a, b)); } return 0; }这里有一个容易忽略的细节我把根节点 1 的父节点设置成了 0。这样当节点已经到根了还要往上跳时up 数组的值就是 00 不会出现在树里所以不会干扰正常的祖先判断。这个“哨兵”用法在很多树形算法里都很常见。另外说一句递归深度的事。在竞赛环境中如果 n 到 10^5DFS 的默认栈空间可能不够。我习惯在 main 函数开头写这么一句ios::sync_with_stdio(false);顺便也可以用 BFS 来建 up 数组这样完全没有爆栈风险void bfs(int root) { queueint q; q.push(root); depth[root] 1; up[root][0] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int k 1; k LOG; k) { up[u][k] up[up[u][k - 1]][k - 1]; } for (int v : tree[u]) { if (v up[u][0]) continue; depth[v] depth[u] 1; up[v][0] u; q.push(v); } } }两者效果一样BFS 的一个额外优势是不会递归爆栈。如果你第一次写 LCA建议直接用 BFS 版本少踩一个坑。4. 常见问题与排查技巧实录写了这么多年代码每次教别人学倍增我发现他们踩过的坑就那么几个。我把它们汇总一下相当于一张速查表你以后遇到类似问题先对照着查一遍。4.1 数组维度开小了这个问题最常见尤其是 ST 表和 LCA 的 up 数组。ST 表要求第二维是 log2(n) 1。很多人只开个 17、18 就觉得够了结果 n 是 10^5 时也没问题但一旦 n 到 10^6 就直接越界。我的习惯是直接定义一个常量const int LOG 20; // 能覆盖 2^20 ≈ 1e6 的范围如果 n 是 10^5取 18 就够。但为了保险我通常取 20 或者 25。不过也不能无限大因为 up 数组是 n × LOG 的大小LOG 开太大内存会白白浪费。4.2 预处理循环顺序搞反ST 表预处理时第一层循环一定是 k区间长度层级第二层才是 i位置。这个顺序搞反了你得到的表就是半成品查询结果时对时错特别诡异。原因我在前面说过了长度为 2^k 的区间依赖的是长度为 2^(k-1) 的区间所以必须把短区间全部算完才能开始算长区间。如果你先枚举 i 再枚举 k那算出的 st[i][2] 可能用到的 st[i1][1] 还是垃圾值。LCA 的 up 数组也是一样在 dfs 里先算出 up[u][k-1] 再去算 up[u][k]顺序必须保证是从小到大。这个在递归函数里是天然成立的因为 up[u][1] 依赖的是 up[up[u][0]][0]而 up[u][0] 已经先算出来了。4.3 查询边界算错ST 表查询时的右区间左端点r - (1 k) 1是一个经典易错点。如果你不小心写成了r - (1 k)那查询结果就会缺少一个元素而且这种错误特别难用样例发现因为大多数时候你只差了一个数结果还是对的。我建议做题时先画一个小数组比如长度为 5 的区间 [2, 6]然后手动推一遍 k 和两侧区间的覆盖范围把这个过程走顺了再写代码。4.4 跳跃过头怎么处理LCA 的查询中第二步循环里很多人容易写成if (up[a][k] ! up[b][k]) { a up[a][k]; b up[b][k]; }注意这里判断的是 up[a][k] 和 up[b][k] 是否相等而不是 a 和 b 是否相等。如果你用后者判断那么当 a 和 b 已经处在不同子树但它们的某层祖先相同时你可能就不会跳了从而导致最后返回的父节点不对。最好的调试方法就是在本地写几个小规模数据手动画出树然后把 lca 的每一步打印出来对照。4.5 什么时候不适合倍增这一点我觉得比会写代码更重要。倍增不是万能的你要清楚它的适用范围ST 表适合静态数组的区间查询不能处理带修改的情况。有修改请用线段树。LCA 用倍增查询一次是 O(log n)如果 n 很大、查询又特别频繁那么可以进一步用欧拉序 RMQ 做到 O(1) 查询但实现复杂度更高。快速幂要求底数和指数固定代入不能处理动态变化的数据结构。一句话总结如果你发现一个问题允许离线预处理所有可能的“2 的幂次”信息并且查询时能拆成若干个等长区间拼接那大概率可以用倍增。5. 从零手写一次完整实现建议直接抄作业讲到这里我把三个经典应用的代码再整合一下方便你直接拿去本地跑。如果是第一次接触倍增我特别建议你把这三个代码都敲一遍敲完你再去看任何“二分答案 倍增验证”的题目都会觉得亲切很多。5.1 快速幂完整代码#include bits/stdc.h using namespace std; long long mod_pow(long long base, long long exp, long long mod) { long long result 1; base % mod; while (exp 0) { // 当前二进制位是 1才需要累乘 if (exp 1) result result * base % mod; // base 翻倍base^2, base^4, base^8 ... base base * base % mod; exp 1; } return result; } int main() { long long a 2, b 13, m 1000000007; printf(%lld^%lld mod %lld %lld\n, a, b, m, mod_pow(a, b, m)); return 0; }5.2 ST 表完整代码#include bits/stdc.h using namespace std; const int N 100005; const int LOG 20; int a[N]; int st[N][LOG]; int lg[N]; void build(int n) { for (int i 1; i n; i) st[i][0] a[i]; lg[1] 0; for (int i 2; i n; i) lg[i] lg[i 1] 1; for (int k 1; (1 k) n; k) { for (int i 1; i (1 k) - 1 n; i) { st[i][k] max(st[i][k - 1], st[i (1 (k - 1))][k - 1]); } } } int query(int l, int r) { int k lg[r - l 1]; return max(st[l][k], st[r - (1 k) 1][k]); }5.3 LCA 完整代码#include bits/stdc.h using namespace std; const int N 100005; const int LOG 20; vectorint tree[N]; int depth[N]; int up[N][LOG]; void dfs(int u, int parent) { depth[u] depth[parent] 1; up[u][0] parent; for (int k 1; k LOG; k) { up[u][k] up[up[u][k - 1]][k - 1]; } for (int v : tree[u]) { if (v parent) continue; dfs(v, u); } } int lca(int a, int b) { if (depth[a] depth[b]) swap(a, b); int diff depth[a] - depth[b]; for (int k 0; k LOG; k) { if (diff (1 k)) { a up[a][k]; } } if (a b) return a; for (int k LOG - 1; k 0; k--) { if (up[a][k] ! up[b][k]) { a up[a][k]; b up[b][k]; } } return up[a][0]; }这三份代码是可以直接跑通正确逻辑的骨架。你做题时根据题意稍作修改比如把求最大值改成求最小值、把向上统计祖先改成统计路径上的边权和就能用在具体题目里。我的几点实操体会最后说点我自己多年写算法题、带新人时攒下的经验。第一学倍增一定要亲手把 up 数组、st 数组打印出来看几遍。不要觉得这是浪费时间的傻办法。我当年第一次学 LCA就是写了个小程序打印出每层 up 数组的值然后对着树图画了一遍才彻底想明白那个递推公式到底是怎么转起来的。当你亲眼看到up[8][2] up[up[8][1]][1]输出结果和手算一致时这个知识点就再也忘不掉了。第二写倍增代码的时候先把“跳步”的核心循环用注释写出来再填代码。比如 LCA 的第一步循环注释写“根据 diff 二进制决定跳到哪个祖先”第二步写“尝试从大到小跳到 LCA 下方”。这样做的好处是你不容易在两个长得差不多的循环之间迷失方向。第三不要急着背模板。我给你一个训练建议先不看任何参考代码自己从 up 数组的定义出发写一版 LCA 的预处理和查询。如果写不出来再回头看我给的代码如果写出来了但感觉不对就逐行对照。这个过程比你背十遍模板都管用。我在带人的时候发现凡是能自己独立推导出这段代码的人后面学树上差分、启发式合并这些进阶内容都特别快因为他们已经真正理解了倍增的本质。倍增算法说来说去核心就那么一句话预处理出所有 2 的幂次步长的信息查询时用二进制拼出需要的步数。不管它套在快速幂、ST 表还是 LCA 上骨子里的思想都是一样的。把这个思想吃透了以后遇到任何“跳步”相关的问题你都会有第一个思路。