第七章 高阶内功：并查集、线段树、字符串匹配与位运算

第七章 · 高阶内功：并查集、线段树、字符串匹配与位运算

本章要回答的四个问题：第四章 Kruskal 判环时客串的并查集，凭什么"近乎常数"？要"边改边查区间和"，前缀和为什么不够用？在一段长文本里找一个模式串，怎么避免一位一位地重比？把整数看成一组开关，能省下多少循环？

为什么会有这一章

这一章是前六章的组合技展示厅。四件兵器各对应一类高频需求的极致优化：

• 并查集把"分组与合并"做到近乎常数：路径压缩与按秩合并两式合璧，单次操作均摊只比常数多一点点；
• 线段树与树状数组给"单点修改加区间查询"这个矛盾需求提供对数级解法——前缀和查得快但改不动，数组改得快但查不动，两者用树形结构两头兼顾；
• KMP 与 Rabin-Karp 是字符串匹配的内外双修：前者靠失配指针记住"已匹配前缀的信息"，后者用哈希把一段子串压成一个数来比较；
• 位运算是最底层的暗劲：集合用整数表示、状态用二进制枚举、乘除用移位替换。

四件兵器没有一件是孤招：并查集消费第四章的判环需求，线段树生长在第三章的完全二叉树数组映射上，KMP 的失配数组本质是"模式串自己匹配自己的动态规划"，位运算则贯穿其余三件的下标算术。这也是把它们压轴的原因：读得懂这一章，说明前六章真的通了。

读完能解决什么

对照开头的问题，本章的知识点清单如下：

• 能实现带路径压缩与按秩合并的并查集，复现"不压缩时长链、压缩后近乎扁平"的对比实验；
• 能用并查集解连通分量、判环，并说清它在 Kruskal 里的角色；
• 能建线段树并实现单点修改与区间求和，跟踪一次下推分解的过程；
• 能用树状数组实现前缀和查询与单点更新，说清 lowbit 的下标含义与两者复杂度；
• 能手工算出 KMP 的失配数组（next）并用它走完一次完整匹配，数出与朴素匹配的比较次数差；
• 能解释 Rabin-Karp 的滚动哈希原理与"哈希相等需二次确认"的原因；
• 能用位运算实现判奇偶、取最低位一、统计位一的个数、枚举子集，并说出移位运算的三个高发事故。

各节怎么分工

先决条件

• 第四章 Kruskal（并查集的消费现场）与图的连通性概念；
• 第二章数组与哈希表（树状数组的下标算术、Rabin-Karp 的取模）；
• 3.1 节完全二叉树的数组映射（线段树的存储方式）；
• 第一章复杂度推导（对数级论证在本章反复出现）；
• 第六章的贪心与动态规划（KMP 的失配数组、限界思想都要借力）。
• 前置有缺口不必慌：每节开头都会点明用到哪一节的哪个结论，缺哪补哪即可。

往下走到哪

本章是本册的终点站，也是更多旅程的起点：并查集通向最小生成树与动态连通性（离线算法）、线段树通向懒标记与区间更新、字符串算法通向 AC 自动机与后缀数组、位运算通向状态压缩动态规划。四件兵器在手，读开源实现（数据库的区间索引、正则引擎、网络连通性判定）时，你看到的将不再是咒语，而是熟悉的心法组合。收官的检验标准也只有一条：拿一篇你感兴趣的源码或一道没见过的题，能认出它用了哪门内功、为什么选它——认得出，本册就算修成了。

高阶兵器的关系图