蓝桥杯每年一到备赛季论坛里问得最多的就是“怎么从暴力优化到能过数据范围”“有没有一些套路是见题就能用的”。说实话算法竞赛里真正高频率出现、又容易被新手忽略的技巧倍增思想和离散化绝对排得上号。前者能把一些O(n)甚至O(n log n)的查询压到O(log n)后者能把稀疏的数值范围压缩成连续的数组下标两者单独用已经很能打组合起来更是很多蓝桥杯中等偏上题目的标准解法。这篇内容是我自己带赛和刷题过程中的一份深度笔记覆盖两大思想的核心原理、代码模板、经典变体和蓝桥杯题向分析适合正在备赛蓝桥杯的同学也适合刚接触算法竞赛、想建立解题工具箱的开发者。我会把每一步为什么这么做、边界在哪、坑在哪都讲透争取你看完能直接上手用而不是只记住几个术语。1. 快速热身两个思想到底解决什么问题1.1 倍增思想的直觉来源与核心模型倍增思想最早的直觉来源其实特别朴素你从一个点出发想知道往前走很远之后的状态如果一步一步走太慢那就一次性走两步、四步、八步通过预处理“跳表”来加速。在算法里这个“跳表”通常是一个二维数组比如up[node][k]表示从某个节点出发走 (2^k) 步之后到达的位置。只要能预处理出这个表任何“走任意步数”的查询都可以用二进制拆分的方式在 O(log n) 时间内完成。整个过程就是把目标步数换成二进制哪些位是 1就对应跳那几段。举个例子你想让一个指针一次走 13 步。13 的二进制是 1101也就是 8 4 1那么你先跳 1 步再跳 4 步再跳 8 步顺序无所谓反过来也行三步搞定而不是傻傻走 13 次。这是一个用“幂次预处理 二进制状态组合”换取查询速度的经典套路。为什么不叫“二分思想”因为二分强调的是“每次砍半”而倍增强调的是“从 1 到 2 到 4 到 8 翻倍增长”。倍增算法里经常配合二分使用比如“先倍增找到可行区间再二分精确收窄”但倍增本身是一种跳跃结构和二分是两码事。1.2 离散化的本质把“数值大小”变为“相对排名”离散化处理的痛点则是另一种有时候数据本身的值域很大比如 1 到 (10^9)但实际出现的不同数字只有 (10^5) 个。如果这时候你想用数组下标直接存储、统计、DP数组根本开不了那么大但你其实也不需要那么大你只需要一个“排名数组”。离散化的本质是一句话把数值映射成它在有序集合中的排名。比如原始数据是 [1000, 2, 200, 2]排序去重之后是 [2, 100, 200, 1000]那么每个数的排名就是 1、4、3、1。这个排名天然就是连续的整数 1 到 m正好可以作为数组下标或者树状数组的索引。这种“压缩值域”的操作在蓝桥杯里极其常见尤其是那些看似值域很大、但实际只用“相对大小关系”的题目。很多同学一看到 (10^9) 就发怵但其实离散化正是处理这种“数值无关紧要顺序才重要”场景的钥匙。2. 倍增思想的内功心法从快速幂到树上跳表2.1 快速幂倍增思想的最小完整单元要理解倍增最经典的入门案例就是快速幂。计算 (a^b \mod p)如果 for 循环老老实实乘 b 次b 一旦到 (10^9) 级别就完蛋。利用倍增你可以把指数 b 拆成二进制每一位代表是否需要乘上当前累积的幂次。为什么这个技巧有效因为每一步我们把底数平方相当于把指数翻倍从 (a^1) 到 (a^2) 到 (a^4)只需要 log b 次平方操作。这种“平方代替连乘”的思路是所有倍增算法的源头树上的倍增跳表本质上也是这个思路的结构化升级版。long long quick_pow(long long a, long long b, long long p) { long long res 1 % p; while (b) { if (b 1) res res * a % p; a a * a % p; b 1; } return res; }这段代码建议背到肌肉记忆级别。不只是因为蓝桥杯偶尔直接考快速幂更因为它能帮你在思维上建立“二进制拆步”的直觉。每次看到一个“跳若干步”的查询都应该下意识问自己能用二进制拆吗2.2 最近公共祖先LCA的倍增跳表LCA 是倍增思想在树上最典型的应用。求两个节点的最近公共祖先朴素做法是一个一个往上走最坏情况是一条链O(n) 查询一次。倍增做法是先把所有节点向上跳 (2^k) 步的祖先预处理出来然后查询时先把较深的节点“抬”到和另一个节点同一深度再一起往上跳直到它们的父节点相同。这里面有个关键细节往上跳的时候要从最大的步长开始试。为什么因为如果你从小的步长开始凑可能需要凑很多次达不到“log 次完成”的目标而二进制拆分本身就是从高位往低位看的所以循环里 k 从大到小。预处理时的递推公式也很重要up[j][i] up[j - 1][up[j - 1][i]]意思是节点 i 往上跳 (2^j) 步等于先跳 (2^{j-1}) 步到达中间节点再从这个中间节点继续跳 (2^{j-1}) 步。这里要求 up 表的第二维先从小到大计算保证中间节点已经算好。很多同学写错 LCA 就是因为这个递推的先后顺序搞反了。2.3 倍增的其他经典变体ST 表、快慢指针、区间覆盖除了树上跳表倍增还有一堆变体每个都值得在蓝桥杯备赛时练一遍ST 表Sparse Table用来处理静态数组的区间最值查询。预处理每个位置往后 (2^k) 长度的区间最值查询时用两个重叠区间取最值O(1) 回答 RMQ。ST 表不能用于区间求和因为 sum 没法用重叠区间直接合并会重复计算但 max/min 可以。快慢指针Floyd 判圈这算是倍增的“思想近亲”——一个指针每次走 1 步另一个每次走 2 步如果链表有环两个指针必然相遇。它不涉及二进制拆分但同样利用了“2 倍速追赶”的核心直觉。区间覆盖的最小段数给定若干线段覆盖大区间用倍增预处理从每个位置出发选择一条能延伸最远的线段后到达的位置查询时同样二进制跳跃。我个人的建议是LCA 和 ST 表在蓝桥杯中考查频率较高快慢指针偶尔出现在填空题或简单大题中区间覆盖则更多作为综合题的一个环节。准备顺序上先吃透 LCA 和 ST 表就足够了其他技巧遇到题再补不用一上来全学。3. 离散化的三步法排序、去重、二分映射3.1 基本操作一行代码搞定的背后逻辑离散化主流写法就三步排序、去重、用二分查找确定排名。C 里直接用 vector 配合 sort、unique、erase 和 lower_bound 四件套Python 里也可以模拟这个操作。vectorint nums {1000, 2, 200, 2}; sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end()); // 之后对每个原数值 x用 lower_bound(nums.begin(), nums.end(), x) - nums.begin() 1 得到排名从1开始这里去重用的是 unique 和 erase 的组合。unique 的作用是把相邻重复元素移到容器末尾并返回新的逻辑结尾迭代器erase 再把末尾的重复段删掉。注意 unique 只对“相邻”重复生效所以必须先 sort不能反过来。有一个常见误解是离散化后值一定从 1 开始。其实从 0 还是从 1 开始取决于你后面用它做什么。如果作为树状数组的下标我建议从 1 开始因为树状数组的 update 和 query 通常都是 1-indexed如果只是做 DP 的状态压缩从 0 开始则更方便跟数组下标对齐。3.2 离散化的本质是“只关心相对大小”什么时候需要离散化判断标准很简单题目里的数值大小本身不重要重要的是它们之间的“大小顺序”或者“相等关系”。最常见的信号是值域范围超大(10^9) 甚至更大但实际输入只有 (10^5) 个不同值题目要求对数值进行排名、按大小统计、区间覆盖、逆序对等操作需要把值映射成数组下标或树状数组索引举个例子求数组的逆序对数量。朴素做法是双层循环比较O(n^2)。用树状数组加速时你要把每个数值当成下标来统计“比它小的数有几个”但如果数值范围是 (10^9)树状数组根本开不了那么大。离散化之后值域缩到 n树状数组就能正常工作了。“只关心相对大小”这一点听起来有点抽象实践中可以这样判断如果把所有输入数值同时放大一万倍题目答案仍然不变那这个题本质上只需要相对顺序离散化一定适用。3.3 常见退化场景与注意事项离散化虽然写起来就几行但有几个细节坑我几乎每次讲都会强调去重前必须排序。有些人喜欢用 set 去重但 set 自带排序其实等价于 sort unique不过在处理重复元素映射时还是要小心 lower_bound 返回的第一个位置确保相等元素映射到同一个排名。如果题目要求保留原始重复信息比如统计每种数字出现了多少次那么离散化时要用“值到排名”的映射表而不是直接把原数组改成排名否则重复信息就丢了。离散化的复杂度是 O(n log n)瓶颈在排序和每次 lower_bound 的二分查询。如果对每个数都调用一次 lower_bound总复杂度就是 O(n log n)。这在 (10^5) 到 (10^6) 级别完全没问题但如果你对同一个数组做大量离散化查询可以考虑提前把映射关系存到 unordered_map 里把单次查询变成 O(1)。4. 组合实战逆序对 最小覆盖区间两个完整案例4.1 离散化 树状数组解决逆序对问题逆序对题大概是“离散化树状数组”的黄金搭档组合蓝桥杯省赛和国赛都出现过类似思路的题。完整做法分三步。第一步读入原始数组 a复制一份到 b对 b 排序去重得到离散化映射数组。第二步初始化一个长度为 n 的树状数组 bit全部为 0。第三步从右往左遍历原数组每次先查询当前值排名之前的累加和计入答案然后更新当前排名位置加 1。long long count_inversions(vectorint a) { vectorint b a; sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); BIT bit(b.size() 2); long long ans 0; for (int i a.size() - 1; i 0; --i) { int rank lower_bound(b.begin(), b.end(), a[i]) - b.begin() 1; ans bit.query(rank - 1); bit.update(rank, 1); } return ans; }为什么要从右往左遍历因为逆序对的定义是 i j 且 a[i] a[j]从右往左时已经遍历过的位置相当于“右侧元素”此时查询“小于当前值”的右侧元素个数恰好就是当前元素与右侧形成的逆序对数。如果你习惯从左往右也可以查询大于当前值的左侧元素个数只是树状数组变成后缀查询不太直观。4.2 倍增 二分求解区间覆盖问题另一道经典题是给定一个目标区间 [L, R] 和若干可选子区间最少选几个子区间才能完全覆盖 [L, R]如果不做预处理每次贪心扫描都需要 O(n)查询一多就爆炸。预处理所有区间后用倍增把查询压到 O(log n)。具体做法是先用左端点排序所有子区间然后对于每个位置 i预处理 jump[i][j] 表示从位置 i 出发选择 2^j 个子区间后能覆盖到的最远右端点。转移公式是jump[i][j] jump[jump[i][j-1]][j-1]本质上和 LCA 的 up 表完全同款。查询时从 L 出发尝试从最大的 k 往下跳只要跳跃后没有超过 R就累加段数并跳到新位置最后如果当前覆盖边界已经小于 R就再选一段补上。核心逻辑是先用大步试探再用小步逼近和二进制拆分的套路严丝合缝。这个组合案例特别适合用来练习“预处理 查询”的思考方式先想清楚暴力怎么做再看看哪些状态可以提前算好、怎么跳最快然后自然就会用到倍增。蓝桥杯的很多压轴题本质上就是让你在“预处理上花功夫把查询压到 log 级别”。4.3 两个思想结合的通用套路总结当你看到一道题同时涉及“值域很大”和“需要反复跳跃”时大概率就是离散化 倍增的组合拳。一个典型的思维链路是先离散化把稀疏数值变成连续下标再在连续下标上建 ST 表或者树状数组最后用倍增跳表回答查询。这种组合棋路其实很顺手离散化解决的“空间”问题倍增解决的“时间”问题。很多同学喜欢背模板但我觉得更重要的是掌握这条“先压值域、再压时间”的思考路径——你遇到新题时按这个顺序试命中率很高。5. 蓝桥杯场景下的题目特征、复杂度评估与调试心得5.1 如何一眼识别题目的“倍增/离散化信号”大家最关心的肯定还是考场上怎么知道这题要用这两个技巧我的判断标准一般有三个题目里有“区间查询”“跳 k 步”“祖先节点”“最少覆盖”等字样而且数据范围在 (10^5) 以上O(n^2) 必然超时——考虑倍增。输入数值范围远大于 n比如 (10^9)但题目只讨论大小关系和相等关系——考虑离散化。题目要求在线回答多个查询且每个查询本身还嵌套其他数据结构操作——大概率是预处理 倍增/离散化作为前置步骤。举个例子一道题说“给一棵 n 个节点的树q 次询问 u 向上跳 k 步到达哪个节点”n、q、k 都在 (10^5) 级别。这题一眼就是倍增 LCA 的同款模板只不过不用查 LCA只需要跳 k 步。如果你只背了 LCA没理解跳表的本质遇到这种题可能还要绕远路。反过来有些题看数据范围就知道不能用倍增如果 n 很小比如 n ≤ 100直接暴力反而更简单没有必要为了“显得高级”硬上算法。竞赛的第一个原则永远是“复杂度够用就行”不要为了炫技增加代码复杂度。5.2 复杂度计算从暴力到优化数字怎么算出来的先看暴力做法如果每次查询都从某个点一步一步走到目标位置最坏走 n 步q 次查询就是 O(nq)。当 n 和 q 都是 (10^5) 时直接是 (10^{10})在现代计算机上无论如何跑不完。倍增做法的复杂度分预处理和查询两块预处理 up 表需要 O(n log n)每个节点都要往 log n 个方向跳单次查询需要 O(log n)总共 q 次查询就是 O(q log n)。总复杂度是 O((n q) log n)n 为 (10^5) 时约 (1.7 \times 10^6) 次操作真实运行时间在毫秒级别完全能过。离散化的复杂度在排序阶段是 O(n log n)之后不管你是做树状数组还是线段树复杂度都由后续的数据结构决定。比如逆序对的完整复杂度就是 O(n log n)因为树状数组的单次 update/query 都是 O(log n)。需要注意的是复杂度计算不能只看主体循环还要把 lower_bound 的 O(log n)、树状数组的 O(log n) 都算进去。很多人觉得“我用了倍增/离散化复杂度肯定是 O(n log n)”但如果你每次查询都调用一次 lower_bound 而没有提前缓存映射实际上复杂度变成了 O(q log n)加上预处理也可能叠加成 O((n q) log n)这通常是没问题的但如果一个题还有额外的 log 因子累积就要警惕常数过大。5.3 现场避坑经验边界条件、数组维度和取整陷阱我几乎每场模拟赛都会看到同学栽在同样的几个坑上这里一起列给你们倍增数组的维度一定是 LOG1其中 LOG 约等于 log2(n) 1。如果你开小了跳着跳着就越界程序不会立刻崩但答案会莫名其妙错。建议直接开 20n ≤ (10^6) 够用或者 30省得每次算。树上的 up 表根节点往上跳要指向 0 或者自身否则处理边界时会出现死循环。我一般约定根节点的 up 值设为 0而不是自身然后用 depth 来辅助判断何时停止跳跃。离散化时 lower_bound 的返回值是迭代器从 0 开始计数。如果你需要从 1 开始比如树状数组记得 1。这是最经典的 off-by-one 错误没有之一。用 ST 表做区间最值查询时区间长度 len 取对数要向下取整查询时用两端各覆盖 (2^k) 长度的区间重叠没关系但 k 不能超过区间实际长度否则会读到未定义范围。6. 核心模板速查可直接搬进代码库的两组实现6.1 倍增模板LCA 和 ST 表的标准实现LCA 的模板我一般这样写const int LOG 20; vectorint up[LOG]; vectorint depth; void dfs(int u, int p) { up[0][u] p; for (int j 1; j LOG; j) up[j][u] up[j - 1][up[j - 1][u]]; for (int v : g[u]) if (v ! p) { depth[v] depth[u] 1; dfs(v, u); } } 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[j][u]; if (u v) return u; for (int j LOG - 1; j 0; --j) if (up[j][u] ! up[j][v]) { u up[j][u]; v up[j][v]; } return up[0][u]; }这里有个细节在把 u 抬升到和 v 同深度时我们是从低到高遍历二进制位的而在最后一步一起往上跳时是从高到低遍历。这两个方向不能搞混。前者是“凑步数”后者是“找第一个不同的祖先之后的位置”。ST 表模板则更短vectorvectorint st; void build(vectorint a) { int n a.size(); int LOG log2(n) 1; st.assign(LOG, vectorint(n)); st[0] a; for (int j 1; j LOG; j) for (int i 0; i (1 j) n; i) st[j][i] max(st[j - 1][i], st[j - 1][i (1 (j - 1))]); } int query(int l, int r) { int len r - l 1; int k log2(len); return max(st[k][l], st[k][r - (1 k) 1]); }很多讲解喜欢说 ST 表的核心是“重叠不冲突”因为 max/min 操作对重叠不敏感这点务必牢记。一旦你想用 ST 表处理 sum 就废了因为重叠区域会被重复累加。6.2 离散化模板两种常用版本标准版本已经在上文出现过我这里再给一个“保留原数组、额外存映射”的版本适合统计类题目vectorint a ...; vectorint sorted_a a; sort(sorted_a.begin(), sorted_a.end()); sorted_a.erase(unique(sorted_a.begin(), sorted_a.end()), sorted_a.end()); unordered_mapint, int rank_map; for (int i 0; i sorted_a.size(); i) rank_map[sorted_a[i]] i 1; // 从1开始 vectorint ranked_a(a.size()); for (int i 0; i a.size(); i) ranked_a[i] rank_map[a[i]];用 unordered_map 的好处是之后不需要每次 lower_bound O(log n) 查排名查询变 O(1)。代价是哈希表常数大n 小于 (10^5) 时其实和 lower_bound 半斤八两但 n 到 (10^6) 时 unordered_map 的内存和哈希碰撞开销会显现。我建议在统计类题目中如果查询次数非常多才用映射表如果只是一次性建立索引直接 lower_bound 更稳。Python 版更简洁from bisect import bisect_left def discretize(arr): sorted_vals sorted(set(arr)) return [bisect_left(sorted_vals, x) 1 for x in arr]Python 的 set 自动去重sorted 之后天然有序bisect_left 就是 lower_bound 的等价物。注意这里的 1 是否要加取决于你的后续数据结构索引约定。用 Python 写树状数组的同学建议从 1 开始方便处理 0 号哨兵位。7. 系统刷题路径与备赛节奏建议7.1 从模板到应用的“三遍刷题法”我不太建议把模板背下来就直接上考场。模板只是“内功”真正的能力在于看到题能识别出该用哪一招。我自己的刷题节奏是每题至少过三遍。第一遍自己写哪怕写得很啰嗦、复杂度不过也要先把暴力思路跑通。第二遍看题解对比别人的倍增/离散化做法找出自己卡住的原因。第三遍合上题解从头到尾手写一次优化版本并且换一组数据自测。这三遍看起来费时间但效果很扎实。第一遍让你理解题意本身第二遍让你学到新套路第三遍把套路变成自己的手感。如果只是“看看题解觉得懂了”一周之后大概率忘光白刷。7.2 蓝桥杯不同组别的策略侧重蓝桥杯省赛和国赛的难度差异体现在题量和数据范围上但核心技巧的分布还是有规律可循。程序设计赛道C/C、Java、Python的省赛离散化作为前置步骤出现较多尤其是与树状数组、线段树结合的题倍增更多出现在中等偏后的位置比如 LCA、ST 表直接作为某一问的考点。到了国赛题目往往把倍增和离散化作为“入场券”而不是压轴。什么意思就是第一问可能就要求你先做离散化、建树、预处理 jump 表然后在后面的小问中反复使用。如果入场券没拿到后面基本没法写。所以备赛时不要只看“这个题我当时 A 了没有”更要看“这个题里我预处理的核心数组是否足够干净”。Python 选手要注意蓝桥杯对 Python 的时限通常比 C 宽松一些但倍增和离散化的优势依然明显尤其是涉及 (10^5) 以上数据的题。如果用 Cvector 和函数内使用的内存池都要注意如果用 Python尽量用局部变量、少用全局变量嵌套可以省下不少常数时间。7.3 我踩过的一些隐蔽坑我在带赛过程中见过最多、自己也踩过的一些隐蔽坑单独列出来供参考树状数组的 update 循环里写i i -i如果初始传入的 rank 是 0离散化后忘记 1update 会死循环。这个问题排查起来非常阴间建议在离散化后立刻打印几个 rank 检查是否从 1 开始。倍增预处理时一定是先枚举步长再枚举节点。如果调换顺序比如对每个节点先算所有步长再算下一个节点也能工作只要保证步长依赖的子问题已算好但容易写错最好固定套路顺序。ST 表查询时log2(len)是浮点运算在极端长度下可能因为精度问题取到小 1 的 k。稳妥做法是用31 - __builtin_clz(len)取整C 里这个内建函数可以直接得到 floor(log2(len))非常快。8. 现场调试与对拍验证的实战心得8.1 生成随机数据 暴力对拍是最高效的纠错法比赛里最怕的不是不会写而是写完之后不知道对不对。我见过的同学经常是样例过了就交结果错在一个边界数据上。更靠谱的做法是写一个小型对拍器生成随机小数据用暴力算法算答案再跑你的优化算法两边比对。以 LCA 为例你可以随机生成一棵小树比如 n 10然后随机 1000 个询问暴力从 u 向上走到根记录路径再和你的倍增 LCA 结果比对。只要有一组不一致马上就能定位哪个环节写错了。Python 里用 random 生成树非常方便C 也可以写一个简单的数据生成程序把生成的测试文件喂给两份代码比对输出。对拍器其实是我认为所有算法选手最应该掌握的调试工具没有之一。8.2 输出中间变量的“格尺法”定位问题如果对拍了一组数据发现出错下一步就是定位。我习惯在每个关键步骤后输出中间变量比如 DFS 后输出 depth 数组和 up[0] 数组离散化后输出 rank_map 的全部键值ST 表建完后输出某一层的几个元素。把这些中间值和手算结果比对就能知道是预处理错了还是查询逻辑错了。这个过程中最麻烦的是“数据规模一放大手算不现实”。所以对拍时一定要用小数据保证你能手算验证。很多同学喜欢直接拿大数据测一错就懵还不如先在小数据上把所有中间变量看一遍。8.3 常见报错信息速查现象可能原因排查方向数组越界 / 段错误LOG 开太小up 表越界加大 LOG检查 up[j][u] 为 0 时的处理死循环树状数组 update 时下标为 0检查离散化排名是否从 1 开始答案比暴力大很多离散化后重复值映射到不同排名检查 lower_bound 是否未 1ST 表查询随机异常log2 浮点精度问题改用31 - __builtin_clz树状数组查询结果偏小从 0 开始下标导致漏统计统一用 1-indexedLCA 结果和暴力不一致深度抬升时二进制位遍历方向错检查抬升阶段 j 从小到大跳跃阶段 j 从大到小9. 备赛资源推荐与日常训练习惯9.1 刷题平台和题单选择如果目标就是蓝桥杯不用贪多一个平台刷透就够了。我比较推荐在主流 OJ 上按专题搜索“倍增”“离散化”“ST 表”“逆序对”“区间覆盖”这些关键词找难度在普及/提高之间的题做。题量不需要大每类 8 到 10 题足够建立手感。题单怎么选我通常建议按“模板题 → 变式题 → 综合题”三级滤波。模板题先确保核心操作熟练比如给你一棵树能 5 分钟内写完 LCA给你一个数组能 3 分钟内写完离散化树状数组。变式题替换场景比如从树换到图、从数组换到矩阵。综合题才涉及多种算法叠加。不要一上来就埋头刷难题。先把模板的每个字符都理解清楚再谈变式。如果你连 up 表的第二维含义都要想一下那刷综合题只会打击自信。9.2 错题本的正确记法错题本不是把题目抄一遍就完事了。我的建议是每题记录三个要素——错误原因、正确思路、复盘时间。错误原因越具体越好不要记“粗心”而是记“离散化后没 1导致树状数组死循环”这种可以直接指导下次的内容。复盘时间是第三遍刷题时的日期用来自检到底记住了没有。我之前带过的很多同学错题本写得满满当当但从不回看等于白写。至少要在第一次记录后的 3 天、7 天各回看一次题目能无草稿纸复述思路才算真正内化。9.3 模拟赛节奏从紧张到习惯蓝桥杯的比赛时长对很多人来说是一个坎。平时练题是“写出解法”比赛是“在规定时间内写出并提交正确代码”完全是两种体验。我建议备赛中期开始每周安排一次完整模拟赛严格按比赛时间限制来练。模拟的时候要注意“放弃策略”遇到一道题 20 分钟没有任何思路果断跳过。蓝桥杯的题量不小但分值分布未必均匀与其卡在一道中等题上不如先把后面能稳定拿分的简单题写完。日常训练也要练这种“快速判断题目性价比”的能力。我自己在模拟赛里还有一个习惯每题放进 IDE 之前先在草稿纸上写下数据范围、期望复杂度、核心数据结构。这样做不是为了给别人看而是强迫自己在动手前想清楚减少写了一半推翻重来的情况。10. 写在最后的一些私人体会刷算法题这几年下来我最深的体会是倍增和离散化这两个思想看似是“技巧”其实是两种非常底层的思维方式。倍增教会你“任何状态都可以用二进制拆分成若干个预先算好的小跳”离散化教会你“面对一个很大的世界也许你只需要关心其中一小部分的相对关系”。这两种视角不只对蓝桥杯有用对后续接触更复杂的数据结构和算法也很有帮助。回到备赛本身我真心建议大家不要只背模板而是把每个模板背后的“为什么”嚼碎。比如 up 表为什么要开 log 层因为任何步数都能拆成 log 个 2 的幂比如离散化为什么要排序因为只有有序才能二分定位。思路通了代码自然写得出来遇到变式也不慌。如果你正在为蓝桥杯刷题试试先把我上面给的模板自己敲一遍再用对拍器跑几组随机数据。相信我这一步比看十篇教程都管用。 
长河君 · 2026/10/11 3:39:00 · 阅读 1.2k 蓝桥杯备赛必看：倍增思想与离散化的核心模板与实战技巧
蓝桥杯每年一到备赛季论坛里问得最多的就是“怎么从暴力优化到能过数据范围”“有没有一些套路是见题就能用的”。说实话算法竞赛里真正高频率出现、又容易被新手忽略的技巧倍增思想和离散化绝对排得上号。前者能把一些O(n)甚至O(n log n)的查询压到O(log n)后者能把稀疏的数值范围压缩成连续的数组下标两者单独用已经很能打组合起来更是很多蓝桥杯中等偏上题目的标准解法。这篇内容是我自己带赛和刷题过程中的一份深度笔记覆盖两大思想的核心原理、代码模板、经典变体和蓝桥杯题向分析适合正在备赛蓝桥杯的同学也适合刚接触算法竞赛、想建立解题工具箱的开发者。我会把每一步为什么这么做、边界在哪、坑在哪都讲透争取你看完能直接上手用而不是只记住几个术语。1. 快速热身两个思想到底解决什么问题1.1 倍增思想的直觉来源与核心模型倍增思想最早的直觉来源其实特别朴素你从一个点出发想知道往前走很远之后的状态如果一步一步走太慢那就一次性走两步、四步、八步通过预处理“跳表”来加速。在算法里这个“跳表”通常是一个二维数组比如up[node][k]表示从某个节点出发走 (2^k) 步之后到达的位置。只要能预处理出这个表任何“走任意步数”的查询都可以用二进制拆分的方式在 O(log n) 时间内完成。整个过程就是把目标步数换成二进制哪些位是 1就对应跳那几段。举个例子你想让一个指针一次走 13 步。13 的二进制是 1101也就是 8 4 1那么你先跳 1 步再跳 4 步再跳 8 步顺序无所谓反过来也行三步搞定而不是傻傻走 13 次。这是一个用“幂次预处理 二进制状态组合”换取查询速度的经典套路。为什么不叫“二分思想”因为二分强调的是“每次砍半”而倍增强调的是“从 1 到 2 到 4 到 8 翻倍增长”。倍增算法里经常配合二分使用比如“先倍增找到可行区间再二分精确收窄”但倍增本身是一种跳跃结构和二分是两码事。1.2 离散化的本质把“数值大小”变为“相对排名”离散化处理的痛点则是另一种有时候数据本身的值域很大比如 1 到 (10^9)但实际出现的不同数字只有 (10^5) 个。如果这时候你想用数组下标直接存储、统计、DP数组根本开不了那么大但你其实也不需要那么大你只需要一个“排名数组”。离散化的本质是一句话把数值映射成它在有序集合中的排名。比如原始数据是 [1000, 2, 200, 2]排序去重之后是 [2, 100, 200, 1000]那么每个数的排名就是 1、4、3、1。这个排名天然就是连续的整数 1 到 m正好可以作为数组下标或者树状数组的索引。这种“压缩值域”的操作在蓝桥杯里极其常见尤其是那些看似值域很大、但实际只用“相对大小关系”的题目。很多同学一看到 (10^9) 就发怵但其实离散化正是处理这种“数值无关紧要顺序才重要”场景的钥匙。2. 倍增思想的内功心法从快速幂到树上跳表2.1 快速幂倍增思想的最小完整单元要理解倍增最经典的入门案例就是快速幂。计算 (a^b \mod p)如果 for 循环老老实实乘 b 次b 一旦到 (10^9) 级别就完蛋。利用倍增你可以把指数 b 拆成二进制每一位代表是否需要乘上当前累积的幂次。为什么这个技巧有效因为每一步我们把底数平方相当于把指数翻倍从 (a^1) 到 (a^2) 到 (a^4)只需要 log b 次平方操作。这种“平方代替连乘”的思路是所有倍增算法的源头树上的倍增跳表本质上也是这个思路的结构化升级版。long long quick_pow(long long a, long long b, long long p) { long long res 1 % p; while (b) { if (b 1) res res * a % p; a a * a % p; b 1; } return res; }这段代码建议背到肌肉记忆级别。不只是因为蓝桥杯偶尔直接考快速幂更因为它能帮你在思维上建立“二进制拆步”的直觉。每次看到一个“跳若干步”的查询都应该下意识问自己能用二进制拆吗2.2 最近公共祖先LCA的倍增跳表LCA 是倍增思想在树上最典型的应用。求两个节点的最近公共祖先朴素做法是一个一个往上走最坏情况是一条链O(n) 查询一次。倍增做法是先把所有节点向上跳 (2^k) 步的祖先预处理出来然后查询时先把较深的节点“抬”到和另一个节点同一深度再一起往上跳直到它们的父节点相同。这里面有个关键细节往上跳的时候要从最大的步长开始试。为什么因为如果你从小的步长开始凑可能需要凑很多次达不到“log 次完成”的目标而二进制拆分本身就是从高位往低位看的所以循环里 k 从大到小。预处理时的递推公式也很重要up[j][i] up[j - 1][up[j - 1][i]]意思是节点 i 往上跳 (2^j) 步等于先跳 (2^{j-1}) 步到达中间节点再从这个中间节点继续跳 (2^{j-1}) 步。这里要求 up 表的第二维先从小到大计算保证中间节点已经算好。很多同学写错 LCA 就是因为这个递推的先后顺序搞反了。2.3 倍增的其他经典变体ST 表、快慢指针、区间覆盖除了树上跳表倍增还有一堆变体每个都值得在蓝桥杯备赛时练一遍ST 表Sparse Table用来处理静态数组的区间最值查询。预处理每个位置往后 (2^k) 长度的区间最值查询时用两个重叠区间取最值O(1) 回答 RMQ。ST 表不能用于区间求和因为 sum 没法用重叠区间直接合并会重复计算但 max/min 可以。快慢指针Floyd 判圈这算是倍增的“思想近亲”——一个指针每次走 1 步另一个每次走 2 步如果链表有环两个指针必然相遇。它不涉及二进制拆分但同样利用了“2 倍速追赶”的核心直觉。区间覆盖的最小段数给定若干线段覆盖大区间用倍增预处理从每个位置出发选择一条能延伸最远的线段后到达的位置查询时同样二进制跳跃。我个人的建议是LCA 和 ST 表在蓝桥杯中考查频率较高快慢指针偶尔出现在填空题或简单大题中区间覆盖则更多作为综合题的一个环节。准备顺序上先吃透 LCA 和 ST 表就足够了其他技巧遇到题再补不用一上来全学。3. 离散化的三步法排序、去重、二分映射3.1 基本操作一行代码搞定的背后逻辑离散化主流写法就三步排序、去重、用二分查找确定排名。C 里直接用 vector 配合 sort、unique、erase 和 lower_bound 四件套Python 里也可以模拟这个操作。vectorint nums {1000, 2, 200, 2}; sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end()); // 之后对每个原数值 x用 lower_bound(nums.begin(), nums.end(), x) - nums.begin() 1 得到排名从1开始这里去重用的是 unique 和 erase 的组合。unique 的作用是把相邻重复元素移到容器末尾并返回新的逻辑结尾迭代器erase 再把末尾的重复段删掉。注意 unique 只对“相邻”重复生效所以必须先 sort不能反过来。有一个常见误解是离散化后值一定从 1 开始。其实从 0 还是从 1 开始取决于你后面用它做什么。如果作为树状数组的下标我建议从 1 开始因为树状数组的 update 和 query 通常都是 1-indexed如果只是做 DP 的状态压缩从 0 开始则更方便跟数组下标对齐。3.2 离散化的本质是“只关心相对大小”什么时候需要离散化判断标准很简单题目里的数值大小本身不重要重要的是它们之间的“大小顺序”或者“相等关系”。最常见的信号是值域范围超大(10^9) 甚至更大但实际输入只有 (10^5) 个不同值题目要求对数值进行排名、按大小统计、区间覆盖、逆序对等操作需要把值映射成数组下标或树状数组索引举个例子求数组的逆序对数量。朴素做法是双层循环比较O(n^2)。用树状数组加速时你要把每个数值当成下标来统计“比它小的数有几个”但如果数值范围是 (10^9)树状数组根本开不了那么大。离散化之后值域缩到 n树状数组就能正常工作了。“只关心相对大小”这一点听起来有点抽象实践中可以这样判断如果把所有输入数值同时放大一万倍题目答案仍然不变那这个题本质上只需要相对顺序离散化一定适用。3.3 常见退化场景与注意事项离散化虽然写起来就几行但有几个细节坑我几乎每次讲都会强调去重前必须排序。有些人喜欢用 set 去重但 set 自带排序其实等价于 sort unique不过在处理重复元素映射时还是要小心 lower_bound 返回的第一个位置确保相等元素映射到同一个排名。如果题目要求保留原始重复信息比如统计每种数字出现了多少次那么离散化时要用“值到排名”的映射表而不是直接把原数组改成排名否则重复信息就丢了。离散化的复杂度是 O(n log n)瓶颈在排序和每次 lower_bound 的二分查询。如果对每个数都调用一次 lower_bound总复杂度就是 O(n log n)。这在 (10^5) 到 (10^6) 级别完全没问题但如果你对同一个数组做大量离散化查询可以考虑提前把映射关系存到 unordered_map 里把单次查询变成 O(1)。4. 组合实战逆序对 最小覆盖区间两个完整案例4.1 离散化 树状数组解决逆序对问题逆序对题大概是“离散化树状数组”的黄金搭档组合蓝桥杯省赛和国赛都出现过类似思路的题。完整做法分三步。第一步读入原始数组 a复制一份到 b对 b 排序去重得到离散化映射数组。第二步初始化一个长度为 n 的树状数组 bit全部为 0。第三步从右往左遍历原数组每次先查询当前值排名之前的累加和计入答案然后更新当前排名位置加 1。long long count_inversions(vectorint a) { vectorint b a; sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); BIT bit(b.size() 2); long long ans 0; for (int i a.size() - 1; i 0; --i) { int rank lower_bound(b.begin(), b.end(), a[i]) - b.begin() 1; ans bit.query(rank - 1); bit.update(rank, 1); } return ans; }为什么要从右往左遍历因为逆序对的定义是 i j 且 a[i] a[j]从右往左时已经遍历过的位置相当于“右侧元素”此时查询“小于当前值”的右侧元素个数恰好就是当前元素与右侧形成的逆序对数。如果你习惯从左往右也可以查询大于当前值的左侧元素个数只是树状数组变成后缀查询不太直观。4.2 倍增 二分求解区间覆盖问题另一道经典题是给定一个目标区间 [L, R] 和若干可选子区间最少选几个子区间才能完全覆盖 [L, R]如果不做预处理每次贪心扫描都需要 O(n)查询一多就爆炸。预处理所有区间后用倍增把查询压到 O(log n)。具体做法是先用左端点排序所有子区间然后对于每个位置 i预处理 jump[i][j] 表示从位置 i 出发选择 2^j 个子区间后能覆盖到的最远右端点。转移公式是jump[i][j] jump[jump[i][j-1]][j-1]本质上和 LCA 的 up 表完全同款。查询时从 L 出发尝试从最大的 k 往下跳只要跳跃后没有超过 R就累加段数并跳到新位置最后如果当前覆盖边界已经小于 R就再选一段补上。核心逻辑是先用大步试探再用小步逼近和二进制拆分的套路严丝合缝。这个组合案例特别适合用来练习“预处理 查询”的思考方式先想清楚暴力怎么做再看看哪些状态可以提前算好、怎么跳最快然后自然就会用到倍增。蓝桥杯的很多压轴题本质上就是让你在“预处理上花功夫把查询压到 log 级别”。4.3 两个思想结合的通用套路总结当你看到一道题同时涉及“值域很大”和“需要反复跳跃”时大概率就是离散化 倍增的组合拳。一个典型的思维链路是先离散化把稀疏数值变成连续下标再在连续下标上建 ST 表或者树状数组最后用倍增跳表回答查询。这种组合棋路其实很顺手离散化解决的“空间”问题倍增解决的“时间”问题。很多同学喜欢背模板但我觉得更重要的是掌握这条“先压值域、再压时间”的思考路径——你遇到新题时按这个顺序试命中率很高。5. 蓝桥杯场景下的题目特征、复杂度评估与调试心得5.1 如何一眼识别题目的“倍增/离散化信号”大家最关心的肯定还是考场上怎么知道这题要用这两个技巧我的判断标准一般有三个题目里有“区间查询”“跳 k 步”“祖先节点”“最少覆盖”等字样而且数据范围在 (10^5) 以上O(n^2) 必然超时——考虑倍增。输入数值范围远大于 n比如 (10^9)但题目只讨论大小关系和相等关系——考虑离散化。题目要求在线回答多个查询且每个查询本身还嵌套其他数据结构操作——大概率是预处理 倍增/离散化作为前置步骤。举个例子一道题说“给一棵 n 个节点的树q 次询问 u 向上跳 k 步到达哪个节点”n、q、k 都在 (10^5) 级别。这题一眼就是倍增 LCA 的同款模板只不过不用查 LCA只需要跳 k 步。如果你只背了 LCA没理解跳表的本质遇到这种题可能还要绕远路。反过来有些题看数据范围就知道不能用倍增如果 n 很小比如 n ≤ 100直接暴力反而更简单没有必要为了“显得高级”硬上算法。竞赛的第一个原则永远是“复杂度够用就行”不要为了炫技增加代码复杂度。5.2 复杂度计算从暴力到优化数字怎么算出来的先看暴力做法如果每次查询都从某个点一步一步走到目标位置最坏走 n 步q 次查询就是 O(nq)。当 n 和 q 都是 (10^5) 时直接是 (10^{10})在现代计算机上无论如何跑不完。倍增做法的复杂度分预处理和查询两块预处理 up 表需要 O(n log n)每个节点都要往 log n 个方向跳单次查询需要 O(log n)总共 q 次查询就是 O(q log n)。总复杂度是 O((n q) log n)n 为 (10^5) 时约 (1.7 \times 10^6) 次操作真实运行时间在毫秒级别完全能过。离散化的复杂度在排序阶段是 O(n log n)之后不管你是做树状数组还是线段树复杂度都由后续的数据结构决定。比如逆序对的完整复杂度就是 O(n log n)因为树状数组的单次 update/query 都是 O(log n)。需要注意的是复杂度计算不能只看主体循环还要把 lower_bound 的 O(log n)、树状数组的 O(log n) 都算进去。很多人觉得“我用了倍增/离散化复杂度肯定是 O(n log n)”但如果你每次查询都调用一次 lower_bound 而没有提前缓存映射实际上复杂度变成了 O(q log n)加上预处理也可能叠加成 O((n q) log n)这通常是没问题的但如果一个题还有额外的 log 因子累积就要警惕常数过大。5.3 现场避坑经验边界条件、数组维度和取整陷阱我几乎每场模拟赛都会看到同学栽在同样的几个坑上这里一起列给你们倍增数组的维度一定是 LOG1其中 LOG 约等于 log2(n) 1。如果你开小了跳着跳着就越界程序不会立刻崩但答案会莫名其妙错。建议直接开 20n ≤ (10^6) 够用或者 30省得每次算。树上的 up 表根节点往上跳要指向 0 或者自身否则处理边界时会出现死循环。我一般约定根节点的 up 值设为 0而不是自身然后用 depth 来辅助判断何时停止跳跃。离散化时 lower_bound 的返回值是迭代器从 0 开始计数。如果你需要从 1 开始比如树状数组记得 1。这是最经典的 off-by-one 错误没有之一。用 ST 表做区间最值查询时区间长度 len 取对数要向下取整查询时用两端各覆盖 (2^k) 长度的区间重叠没关系但 k 不能超过区间实际长度否则会读到未定义范围。6. 核心模板速查可直接搬进代码库的两组实现6.1 倍增模板LCA 和 ST 表的标准实现LCA 的模板我一般这样写const int LOG 20; vectorint up[LOG]; vectorint depth; void dfs(int u, int p) { up[0][u] p; for (int j 1; j LOG; j) up[j][u] up[j - 1][up[j - 1][u]]; for (int v : g[u]) if (v ! p) { depth[v] depth[u] 1; dfs(v, u); } } 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[j][u]; if (u v) return u; for (int j LOG - 1; j 0; --j) if (up[j][u] ! up[j][v]) { u up[j][u]; v up[j][v]; } return up[0][u]; }这里有个细节在把 u 抬升到和 v 同深度时我们是从低到高遍历二进制位的而在最后一步一起往上跳时是从高到低遍历。这两个方向不能搞混。前者是“凑步数”后者是“找第一个不同的祖先之后的位置”。ST 表模板则更短vectorvectorint st; void build(vectorint a) { int n a.size(); int LOG log2(n) 1; st.assign(LOG, vectorint(n)); st[0] a; for (int j 1; j LOG; j) for (int i 0; i (1 j) n; i) st[j][i] max(st[j - 1][i], st[j - 1][i (1 (j - 1))]); } int query(int l, int r) { int len r - l 1; int k log2(len); return max(st[k][l], st[k][r - (1 k) 1]); }很多讲解喜欢说 ST 表的核心是“重叠不冲突”因为 max/min 操作对重叠不敏感这点务必牢记。一旦你想用 ST 表处理 sum 就废了因为重叠区域会被重复累加。6.2 离散化模板两种常用版本标准版本已经在上文出现过我这里再给一个“保留原数组、额外存映射”的版本适合统计类题目vectorint a ...; vectorint sorted_a a; sort(sorted_a.begin(), sorted_a.end()); sorted_a.erase(unique(sorted_a.begin(), sorted_a.end()), sorted_a.end()); unordered_mapint, int rank_map; for (int i 0; i sorted_a.size(); i) rank_map[sorted_a[i]] i 1; // 从1开始 vectorint ranked_a(a.size()); for (int i 0; i a.size(); i) ranked_a[i] rank_map[a[i]];用 unordered_map 的好处是之后不需要每次 lower_bound O(log n) 查排名查询变 O(1)。代价是哈希表常数大n 小于 (10^5) 时其实和 lower_bound 半斤八两但 n 到 (10^6) 时 unordered_map 的内存和哈希碰撞开销会显现。我建议在统计类题目中如果查询次数非常多才用映射表如果只是一次性建立索引直接 lower_bound 更稳。Python 版更简洁from bisect import bisect_left def discretize(arr): sorted_vals sorted(set(arr)) return [bisect_left(sorted_vals, x) 1 for x in arr]Python 的 set 自动去重sorted 之后天然有序bisect_left 就是 lower_bound 的等价物。注意这里的 1 是否要加取决于你的后续数据结构索引约定。用 Python 写树状数组的同学建议从 1 开始方便处理 0 号哨兵位。7. 系统刷题路径与备赛节奏建议7.1 从模板到应用的“三遍刷题法”我不太建议把模板背下来就直接上考场。模板只是“内功”真正的能力在于看到题能识别出该用哪一招。我自己的刷题节奏是每题至少过三遍。第一遍自己写哪怕写得很啰嗦、复杂度不过也要先把暴力思路跑通。第二遍看题解对比别人的倍增/离散化做法找出自己卡住的原因。第三遍合上题解从头到尾手写一次优化版本并且换一组数据自测。这三遍看起来费时间但效果很扎实。第一遍让你理解题意本身第二遍让你学到新套路第三遍把套路变成自己的手感。如果只是“看看题解觉得懂了”一周之后大概率忘光白刷。7.2 蓝桥杯不同组别的策略侧重蓝桥杯省赛和国赛的难度差异体现在题量和数据范围上但核心技巧的分布还是有规律可循。程序设计赛道C/C、Java、Python的省赛离散化作为前置步骤出现较多尤其是与树状数组、线段树结合的题倍增更多出现在中等偏后的位置比如 LCA、ST 表直接作为某一问的考点。到了国赛题目往往把倍增和离散化作为“入场券”而不是压轴。什么意思就是第一问可能就要求你先做离散化、建树、预处理 jump 表然后在后面的小问中反复使用。如果入场券没拿到后面基本没法写。所以备赛时不要只看“这个题我当时 A 了没有”更要看“这个题里我预处理的核心数组是否足够干净”。Python 选手要注意蓝桥杯对 Python 的时限通常比 C 宽松一些但倍增和离散化的优势依然明显尤其是涉及 (10^5) 以上数据的题。如果用 Cvector 和函数内使用的内存池都要注意如果用 Python尽量用局部变量、少用全局变量嵌套可以省下不少常数时间。7.3 我踩过的一些隐蔽坑我在带赛过程中见过最多、自己也踩过的一些隐蔽坑单独列出来供参考树状数组的 update 循环里写i i -i如果初始传入的 rank 是 0离散化后忘记 1update 会死循环。这个问题排查起来非常阴间建议在离散化后立刻打印几个 rank 检查是否从 1 开始。倍增预处理时一定是先枚举步长再枚举节点。如果调换顺序比如对每个节点先算所有步长再算下一个节点也能工作只要保证步长依赖的子问题已算好但容易写错最好固定套路顺序。ST 表查询时log2(len)是浮点运算在极端长度下可能因为精度问题取到小 1 的 k。稳妥做法是用31 - __builtin_clz(len)取整C 里这个内建函数可以直接得到 floor(log2(len))非常快。8. 现场调试与对拍验证的实战心得8.1 生成随机数据 暴力对拍是最高效的纠错法比赛里最怕的不是不会写而是写完之后不知道对不对。我见过的同学经常是样例过了就交结果错在一个边界数据上。更靠谱的做法是写一个小型对拍器生成随机小数据用暴力算法算答案再跑你的优化算法两边比对。以 LCA 为例你可以随机生成一棵小树比如 n 10然后随机 1000 个询问暴力从 u 向上走到根记录路径再和你的倍增 LCA 结果比对。只要有一组不一致马上就能定位哪个环节写错了。Python 里用 random 生成树非常方便C 也可以写一个简单的数据生成程序把生成的测试文件喂给两份代码比对输出。对拍器其实是我认为所有算法选手最应该掌握的调试工具没有之一。8.2 输出中间变量的“格尺法”定位问题如果对拍了一组数据发现出错下一步就是定位。我习惯在每个关键步骤后输出中间变量比如 DFS 后输出 depth 数组和 up[0] 数组离散化后输出 rank_map 的全部键值ST 表建完后输出某一层的几个元素。把这些中间值和手算结果比对就能知道是预处理错了还是查询逻辑错了。这个过程中最麻烦的是“数据规模一放大手算不现实”。所以对拍时一定要用小数据保证你能手算验证。很多同学喜欢直接拿大数据测一错就懵还不如先在小数据上把所有中间变量看一遍。8.3 常见报错信息速查现象可能原因排查方向数组越界 / 段错误LOG 开太小up 表越界加大 LOG检查 up[j][u] 为 0 时的处理死循环树状数组 update 时下标为 0检查离散化排名是否从 1 开始答案比暴力大很多离散化后重复值映射到不同排名检查 lower_bound 是否未 1ST 表查询随机异常log2 浮点精度问题改用31 - __builtin_clz树状数组查询结果偏小从 0 开始下标导致漏统计统一用 1-indexedLCA 结果和暴力不一致深度抬升时二进制位遍历方向错检查抬升阶段 j 从小到大跳跃阶段 j 从大到小9. 备赛资源推荐与日常训练习惯9.1 刷题平台和题单选择如果目标就是蓝桥杯不用贪多一个平台刷透就够了。我比较推荐在主流 OJ 上按专题搜索“倍增”“离散化”“ST 表”“逆序对”“区间覆盖”这些关键词找难度在普及/提高之间的题做。题量不需要大每类 8 到 10 题足够建立手感。题单怎么选我通常建议按“模板题 → 变式题 → 综合题”三级滤波。模板题先确保核心操作熟练比如给你一棵树能 5 分钟内写完 LCA给你一个数组能 3 分钟内写完离散化树状数组。变式题替换场景比如从树换到图、从数组换到矩阵。综合题才涉及多种算法叠加。不要一上来就埋头刷难题。先把模板的每个字符都理解清楚再谈变式。如果你连 up 表的第二维含义都要想一下那刷综合题只会打击自信。9.2 错题本的正确记法错题本不是把题目抄一遍就完事了。我的建议是每题记录三个要素——错误原因、正确思路、复盘时间。错误原因越具体越好不要记“粗心”而是记“离散化后没 1导致树状数组死循环”这种可以直接指导下次的内容。复盘时间是第三遍刷题时的日期用来自检到底记住了没有。我之前带过的很多同学错题本写得满满当当但从不回看等于白写。至少要在第一次记录后的 3 天、7 天各回看一次题目能无草稿纸复述思路才算真正内化。9.3 模拟赛节奏从紧张到习惯蓝桥杯的比赛时长对很多人来说是一个坎。平时练题是“写出解法”比赛是“在规定时间内写出并提交正确代码”完全是两种体验。我建议备赛中期开始每周安排一次完整模拟赛严格按比赛时间限制来练。模拟的时候要注意“放弃策略”遇到一道题 20 分钟没有任何思路果断跳过。蓝桥杯的题量不小但分值分布未必均匀与其卡在一道中等题上不如先把后面能稳定拿分的简单题写完。日常训练也要练这种“快速判断题目性价比”的能力。我自己在模拟赛里还有一个习惯每题放进 IDE 之前先在草稿纸上写下数据范围、期望复杂度、核心数据结构。这样做不是为了给别人看而是强迫自己在动手前想清楚减少写了一半推翻重来的情况。10. 写在最后的一些私人体会刷算法题这几年下来我最深的体会是倍增和离散化这两个思想看似是“技巧”其实是两种非常底层的思维方式。倍增教会你“任何状态都可以用二进制拆分成若干个预先算好的小跳”离散化教会你“面对一个很大的世界也许你只需要关心其中一小部分的相对关系”。这两种视角不只对蓝桥杯有用对后续接触更复杂的数据结构和算法也很有帮助。回到备赛本身我真心建议大家不要只背模板而是把每个模板背后的“为什么”嚼碎。比如 up 表为什么要开 log 层因为任何步数都能拆成 log 个 2 的幂比如离散化为什么要排序因为只有有序才能二分定位。思路通了代码自然写得出来遇到变式也不慌。如果你正在为蓝桥杯刷题试试先把我上面给的模板自己敲一遍再用对拍器跑几组随机数据。相信我这一步比看十篇教程都管用。