★ FEATURED ARTICLE 省赛考场上我盯着那道“树上路径覆盖统计”看了三分钟脑子里只有暴力枚举的思路回头瞥到旁边一位选手已经在草稿纸上画了两棵树的递推关系。那次之后我得出一个结论蓝桥杯拉开差距的往往不是会多少个冷门算法而是能不能在第一时间认出“这题该用哪个基础工具”。而在基础工具里倍增和离散化又是最容易被低估的两个。它们经常在同一个题里出现一个负责把单次操作的代价从 O(N) 压到 O(log N)一个负责把数据范围从 10^9 压缩到 N让数组和树状数组派上用场。这篇文章就把两个思想彻底拆开从原理、代码到踩坑一次讲透。1. 为什么“倍增”不是跳棋而是二进制拆分的提款机很多同学学倍增第一个接触的是快速幂于是误以为倍增就是“每次乘以2不断翻倍”。这个理解方向是对的但它掩盖了一个关键点倍增的核心不是“翻倍”本身而是把一条单步路径按 2 的幂切碎达到一眼就能跳到远处的效果。想象一下你要从地面爬到第 n 级台阶一次只能跨一格那复杂度是 O(n)。现在给你若干张“跳板”能让你一次跨 2 格、4 格、8 格……你并不会真的每次都跳最大格而是先看 n 的二进制表示里哪些位是 1。二进制从低位往高位看第 i 位是 1就跳一次 2^i 格。这样一来最多跳 log n 次就到位了这就是“二进制拆分 预计算跳板”的组合。那为什么一定是 2 的幂而不是 3 的幂、10 的幂因为任何一个正整数都能且只能用二进制表示用十进制幂做不到“任意步数都能凑出来”。同样跳板指数要是 3 或 10就会出现某些距离凑不出来的尴尬情况。这一点理解了倍增的整个框架就立住了。在蓝桥杯级别的算法题里有三个最常见“倍增落点”场景要解决的事典型的单步操作快速幂算 a^n mod p乘法RMQ区间最值查询一段区间的最小/最大值相邻两段合并LCA最近公共祖先树上两点的最近公共祖先节点向上跳一层这三个场景代码长相完全不同但骨架高度一致预处理一个二维转移数组查询时用二进制从大到小试探。2. 倍增的第一个战场快速幂如何帮你建立二进制直觉快速幂的代码几乎人人会写但很少有人停下来想它和倍增的深层关系。原理极其简洁要算 a^n不把 n 个 a 连乘而是看 n 的二进制。n 13 1101_2 8 4 1那么a^13 a^8 * a^4 * a^1所以我们只需要自底向上算出a^1、a^2、a^4、a^8这就是“预计算跳板”。具体代码如下long long quickPow(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; }这个循环里做了两件事一是n 1让 n 的二进制位逐位暴露出来二是每轮把 a 自乘一次相当于从 a^1 得到 a^2、从 a^2 得到 a^4。只有当二进制位为 1 时才把当前的 a 乘进答案。我在实际做题时很少单独用快速幂但它带来的二进制直觉是后面理解 LCA 和离散化排序逻辑的“发动机”。如果你现在看到if (n 1)还没有那种“这一位该跳就跳”的肌肉记忆建议先把快速幂在自己本子上推演 5 组不同 n 的取值这一步省不了。3. 倍增的第二战场RMQ 与 ST 表的合并查询思路竞赛里做区间最小值查询最容易想到的是线段树但静态数组的 RMQ 用 ST 表会快一个常数级写法上也更像“倍增的样子”。ST 表的思路很简单预处理出所有长度为 2 的幂的区间最值然后用两个可重叠的子区间覆盖整个查询区间。举一个具体的例子。设一个数组a [3, 1, 4, 1, 5, 9, 2, 6]定义st[i][j]表示从下标 i 开始、长度为 2^j 的区间最小值。先有st[i][0] a[i]转移方程一眼就能看出“合并”的影子st[i][j] min(st[i][j-1], st[i 2^(j-1)][j-1])比如要查询区间 [2, 7] 的最小值区间长度为 6它的二进制是 110理论上可以把它拆成长度 4 和长度 2 的两段但这会产生两次查询合并。ST 表真正常用的技巧是重叠查询令k floor(log2(区间长度))然后对比st[L][k]和st[R - 2^k 1][k]这两个区间可能重叠但最小值不受影响。int query(int l, int r) { int k lg[r - l 1]; return min(st[l][k], st[r - (1 k) 1][k]); }这里lg数组是为了 O(1) 拿 log2 值而预处理的推导方式很朴素lg[1] 0;之后对i 2lg[i] lg[i/2] 1。可能有人会问重叠不会多算吗对于最值类的幂等运算答案是“不会”。min(一堆数)重复取两次不影响结果这也是 ST 表只适用于最值或 gcd 这类可重叠贡献的运算的原因。换成区间和就不行区间和运算不幂等两段重叠会把中间部分加两次。在实际比赛中静态查询区间最值的题ST 表的代码量比线段树少太多尤其在蓝桥杯这种时间紧张的比赛里能省几分钟都是实打实的。但要记住ST 表不支持修改需要修改就老实上线段树。4. 倍增的主战场LCA 的树上前进与二进制试探讲完了热身项终于说到 LCA。树上最经典的问题是给定一棵树多次询问两个节点的最近公共祖先。暴力做法是先把较深的节点往上提到和另一个节点同一深度然后两个节点同时往上爬。但每次只爬一层遇到深度很大、询问很多的题目就直接超时。这里的优化思路就是把“每次爬一层”升级成“每次爬 2^j 层”。先预处理出每个节点的第 2^j 层祖先记为up[u][j]。这个数组的意义是up[u][0]是 u 的父节点up[u][1]是 u 的祖父节点up[u][2]是往上数 4 层的祖先节点以此类推。递归关系用一句话就能说明白往上跳 2^j 层等于先往上跳 2^(j-1) 层再跳 2^(j-1) 层。也就是说up[u][j] up[up[u][j-1]][j-1]这其实就是第一个转移式的树形版本。有了这个递推关系预处理只需一次 DFS代码也很短const int LOG 20; vectorint g[N]; int up[N][LOG], depth[N]; void dfs(int u, int father) { up[u][0] father; depth[u] depth[father] 1; for (int j 1; j LOG; j) { up[u][j] up[up[u][j-1]][j-1]; } for (int v : g[u]) { if (v ! father) dfs(v, u); } } int lca(int a, int b) { if (depth[a] depth[b]) swap(a, b); // 先把 a 提到与 b 同一深度 int diff depth[a] - depth[b]; for (int j LOG - 1; j 0; j--) { if ((diff j) 1) a up[a][j]; } if (a b) return a; // 两个节点一起往上跳但最终跳到 LCA 的下一层 for (int j LOG - 1; j 0; j--) { if (up[a][j] ! up[b][j]) { a up[a][j]; b up[b][j]; } } return up[a][0]; }这段代码里有两点值得专门说道。第一段for循环判断条件(diff j) 1用的是二进制试探法diff 的二进制哪一位是 1就说明需要跳对应的 2^j 层。这一段的目的只是让两个节点深度对齐所以直接跳就行。第二段for循环要理解“为什么条件是up[a][j] ! up[b][j]而不是up[a][j] up[b][j]”——如果是后者容易直接跳到 LCA 本身或甚至跳过 LCA。而这里我们刻意让两个节点停在 LCA 的下一层即它们往上跳一步才能汇合的那个位置这样最后返回up[a][0]才是真正的 LCA答案永远是唯一且正确的。刚开始学这个算法的人几乎都会在这个判断条件上栽一次跟头我第一次自己尝试用“相等就返回”的策略时遇到两点为祖孙关系的情况就出问题所以要特别记一下这个设计。关于 LOG 的取值一般取ceil(log2(N)) 1。比如 N 最大 10^52 的 17 次方是 131072那 LOG 取 17 就够了实际代码里为了稳妥我经常直接开 20如果 N 上限是 10^6则需要开到 24 左右。这个细节在比赛中很致命开小了悬空访问越界开大了又浪费一点内存但相比越界崩溃浪费一点完全可接受。5. 离散化精讲把 10^9 的值域装进下标为 N 的数组倍增讲完来说离散化。这个名字很唬人其实做的事情非常朴素把大范围的零散数值映射成连续的小整数 1 到 M保持数值之间的相对大小关系不变。举个例子给你一组坐标[-10^9, 0, 10^9, 3, 7, -100]你要统计每个坐标的出现次数开数组的话得开多大不可能为每个可能值开一个数组元素那就把这一组出现过的值排序、去重然后按顺序重新编号-10^9 - 1, -100 - 2, 0 - 3, 3 - 4, 7 - 5, 10^9 - 6。这样做完原来的每个值都能对应到一个不超过 N 的小整数桶数组就放得下了。标准离散化流程分三步把所有要离散化的值收集进一个 vector。对这个 vector 排序并去重。对于每个原始值用二分查找计算它在 vector 中是第几个作为它的新编号。vectorint v; for (int i 1; i n; i) { cin a[i]; v.push_back(a[i]); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (int i 1; i n; i) { a[i] lower_bound(v.begin(), v.end(), a[i]) - v.begin() 1; }注意几个细节。第一lower_bound返回的是从 0 开始的下标我习惯加 1 变成从 1 开始的编号方便后面配合树状数组或前缀和不用预留 0 号位。第二unique用于去重它会把重复元素移到容器末尾并返回去重后的新尾部迭代器后面的erase就是删掉多余的部分。第三离散化后判断两个原始值哪个大只需要比较它们的映射编号偏序关系完全保留。那离散化到底有什么用它最大的价值是把“值域问题”变成“下标问题”。树状数组要求下标必须是 1 到 M 范围内的整数线段树要按区间划分值域很大的情况下这些数据结构全都派不上用场离散化之后M 最大不过 N任何人都能用普通数组搞定。代价是什么离线。你必须在读入所有数据之后才能做离散化一旦中途有新数值进来旧的映射关系就要怎么处理通常的做法是全部收集完再统一处理。所以离散化天生适合“离线一次性处理”的应用场景。蓝桥杯里比较常见的离散化题目长这样给一个数轴上若干条线段的端点每个端点最大 10^9求有多少个“孤立的单位区间”被至少一条线段覆盖。经典的思路是把所有端点离散化后在映射后的区间上做差分差分数组的长度最多是 2N完全可控。这类题你一眼就能认出“端点范围巨大但数量有限”的特征这正是离散化的召唤信号。6. 组合技实战一道题同时用上倍增与离散化现在把两个思想放到同一个案例里这是这篇文章价值最高的部分。我选一个经典但不过分复杂的问题类似于省赛中的压轴题变体给一棵 N 个节点的树以及 M 条树上路径每条路径由起点 u 和终点 v 给定。有 Q 次询问每次询问给出一个节点 x求有多少条路径覆盖了 x。先拆解这道题。它需要求 LCA因为路径信息要用 LCA 来差分也需要按节点编号或某种坐标顺序做统计如果节点编号范围很大、或者有很多额外坐标那又得离散化。这里我们假设节点编号已经是 1..N不需要离散化真正要离散化的是“值域”维度。但为了演示组合我在下面的步骤里把“按路径数据差分后生成每个节点的覆盖次数”这一步用桶实现并在另一个变体中说明如何用离散化处理坐标型的版本。先处理 LCA 部分DFS 预处理up[u][j]和depth[u]。对每条路径 (u, v)先计算l lca(u, v)。用树上差分数组cnt记录cnt[u] 1; cnt[v] 1; cnt[l] - 1如果 l 不是根再cnt[parent[l]] - 1。从叶子向上做一遍 DFS 后序遍历把每个子节点的cnt累加到父节点上。累加结束后cnt[x]就是覆盖节点 x 的路径条数。这里树上差分的原理是路径 (u, v) 可以被拆成从 u 到 LCA 和从 v 到 LCA 两段。cnt[u]和cnt[v]分别代表这两段向上“开启”两段在到达 LCA 后汇合所以cnt[l] - 1消除重复计数再cnt[parent[l]] - 1让计数在 LCA 的父节点处结束不会继续向上蔓延到整棵树的祖先。第二步里的 LCA 就是倍增上场的地方。每次查询一个路径的 LCA代价从暴力 O(N) 降到了 O(log N)M 条路径总共 O(M log N)这个复杂度在 N10^5、M10^5 的数据下完全没问题。那离散化在哪假设题目把“节点”换成了“平面上 N 条线段”每次询问给一个点坐标求它被多少线段覆盖。这时坐标范围可能是x, y 10^9你就必须对所有端点坐标做二维离散化映射成小整数后再用二维差分或扫描线。整个过程唯一区别是桶下标从“节点编号”变成了“离散化后的坐标编号”代码上几乎只多了一部分排序二分。为了让这套思路更清楚我写上单棵树版本的核心代码void dfs_calc(int u, int father) { for (int v : g[u]) { if (v father) continue; dfs_calc(v, u); cnt[u] cnt[v]; } }查完累加结果对每个询问直接输出cnt[x]即可。整体复杂度步骤复杂度DFS 预处理倍增表O(N log N)每条路径求 LCA 并做差分O(M log N)后序遍历累加差分数组O(N)处理每个询问O(1)比暴力的“每条路径都往上走一遍标记节点”的 O(MN) 要好一个量级在实际评测中跑 10^5 的数据轻松通过。7. 复盘蓝桥杯实战里最容易翻车的几个细节算法思路讲了代码也贴了最后必须来点比赛里被反复折磨过的坑。这些细节看起来小错了就是整道题爆零而且样例往往还测不出来。第一个坑是倍增表的 LOG 开太小。很多人看到 N10^5取 LOG17单看 2^17 131072 覆盖 10^5 好像没问题但代码里如果要从深度差上升到祖先实际还可能出现“UNEQUAL 时两个节点跳到 LCA 下一层”的操作需要访问到up[a][LOG-1]级别的数据。换句话说开LOG1层最稳妥。比赛里数组开大 1 倍不扣分但访问越界可能直接异常退出所以我个人习惯在原有估算基础上至少再加 1 到 2 层。第二个坑是离散化时忘掉去重导致映射编号不是连续的后面开数组时按完整 N 开了但查lower_bound返回的下标跳了好几位某些编号永远不会被命中统计结果错得毫无规律。排完序之后的unique那行一定要配合erase删干净不能偷懒。第三个坑是差分路径时忽略“LCA 不是根”的判断。如果某条路径的 LCA 恰好是根节点那么parent[l]不存在代码里再cnt[parent[l]] - 1就访问到非法内存。正确的做法是只在 LCA 不是根时才减最后一个值。第四个坑是二分映射lower_bound之后忘记加 1。从 0 开始的下标在树状数组等结构里是有隐患的需要预留 1 号位我建议统一加 1从 1 开始编号。如果想偷懒不加就必须保证树状数组的 update 函数里i从idx1开始两个地方容易不一致建议直接把“加 1 变成 1-based”作为一种默认规则。最后还有一个心里层面的问题比赛里时间分配上如果一道题需要离散化和 LCA 同时用我建议先写离散化再写树上预处理因为离散化一旦写完整个程序的容器结构就定下来了调试时只需要盯着 LCA 和差分部分。反过来先写了 LCA 再去补离散化很容易被“是映射前还是映射后”的混乱逻辑搞到怀疑人生。8. 除了刷题这两个思想还能给你带来什么很多人刷算法题目标是“记住这个题型的模板”但我更愿意把倍增和离散化看成一种思维工具它们能让你在拿到一道新题时更快地做出“结构判断”。看到“多次询问第 k 级祖先”“静态区间最值”“路径覆盖统计”这类有“往上/往右/往前跳跃”特征的问题第一反应应该有“倍增”这个词。看到“值域很大但数量很小”“需要离线统一处理坐标”这类描述第一反应就该是“离散化”。这两个反应如果变成肌肉记忆比赛时就不用靠灵感碰运气了。以我的经验蓝桥杯国赛级别的题很少直接考一个孤立的算法基本都是把两三个思想嵌套在一起。倍增解决时间维度上的跳跃离散化解决空间维度上的压缩两者组合起来无论是大范围值域上的树状数组方案还是树结构上的路径统计都能用一套模式快速拿下。复习建议也很直接把快速幂、ST 表、LCA 三个模板手写熟至少不出错离散化流程用同一个 paste 模板练到不用动脑最后找五六道同时包含“大量查询大值域”的旧题从暴力开始优化体会“哪些复杂度是被倍增拉下来的哪些内存是被离散化省出来的”。这套练完你会对我开头那句话有更深的认同——蓝桥杯拼的从来不是会不会多少个偏门算法而是你能不能把最基础的工具组合出最大的威力。
阅读完成 · 觉得有帮助？
