CLRS 六至七部分核心章节

• 各图算法的思想
• 数据结构选择
• 工业应用

BFS 用队列实现无权图最短路径，DFS 用栈/递归实现连通性与拓扑；拓扑排序用 Kahn 算法或 DFS 后序；最短路径用 Dijkstra（堆优化 O(E log V)）、Bellman-Ford（负权）、Floyd（全源）；最小生成树用 Kruskal（并查集）与 Prim（堆）；最大流用 Dinic/Edmonds-Karp。工业实现中，图常以邻接表存储，用优先队列、并查集、双端队列等数据结构优化；应用于网络路由、任务调度、社交网络、推荐系统与网络流建模。工程上需处理稀疏/稠密图的不同表示、大图的内存与遍历优化。

图算法是组合优化的基石。工业实现的关键是选择合适的数据结构（邻接表、堆、并查集）与算法变体匹配图性质（负权、稠密、稀疏），并考虑大图扩展性。

• 各主题的算法思想
• 工程应用
• 复杂度与取舍

多线程算法（如 Cilk 式并行）用"工作-深度"分析并行复杂度；矩阵运算强调缓存友好的分块（如 Strassen 算法理论但工程常数大）；线性规划用单纯形/内点法求解优化问题；字符串匹配涵盖 KMP、Boyer-Moore、Rabin-Karp 等；近似算法处理 NP-hard 问题给出近似比；随机化算法用概率换来复杂度或简单性。工程上，这些算法分别用于并行计算、科学计算、运筹优化、文本搜索、组合优化与概率检索。工程语义强调"理论复杂度 vs 实际常数/缓存"的权衡。

Part VII 覆盖算法设计的"应用前沿"，每个主题都有明确的工程用途。其共同点是：理论最优并不总是工程最优，需结合缓存、并行与问题规模选型。

• Dijkstra 与折叠点
• 层次化/预处理加速
• SDN 的集中式计算

地图路由中，Dijkstra 直接用于小规模图，大规模路网用 A*（启发式）、双向 Dijkstra、层次图（Contraction Hierarchies）与 Landmark 预处理加速，把大规模查询降到毫秒级；SDN 路由集中式计算最短路径，用 Dijkstra/Bellman-Ford 在控制器中计算转发路径，并支持按策略（如带宽、延迟）加权。工程上需处理动态权重（交通、链路状态）、大规模图的内存与预处理、以及增量更新。最短路径算法是路由与导航系统的核心。

最短路径的工程化核心是"预处理换取查询时间"与"启发式/双向搜索减分支"。地图路由与 SDN 都依赖高效的最短路径求解，只是图规模与动态性不同。

• KMP/Boyer-Moore/Rabin-Karp
• 后缀树/数组
• 工程应用

文本搜索常用 KMP（O(n+m)）、Boyer-Moore（含坏字符与好后缀启发式，实际最快）、Rabin-Karp（滚动哈希，适合多模式）；DNA 序列分析用后缀树/后缀数组做子串查询、最长重复子串、模式匹配，配合 BWT 用于序列比对。工程上，文本编辑器、grep、搜索引擎用 Boyer-Moore/KMP；生物信息中用后缀数组与 BWT 处理超长序列。选择取决于模式长度、多模式需求与内存约束。

字符串匹配在"精确匹配"与"索引加速"间取舍。KMP/Boyer-Moore 适合单次搜索，后缀数组/BWT 适合需要多次查询与索引的大规模序列（DNA）。

• 合并策略
• 势能/每个元素被移动次数
• 总复杂度

Small-to-Large 合并策略：把较小的集合合并到较大的集合中，每次操作只遍历较小集合的元素。证明要点：每个元素每次被"移动"时，所在集合大小至少翻倍（因为并入更大集合），因此每个元素至多被移动 O(log n) 次，n 个元素总移动次数 O(n log n)。这一论证是"势能/倍增"分析：集合大小单调增长，限制每个元素的重放置次数。Small-to-Large 广泛用于并查集子树合并、启发式合并、树形 DP 合并等。

O(n log n) 的关键是"每个元素所在集合大小单调翻倍"，故每个元素移动次数有界。它是"小合入大"类算法的通用势能证明，与启发式合并等价。

• 并查集合并方向
• 子树信息维护
• 说服工程技巧

在并查集需维护集合内信息（如子树颜色集合、元素集合）时，用 Small-to-Large 合并：合并两个集合时，把较小集合的信息逐一并入较大集合，而不是按秩合并的固定方向。这样每条信息被移动次数 O(log n)，总维护代价 O(n log n)。工程实现中，用集合（如 HashSet/vector）存储每个集合代表元的信息，合并时遍历小集合插入大集合，并更新代表元。该技术用于离线算法（如 DSU on Tree、子树合并）中，在并查集基础上同时维护可合并的集合数据。

把"并查集代表元"与"集合内信息"结合，用 Small-to-Large 决定合并方向，使信息维护的总代价有界。工程实现的关键是选择合适的数据结构承载集合信息。

• multiset 合并
• Small-to-Large 应用
• 子树信息统计

求每个子树的不同颜色数，可对每个节点维护一个 multiset 记录子树内颜色出现次数，用 Small-to-Large 合并：把子节点的 multiset 并入父节点，合并时把小集合元素插入大集合并更新不同颜色计数。每个元素（节点）被移动 O(log n) 次，总复杂度 O(n log n)。工程实现需用高效容器（如 unordered_map 或平衡树）记录颜色计数，合并时维护"不同颜色数"这一增量。该技术是 DSU on Tree 与子树统计的通用基础。

子树 multiset 合并把"每节点的子树统计"转化为"Small-to-Large 合并"，用倍增保证 O(n log n)。核心是合并时增量维护不同颜色数，避免重复扫描。

• HLD 的链划分
• dfn 序到区间
• 树状数组维护

树链剖分把树分解为若干链，每个节点映射到 dfn 序，使一条链对应一个连续区间。对于"单点修改、路径求和"，用树状数组（BIT）维护 dfn 序上的值：单点修改更新 BIT 的对应位置；路径求和时，沿 HLD 把路径拆为若干条链的区间，对每条链在 BIT 上做区间求和，最后累加。每次操作经过 O(log n) 条链，每条链 O(log n) 区间查询，总复杂度 O(log² n)。相比线段树，树状数组常数小、实现简单，适合只支持单点修改与区间求和（无区间赋值）的场景。

HLD 把"树路径"转化为"若干 dfn 区间"，树状数组提供高效的区间求和与单点更新。两者的组合是"树路径 + 简单值操作"的经典高效方案。

• 0/1 边权 BFS
• 约束转换
• HLD 与二分

0/1 边权最短路径可用双端队列 BFS（0-1 BFS）在 O(V+E) 内求解。若路径上还需满足"经过的某种边数不超过某阈值"等约束，工程上常把约束转化为二分：对阈值 x 二分其可行性，用 0-1 BFS 判定是否存在满足约束的路径。HLD 在此类问题的角色是：当路径约束与"树上路径"有关时，用树链剖分把路径分解为区间，配合数据结构（如差分、线段树）判定约束是否满足。整体复杂度为二分次数 × 判定代价。

0-1 BFS 解决基础最短路，二分处理"单调约束"（可行性随阈值单调），HLD 处理树路径的区间化。三者组合是"树上带约束最短路"的通用框架。

• 重儿子定义
• 保留/清空策略
• 复杂度

Sack（DSU on Tree）是离线处理子树查询的算法：对每个节点，先递归处理轻儿子（每次处理完清空其贡献），再处理重儿子（保留其贡献），最后把轻儿子的贡献重新加入并回答该节点查询。重儿子保留避免重复计算，轻儿子每次清空重算；由于每个节点只在"作为轻儿子的祖先链"中被加入有限次，总复杂度 O(n log n)。工程实现用全局计数数组维护答案，软清空（只重置计数）配合重儿子保留。适合子树众数、颜色数等统计查询。

Sack 的精髓是"重儿子保留贡献、轻儿子清空重加"，用继承避免重复，使每个节点被重加 O(log n) 次。它把"逐子树统计"优化为 O(n log n)。

• 问题建模
• 奇偶计数
• DSU on Tree 实现

CF 570D 要求对每个查询 (v, h) 判断子树 v 中深度为 h 的节点字符能否重排成回文。回文条件：深度 h 层中字符出现次数为奇数的字符数 ≤ 1。用 DSU on Tree 离线处理：对每个节点维护深度 → 字符频率的"奇偶掩码"，用全局计数数组记录各深度的奇偶信息（用位掩码表示各字符出现奇偶），重儿子保留、轻儿子清空。回答查询时取该深度掩码的 popcount ≤ 1 即可。复杂度 O((n+q) log n)。

该题把"回文判定"转化为"奇偶计数 ≤ 1"，用位掩码压缩字符频次，DSU on Tree 提供子树深度的离线统计。关键是把"深度+字符"的二维信息用掩码高效维护。

• 最大流/最小割
• 网络设计建模
• 任务调度

最大流问题求源到汇的最大流量，最小割定理给出最大流等于最小割。工程上，网络设计用最大流/最小割分析网络容量瓶颈、划分与鲁棒性；任务调度用二分图匹配（可转化为最大流）求解工人-任务分配、最大匹配、最小路径覆盖；多源多汇、带容量约束的分配问题也建模为最大流。算法用 Dinic（O(E√V) 二分图）或 push-relabel 高效求解。工程应用涵盖带宽分配、资源调度、二分匹配与网络规划。

最大流把"容量约束下的最优分配"统一建模，最小割揭示瓶颈与划分。工程上先用图建模流量/匹配，再选择高效流算法求解。

• 模运算与快速幂
• 扩展欧几里得
• 素性测试与 RSA

数论算法是密码学的基础：模运算与快速幂（快速幂取模）用于加密解密；扩展欧几里得求模逆元（RSA 私钥、模运算）；Miller-Rabin 素性测试用于生成大素数；RSA 依赖大整数模幂与因子分解的困难性。工程上，这些算法用于密钥生成、加密、签名、哈希与零知识证明。实现需注意大整数运算、防止侧信道攻击、常数时间比较等。数论算法是公钥密码与安全协议的核心组件。

数论为密码学提供"单向性"（模幂易、离散对数/分解难）与代数工具（模逆元、素性）。工程实现强调效率与安全性（常数时间、防侧信道）。

• 启发式合并思想
• DSU on Tree 的继承
• 复杂度统一

Small-to-Large 与 DSU on Tree 都是"启发式合并"：把较小集合并入较大集合，靠"每个元素所在集合大小翻倍"保证 O(n log n)。统一视角：DSU on Tree 是"树上启发式合并"的特例，它通过"重儿子保留、轻儿子清空重加"实现每个子树只被完整扫描一次，等价于对所有节点做 Small-to-Large，只是用"继承重儿子"替代显式合并。两者复杂度来源相同（倍增），实现上一个显式合并集合、一个继承重儿子贡献。统一视角帮助理解树的离线统计与一般集合合并的共性。

二者的本质都是"小合入大 + 倍增耗尽移动次数"。DSU on Tree 是"结构化的 Small-to-Large"（按树链定向继承），统一视角便于迁移与复杂度分析。

• HLD 的静态路径
• LCT 的动态路径
• 路径修改

HLD 用于静态树，把路径分解为若干 dfn 区间，配合线段树做路径修改/查询；LCT（Link-Cut Tree）用于动态树（支持加边、删边、换根），用 splay 维护偏好路径（preferred path），对路径修改通过 access 操作把路径展平到一条 splay 上再打懒标记。工程取舍：静态树用 HLD+线段树（简单、实现稳），动态树用 LCT（O(log n) 但实现复杂）。路径修改在 HLD 中是区间打标，在 LCT 中是"access 后整条 splay 打标"。

HLD 与 LCT 都解决"路径操作"，但 HLD 面向静态树、LCT 面向动态树。路径修改的核心是"把路径映射到可维护的线性结构"（dfn 区间或 splay 实链）。

• dfn 序的子树连续
• 子树区间映射
• 区间查询

在树链剖分中，对树做 DFS 得到 dfn 序，一棵子树恰好对应 dfn 序上一个连续区间 [dfn[u], dfn[u]+size[u)-1]（因为 DFS 先访问完整棵子树再离开）。因此子树查询转化为区间查询，用线段树/树状数组在 O(log n) 内完成。这是 HLD 区间映射的基础：子树天然连续，无需拆链。与其相对，路径查询需拆成若干条链，复杂度 O(log² n)；子树查询因 dfn 连续而只需 O(log n)。

子树查询的 O(log n) 来自"DFS 序中子树连续"这一性质，使子树映射为单区间，避免链拆分。现存于线段树/树状数组即可。

• 链拆分
• 区间查询
• 复杂度分析

HLD 把树路径分解为 O(log n) 条链（因为任意路径跨越的轻边数 O(log n)），每条链对应 dfn 序上的连续区间。对每条链的区间做线段树查询（求和/最值），累加或取 max，复杂度为 O(log n) 条链 × O(log n) 区间查询 = O(log² n)。工程实现需在跳链时维护 top[u]、dfn[u]、线段树，并注意方向（路径两端向 LCA 收敛）。若改为树状数组做单点更新+区间求和，路径求和仍为 O(log² n) 但常数更小。

O(log² n) 来自"链数 O(log n) × 每条链区间查询 O(log n)"。它是 HLD 处理路径问题的标准复杂度，来源于轻边数的对数上界。

• 深度与祖先数
• 子树信息维护
• 结合查询

子树深度可用 dfs 时记录 depth[u]，祖先数即 depth[u]（根深度为 0 时祖先数 = depth[u]，或根深度为 1 时 = depth[u]-1）。在子树信息查询中，需同时维护"子树内各深度"的信息，通常用桶/数组按深度记录，配合 DSU on Tree 或线段树合并。例如查询"子树 u 中深度为 h 的节点数"，用深度桶统计。祖先数用于判断深度关系（如节点是否在另一节点的子树、LCA 深度）。工程上结合 depth 数组与 dfn 序、子树 size 实现各类子树查询。

深度与祖先数是树的基础属性，用来索引子树信息（按深度）、判断祖先-后代关系、定位 LCA。子树查询常把"深度维度"纳入统计结构。

• 长链剖分定义
• 与 HLD 的差异
• 与 LCT 的取舍

长链剖分按"子树最大深度"划分重儿子（长链），与 HLD 按"子树大小"划分不同。长链剖分适合处理"深度相关"的 DP 与"K 级祖先"查询（O(1) 配合跳表），并把子树合并（如维护深度桶）优化到 O(n)。HLD 按子树大小划分，适合路径统计与子树区间查询。LCT 面向动态树，支持加边删边。工程取舍：静态树且深度相关用长链剖分，静态树且路径统计用 HLD，动态树用 LCT。长链剖分实现简单但适用面窄，主要服务于深度 DP 与 O(1) 祖先查询。

三种剖分按"深度/大小/动态"划分适用场景。长链剖分用"长链覆盖"优化深度相关 DP 与祖先查询，HLD 用大小划分优化路径查询，LCT 用 splay 支持动态。

• 典型题型
• 全局计数数组
• 重儿子保留

CF EDU DSU on Tree 章节覆盖的典型题型：子树众数/出现次数最多的颜色、子树内不同颜色数、子树内按深度统计、子树内满足条件的节点数等。这些题共同模式是"对每个子树回答一个基于子树内节点信息的统计查询"，用 DSU on Tree 离线处理：全局计数数组维护当前统计，重儿子保留、轻儿子清空重加，在 add 时增量更新答案。复杂度 O(n log n)。典型题如 CF 600E（众数和）、CF 570D（深度字符）、CF 375D（颜色计数）。

DSU on Tree 的题型依赖"子树的聚合统计 + 全局计数数组 + 增删改查"。回答查询时利用已保存的重儿子贡献，只需重加轻儿子，避免重复计算。

• Top Tree 概念
• 子树与路径统一
• 与 HLD 结合

Top Tree 是维护树上动态聚合（子树与路径）的树数据结构，基于 cluster（簇）的合并与分裂，支持 O(log n) 的路径与子树操作。在 HLD 基础上，Top Tree 把树分解为"偏序簇"（rake/compress），统一处理路径、子树与换根等操作。工程上，Top Tree 用它把"路径操作"与"子树操作"在同一个簇结构上维护，配合懒标记实现动态树聚合。相比 LCT，Top Tree 更利于复合聚合（如路径+子树）；实现复杂度高，常作为 HLD 与 LCT 的扩展。

Top Tree 用 cluster 抽象统一"路径/子树"的聚合，通过 rake 与 compress 组合簇。它在 HLD 之上提供更统一、更灵活的树动态维护模型。

• cluster 分解
• 聚合与分裂
• 复杂度

Top Tree 把树划分为若干 cluster（簇），每个 cluster 有聚合信息（如路径和、最值），通过 rake（合并旁支）与 compress（合并链）两个操作组合簇。动态修改（边权更新、换根）时，更新受影响的簇并自底向上重算聚合，cost 层 O(log n) 的簇级分解保证单次操作 O(log n)。路径聚合查询通过"找到覆盖路径的簇分解"并合并各簇聚合得到。工程实现需维护簇的边界、聚合值与懒标记，复杂度来自簇树的高度/重叠。

Top Tree 的 O(log n) 来自"簇的平衡分解"，任何路径/子树可分解为 O(log n) 个簇。聚合经簇合并计算，动态更新经簇分裂/合并维护。

• Cluster Forest
• 分裂与合并
• 动态维护

Top Tree 用 Cluster Forest 表示动态树：一个簇（cluster）由若干顶点与边组成，维护其内部结构；整个树被组织为簇的森林，其中根簇代表整棵树。路径分裂（如加边/删边、换根）通过把簇拆分为子簇（split）与组合（merge）实现，保持簇的平衡。Cluster Forest 表示使路径分裂与合并成为局部簇操作，配合 rake/compress 维护聚合。工程上，用平衡树/链式结构实现簇的 split/merge，保证 O(log n) 的复杂度。

Cluster Forest 把树的动态变化转化为"簇的 split/merge"，使路径分裂与合并成为局部、可平衡的操作。复杂度依赖簇的平衡分解。

• 众数和定义
• 颜色桶维护
• DSU on Tree 实现

CF 600E 求每个子树中"出现次数最多的颜色"的编号之和（众数和）。用 DSU on Tree 维护全局颜色计数桶（cnt[color]）与当前众数信息（maxCnt 与 sum）：add 一个节点时更新 cnt，若新计数超过 maxCnt 则更新 maxCnt 与 sum，等于则累加 sum。重儿子保留、轻儿子清空重加，回答每个子树查询时读取当前 sum。复杂度 O(n log n)。颜色桶用数组/哈希表，众数和用增量维护避免全量扫描。

该题的关键是"增量维护众数"：在 add/remove 时用 cnt、maxCnt、sum 三元组快速更新，避免每次扫描颜色。DSU on Tree 提供子树统计框架。

• 深度相关 DP
• 长链继承
• O(n) 复杂度

对深度相关的树形 DP（如"子树内距离某节点 ≤ k 的节点数"），用长链剖分优化：每个节点维护一个按深度索引的 DP 数组，重儿子（长链）的数组直接继承（复用指针），轻儿子（短链）的数组合并进父节点。由于每次合并只遍历短链的深度，而每个深度只被合并到更长链一次，总合并代价 O(n)。配合"深度维度数字化"（把长链深度差值作为偏移），实现 O(n) 的深度 DP，相比朴素 O(n²) 显著优化。

长链剖分用"继承最长链 + 合并短链"避免深度维度的重复计算，每个深度只被合并 O(1) 次，故总 O(n)。适合深度相关但状态随深度单调合并的 DP。

• 支配集 DP
• 长链剖分结合
• O(n) 复杂度

树上支配集/最小支配集 DP 通常需维护"距离最近被选节点"等深度相关状态，朴素深度 DP 是 O(n²)。长链剖分优化：把重链的 DP 数组以指针形式继承，轻链合并时只遍历短链深度，总合并代价 O(n)（每个深度只被合并一次）。对支配集 DP 中"距离 ≤ k"的深度状态，用长链剖分把每个节点的深度数组代价摊到 O(1)，实现 O(n) 求解。工程上需用动态数组/指针继承并处理状态语义的偏移。

支配集 DP 的状态随深度索引，长链剖分通过"继承长链 + 合并短链"把深度维度的重复计算消除，使总复杂度 O(n)。这是长链剖分对深度 DP 的通用优化。

• 指针继承
• vector 复用
• 合并优化

长链剖分进行深度 DP 合并时，为"继承重儿子数组"常用指针技巧：每个节点分配一个数组，重儿子直接复用父节点的数组（用指针指向偏移），避免拷贝；轻儿子用独立数组，合并时把短链元素并入长链数组。工程上也可用 vector 配合"swap 复用"：把重儿子的 vector 通过 move 交给父节点，轻儿子合并后复用空闲 vector。这样避免 O(n²) 的数组拷贝，使总合并代价 O(n)。需小心下标偏移与数组生命周期管理。

长链剖分 O(n) 的工程基础是"避免数组拷贝"：指针继承或 vector move 复用实现长链数组的共享，合并只遍历短链。生命周期与偏移管理是实现关键。

• 二进制抬表
• 长链剖分 O(1) 查询
• 预处理与查询取舍

二进制抬表（树上倍增）预处理 O(n log n) 时间与内存，查询 K 级祖先 O(log n)；长链剖分预处理 O(n)，查询 K 级祖先 O(1)，但需配合跳表（每个节点记录长链上跳 K 步的位置）。取舍：二进制抬表实现简单、通用（还支持 LCA），但查询 O(log n)；长链剖分查询 O(1)、预处理 O(n)，但实现复杂、主要针对 K 级祖先单查询。若频繁查询 K 级祖先且无需 LCA，长链剖分更优；若需 LCA 或实现简单，用二进制抬表。

两种方案在"预处理/内存"与"查询时间"间取舍。二进制抬表 O(n log n) 预处理 + O(log n) 查询，长链剖分 O(n) 预处理 + O(1) 查询，适合高频 K 级祖先查询。

• 预处理跳表
• O(1) 查询
• 与二进制抬表对比

长链剖分实现 K-th ancestor：预处理时对每个节点，记录其所在长链并预计算"长链顶部"与"链上第 2^j 个祖先"跳表（O(n log n) 预处理）。查询 K 级祖先 O(1)：先用二进制跳表跳到 K 的最高位对应的 2^j 祖先，再沿长链顶部向上/向下定位到具体祖先。该方案 O(n log n) 预处理、O(1) 查询，比纯二进制抬表的 O(log n) 查询更快，适合高频祖先查询。工程上需维护 up[][] 跳表 + 长链位置映射。

长链剖分 + 跳表结合了二进制抬表的"跳大步"与长链的"O(1) 链内定位"，实现 O(1) 查询。预处理 O(n log n) 同二进制抬表，但查询常数更小。