CP-Algorithms 模板与实战

• 根据 n 估算需要的复杂度量级（O(n^2)、O(n log n)、O(n)）
• 根据时限与语言常数选择实现
• 根据输入特点（稀疏/稠密、结构特征）选择算法

实战选择算法首先要估算复杂度量级：由 n 的上界反推允许的复杂度（如 n=10^5 需 O(n log n) 或更好，n=10^3 可 O(n^2)，n=10^6 需 O(n)）。其次结合时限与语言：同样复杂度在 C++ 可承受更大常数，在 Python/Java 需更注意常数；时限紧时选常数小的实现（静态数组、位运算）。再次考虑输入特点：稀疏图用邻接表、稠密图用矩阵；数据有序/无序决定是否需排序；是否允许离线（用离线算法如莫队、CDQ）等。最后权衡：数据规模小可用暴力/朴素，规模大需高效算法；有特殊结构（如单调、凸）可针对性优化。决策是"复杂度 + 常数 + 数据特征"的综合判断。

选算法的入口是"n 与时限"给的复杂度预算，再结合常数与数据特征。核心是"估复杂度可接受 + 选常数合适的实现 + 利用数据特征"。这是竞赛从模板到实战的关键能力。

• 数论：素数、GCD、模运算、逆元、组合数
• 图论：最短路、最小生成树、网络流、连通性
• 字符串：哈希、KMP、后缀数组、自动机

CP-Algorithms 覆盖三大模块：数论（素数筛、扩展欧几里得、模逆元、组合数、线性同余）、图论（BFS/DFS、最短路、MST、网络流、SCC、匹配）、字符串（哈希、KMP、Z、后缀数组、AC 自动机、SAM）。三者有依赖与组合：数论为图论提供模运算（如带模最短路、生成函数）、为字符串提供模与哈希（素数模、逆元）；图论算法被字符串用于后缀自动机/后缀树的图结构；字符串哈希与数论模运算结合。组合用法常跨模块：如"数论 + 图论"（带模计数、矩阵快速幂）、"字符串 + 图论"（自动机构造、后缀树）、"数论 + 字符串"（多项式哈希）。理解依赖关系能帮你按需组装模板。

三块不是孤立的：数论是地基（模、逆元、素数），图论与字符串都依赖它；字符串自动机本身是图论结构。组合用法围绕"把一类问题归约到另一类"（如把匹配问题建模为图、把计数问题用数论）。

• 杜教筛用狄利克雷卷积 f*g 的性质递推前缀和
• 先线性筛预处理前 n^(2/3) 项，大项用递归/记忆化
• 结合取整分块（整除分块）优化

杜教筛用于求数论函数（如莫比乌斯函数 μ、欧拉函数 φ）的前缀和 S(n) = Σ_{i<=n} f(i)，当 n 很大（如 10^10）时无法线性筛。它利用狄利克雷卷积：若 f*g = h，且 g、h 的前缀和好求，则 S_f(n) = S_h(n) - Σ_{d=2}^{n} g(d) * S_f(n/d)。用整除分块把 Σ 分成 O(sqrt n) 段，每段递归求 S_f 的较大参数；配合预处理前 n^(2/3) 项（线性筛）作为小项直接查表，大项用记忆化递归。总复杂度 O(n^(2/3))。典型应用：求 μ、φ 前缀和，从而求 gcd 相关计数、互素数对计数。

杜教筛的核心是"用卷积把大前缀和归约到更小的前缀和 + 整除分块"。关键在于选择 g 使得 h=fg 的前缀和容易求（如 μ1=ε，φ*1=id）。预处理 + 记忆化保证每层只算一次，O(n^(2/3))。

• 模拟退火：温度下降 + 接受劣解概率
• 调参：初始温度、降温速率、迭代次数、终止条件
• 调参曲线：温度与接受率/收敛速度的关系

模拟退火是启发式全局优化，模仿冶金退火：从高温度开始，随机扰动解，接受更优解且以概率 e^(-Δ/T) 接受劣解；温度按一定速率下降，最终收敛到低温（局部最优）。工程调参关键在温度曲线：初始温度 T0 决定初始接受率（太高则漫游、太低则早陷入局部最优）；降温速率（如几何降温 T *= α，α 常取 0.98~0.999）决定探索与收敛的平衡（α 大则探索充分但慢）；每温度迭代次数与扰动幅度；终止条件（温度阈值或最大迭代）。调参曲线本质是"探索-利用"权衡：前期高接受率全局搜索，后期低接受率精确收敛。对 TSP 等 NP-hard 问题，模拟退火能给出高质量近似解，但需对具体问题调参（扰动方式、邻域结构）。

调参的核心是"温度曲线控制探索-利用"。初始温度定接受率、降温速率定探索持久度、迭代次数定收敛精度。工程上是"接受劣解概率随温度下降"的机制让算法跳出局部最优。无通用最优参数，需针对问题校准。

• SAM 的 O(n) 构造与状态/转移
• 子串出现次数：endpos 大小累加
• 不同子串数：Σ(len - len[link])

后缀自动机（SAM）的工程模板覆盖多个子串问题。子串出现次数：对每个状态，其 endpos 集合大小即出现次数，构造时先给主串各前缀的最后一个状态计数 +1，再按 len 递减的拓扑序把计数沿后缀链接 link 累加到父状态。不同子串数：每个状态贡献 len[v] - len[link[v]] 个互不相同的子串，求和即可。最长公共子串：对较短串建 SAM，用较长串在 SAM 上匹配，维护当前匹配长度与状态，匹配失败时沿 link 退而更新长度，得到最长公共子串。三者都基于"状态 = endpos 等价类 = 一段长度区间的子串集合"这一核心性质。

SAM 的核心是"endpos 等价类"：每个状态代表一段长度区间 [len[link]+1, len[v]] 的子串，它们 endpos 相同。出现次数 = endpos 大小（拓扑序累加），不同子串数 = 各状态长度区间长度之和，公共子串 = 在 SAM 上匹配。理解状态与 link 是模板基础。

• 主席树：按版本建可持久化线段树，值域上计数
• 每个前缀一个版本，根存版本
• 查询区间 [l,r] 的 K 小值用两版本差分

主席树（可持久化线段树）用于静态区间第 K 小（K-th number）。做法：把数组离散化到值域，为每个前缀 [1..i] 建一棵线段树（记录值域中各值的出现次数），相邻前缀共享未变部分，形成版本链。build 时先建空树（全 0），update 时对每个位置 i 在版本 i-1 基础上单点 +1（路径复制 O(log n)）。查询区间 [l,r] 的第 K 小：同时从版本 r 与版本 l-1 的根出发，比较左子树计数差（cnt[r左]-cnt[l-1左]），若 >= K 则往左走，否则 K 减去该差往右走，O(log n)。离线是因为需先离散化并确定查询区间。

主席树的核心是"版本差分"：版本 r 与版本 l-1 的计数差即区间 [l,r] 的计数。前缀线段树 + 路径复制 + 值域计数是三大支柱。查询用两根并行下降实现 O(log n)。

• 爬山法：从当前解向邻域中更优解移动，易陷入局部最优
• 局部搜索：2-opt/3-opt 等邻域算子
• 收敛速度与解质量权衡

爬山法（hill climbing）是贪心局部搜索：从当前解出发，在当前邻域中找更优解并移动，直到无改进，简单快速但易陷入局部最优。对 TSP/VRP 等组合优化，常用局部搜索算子（如 2-opt：交换两条边消除交叉；3-opt；or-opt 移动子路径）构造邻域。工程收敛速度取决于邻域大小与算子复杂度：2-opt 每次 O(n^2) 评估改进，收敛较快但易局部最优；3-opt 邻域更大、解质量更好但更慢。实际常结合"多次随机起点 + 局部搜索"（多起点）或把爬山作为更复杂算法（模拟退火、禁忌搜索）的局部改进算子。工程上根据问题规模与时限权衡邻域算子与迭代次数。

爬山/局部搜索的工程权衡是"邻域大小 vs 收敛速度 vs 解质量"。2-opt 快但局部最优，3-opt 好但慢。工程常用"多起点 + 局部搜索"或"局部搜索作为启发式组件"提升质量。理解"邻域算子"是核心。

• HAMT：用 32 位 hash 切分成 5-bit 段 + bitmap 稀疏节点
• immutable 结构：更新共享路径，旧版本保留
• Map/Set/List/Record 的封装

Immutable.js 的 Map/Set 基于 Hash Array Mapped Trie（HAMT）：把键的 32 位 hash 按 5 bit 切分成若干段，每段决定在 TIRE 一层中的分支（32 路扇出），用 bitmap 标记稀疏节点中实际存在的子槽，减少内存。更新时沿 path 复制共享节点（路径复制），旧版本不变，实现不可变（immutable）语义；List 用前缀树按索引切分；Record 是固定字段的 Map。这套结构使 Map/Set/List 的 get/set O(log_32 n)（近似常数），且天然支持结构共享与历史版本。工程上，bitmap + 32-way 分支是 HAMT 的核心，兼顾速度与内存。

HAMT 的核心是"hash 按 5-bit 分段 + bitmap 压缩稀疏节点"。immutable 依赖路径复制共享。5 bit 取 32 路分支是"缓存友好 + 深度浅"的平衡。理解 hash 分段与 bitmap 是掌握 HAMT 的关键。

• 32-bit hash 按 5-bit 段逐层索引，32 路扇出
• bitmap 标记稀疏节点中实际存在的子槽
• 持久化：路径复制共享旧节点

Persistent HAMT 把键的 32 位 hash 分成 5 个 bit 一段，共 6 层多（32 bit / 5 = 6.4），每层用一段 5-bit 值作为该层数组的索引，形成 32 路分支的 trie。由于 32 路分支使深度浅（约 6-7 层），查找/插入 O(log_32 n) 近似常数。为了省内存，用 bitmap 压缩：稀疏节点只存 bitmap（32 位，标记哪些子槽存在）与紧凑的子数组（只含存在的槽），定位通过 popcount 计算偏移。持久化（persistent）通过路径复制：插入/删除时沿路径复制节点，新版本指向新根，旧版本节点共享不变。这使 HAMT 既高效又支持不可变与历史版本。

核心是"hash 分段 + bitmap 压缩 + 路径复制"。5-bit 段选 32 路是深度与缓存的平衡；bitmap 让稀疏节点紧凑；路径复制实现持久化。理解这三者是 HAMT 工程实现的关键。

• RocksDB/BoltDB 是 LSM-tree / B+tree 存储引擎
• snapshot 提供一致性读视图
• 持久化键值存储的工程化

RocksDB 与 BoltDB 都是嵌入式键值存储，但用不同数据结构：RocksDB 用 LSM-tree（Log-Structured Merge，写由内存 memtable + 磁盘分层 SST，读用布隆过滤器加速），BoltDB 用 B+tree（单文件、ACID 事务）。snapshot 是它们提供的一致性读视图：读操作在 snapshot 上看到固定时刻的数据，不受后续写影响。RocksDB 的 snapshot 通过版本号与 sequence number 实现，读在固定版本上；BoltDB 的 snapshot 通过 B+tree 的页复制/不可变页实现（mmap + 写时复制）。"Persistent HashMap" 在工程上常体现为：用这类存储引擎的 snapshot 能力实现"键值数据的历史版本/一致性读"，而非字面意义的可持久化哈希表。工程化路径是"用成熟存储引擎 + snapshot 语义"而非自己实现完备的持久哈希。

RocksDB/BoltDB 的 snapshot 是"持久化 + 一致性读"的工程答案。RocksDB 用 LSM + sequence，BoltDB 用 B+tree + 写时复制。工程上"持久化 Map"通常交给存储引擎，而非自建可持久化哈希表。

• 函数式语言（Racket/Elixir）天然支持不可变结构
• AI（Association List）与 AVL 的取舍
• 各语言对持久化树的生态支持

Racket 与 DrRacket 是函数式语言，默认不可变数据结构，持久化 AVL 树（作为有序 map）原生支持，插入/删除返回新树、旧树不变，footprint 小；Racket 还提供标准库的 sorted-map（基于 AVL/红黑树）等。Elixir（Erlang VM）同样不可变，Erlang 的 :gb_trees（广义平衡树）与 :maps 提供持久化结构，footprint 中等。对比：Racket/Scheme 生态对"函数式持久树"最自然、教学与库支持完善；Elixir 依赖 Erlang 内置的平衡树，API 略底层；命令式语言（Java/C++）需自己实现路径复制，footprint 最大。工程化 footprint 指"实现成本 + 生态支持 + 性能代价"：函数式语言零成本获得不可变，命令式语言需要额外工作。

footprint 差异源于语言对不可变的支持：函数式语言天然不可变，持久化零成本；命令式语言需手动路径复制。理解"语言范式决定持久化成本"是核心。

• Clojure 的 PersistentHashMap 基于 HAMT
• 5-bit 段 => 32-way 分支，bitmap 压缩节点
• 分支因子选择：深度浅、缓存友好、内存平衡

Clojure 的 PersistentHashMap 是 HAMT（Hash Array Mapped Trie）的实现：把键的 32 位 hash 按 5 bit 分段，每段作为一层中的分支索引，形成 32-way 分支的 trie。用 bitmap（32 位整数）标记节点中实际存在的子槽，配合紧凑子数组（popcount 定位）压缩存储。32-way 分支因子的选择是权衡：32 路扇出使树深度约 6-7 层（32^6 ≈ 1e9），查找/插入 O(log_32 n) 近似常数且缓存友好（32 个子槽可放一个缓存行内）；比 2-way 深得多但浅，比 64-way 缓存不友好。再加上路径复制，实现不可变 PersistentMap，更新共享路径、旧版本保留。它是 Clojure 默认 map 的核心，兼顾性能与持久化。

32 = 2^5 是深度与缓存/内存的平衡点：5-bit 段使 32 路扇出，深度浅、缓存友好、bitmap 压缩合理。理解"分支因子 = 2^段宽"与 bitmap 是 HAMT 设计的核心。

• PersistentQueue 用两个 PersistentList（front 与 rear）镜像
• 入队加 rear 尾，出队取 front 头，front 空时翻转 rear
• 均摊 O(1) 入队出队，不可变

Clojure 的 PersistentQueue 用两个不可变 PersistentList 实现：一个 front（队头）一个 rear（队尾，逆序）。入队（conj）把元素加到 rear 头部（O(1)）；出队（pop）从 front 头部取（O(1)）；当 front 为空时，把 rear 整体翻转成 front（O(n) 但均摊 O(1)）。这样既保持不可变（队列操作返回新队列，旧队列不变），又实现均摊 O(1) 的入队出队。这是"两栈实现队列"的持久化版本，front 与 rear 共享结构，翻转时产生新 front。工程上保证了 FIFO 语义与不可变，是 Clojure 默认队列。

核心是"front/rear 两栈镜像 + 惰性翻转"：入队 O(1) 到 rear，出队 O(1) 从 front，front 空时翻转 rear 为 front（均摊 O(1)）。两栈实现队列是经典技巧，持久化版本用共享 List 实现。

• gen_server 是 OTP 的通用服务器，状态放回调内
• 不可变状态 + 模式匹配更新
• ETS 作为外部可变存储（独立于进程状态）

Elixir 的 OTP gen_server 是通用服务器抽象：状态作为参数传入回调，回调返回新状态，每次更新产生新状态（函数式不可变）。状态管理遵循"不可变传递"：gen_server 的 handle_call/handle_cast 接收当前状态，返回 {:reply, reply, new_state} 或 {:noreply, new_state}，新状态替换旧状态。但大量/频繁的键值状态用不可变 map 较慢，工程上用 ETS（Erlang Term Storage）：ETS 是进程内存中的可变哈希表，独立于 gen_server 进程，可跨进程共享、读写 O(1)（表级），适合做缓存、路由表、计数器。取舍：gen_server 状态（不可变、单一进程、一致性）vs ETS（可变、共享、高效查询）。工程常结合：核心状态用 gen_server 不可变保证，高吞吐查询用 ETS。Persistent 数据结构（如 :maps、:gb_trees）用于 gen_server 内部状态。

核心是"不可变状态 vs 可变 ETS"的取舍。gen_server 状态不可变、单一进程、安全；ETS 可变、共享、高效。工程上按"一致性 vs 吞吐"选择。理解 OTP 状态传递与 ETS 定位是关键。

• Haskell 默认不可变，持久化 BST 天然支持
• Functor：fmap 映射结构
• Foldable：fold 遍历聚合

Haskell 是纯函数式语言，数据结构默认不可变，因此 Balanced BST（如红黑树、AVL）天然是持久化的：插入/删除返回新树，旧树不变。实现时用代数数据类型（ADT）定义树节点，用 Functor 类型类提供 fmap（对树中每个值应用函数，保持结构），用 Foldable 类型类提供 foldr/foldl（遍历树聚合，如求和、取最小），用 Show/Ord 等类型类约束。通过类型类，BST 的操作被抽象成标准接口，可组合进通用函数（如 Data.Foldable 的通用工具）。持久化 + 类型类是 Haskell 的惯用风格：函数的不可变保证历史版本，类型类保证多态复用。

Haskell 的持久化是"语言默认"而非额外努力。Functor/Foldable 类型类把"映射/遍历"抽象成通用接口，使 BST 可复用标准库函数。理解"不可变 + 类型类多态"是 Haskell 数据结构风格的核心。

• 跳表用多层链表 + 随机层数实现有序、O(log n) 操作
• LevelDB/RocksDB 用跳表作为 memtable（内存写缓冲）
• snapshot 通过不可变节点/版本实现

跳表（Skip List）用随机层数的多层链表实现有序结构，查找/插入/删除 O(log n) 期望。LevelDB/RocksDB 用跳表作为 memtable（内存中的写缓冲），因为跳表支持高效的顺序/随机读写、易实现并发与迭代。snapshot 的一致性通过不可变节点实现：跳表节点一旦写入即不可变，查询在固定版本上进行，配合 sequence number 保证快照读不被后续写影响；当 memtable 达到阈值时转成不可变 memtable（immutable memtable）再刷盘到 SST。Persistent 跳表在工程上指"共享节点 + 不可变 + 多版本读"，LevelDB 的 memtable 是"单写多读 + 快照"的典型。工程细节包括：随机层数生成、节点复用以避免重复分配、迭代器支持。

LevelDB 选择跳表做 memtable 因其"有序 + 并发友好 + 易实现快照"。snapshot 靠不可变节点 + sequence 实现。理解"跳表的随机层数与不可变节点"是工程细节核心。

• Racket 函数式不可变，持久化结构原生支持
• WScheme 是教学用 Scheme 实现
• 教学重概念清晰，工业重性能与生态

Racket（及教学用 WScheme/Scheme）是函数式语言，数据结构默认不可变，持久化结构（list、map、tree）原生支持，插入/删除返回新结构、旧结构保留。教学路径：用 WScheme/Scheme 讲清"不可变 + 递归 + 结构共享"的持久化概念，实现简单、易理解，适合演示路径复制与共享子树。工业路径：Racket 的标准库与生态提供高效持久化结构（如 sorted-map、持久 hash），并追求性能与内存优化，服务实际应用。对比是"教学重概念清晰、工业重性能/生态"：同一套不可变思想，教学用小而清晰的实现，工业用优化的库与工程化封装。

教学与工业的差异是"清晰 vs 性能"，但共享"不可变 + 结构共享"的持久化思想。理解 Racket 的不可变默认与两种路径的侧重，是掌握函数式持久化的关键。

• Scala 的不可变 Map 用 HAMT 变体
• 6-way 压缩节点存哈希片段
• 内存与性能权衡

Scala 标准库的不可变 HashMap（scala.collection.immutable.HashMap）基于 HAMT 的变体：内部用 6-way 压缩节点（每个节点存若干 5-bit 哈希片段对应的子项），相比 Clojure 的 32-way 用更紧凑的方式存储，权衡内存与查找深度。Cats 库的语法与类型类并不直接提供 HashMap 实现，但 Scala 的不可变 Map 天然持久化（更新返回新 Map、旧 Map 不变）。6-way 压缩节点指：节点中存键值的哈希片段、用紧凑数组存储子项，减少空槽浪费，代价是查找时需线性扫描节点内子项（小常数）。工程上 Scala 在 HAMT 基础上做压缩优化，兼顾持久化、内存与性能。

Scala 用 6-way 压缩节点在 HAMT 基础上优化内存：节点内紧凑存储、减少空槽。相比 32-way，6-way 更省内存但查找略慢。理解"分支因子与压缩"的权衡是关键。

• 对拍：用暴力正确程序 vs 高效程序对比输出
• 随机数据生成覆盖边界与常规
• 定位 bug 与回归验证

对拍（stress test / 对拍）是验证模板正确性的核心方法：写一个暴力但正确的小程序（或直接对已知正确解），生成随机数据，让暴力程序与高效模板（或新实现的算法）都跑，比较输出是否一致；不一致时用最小化的反例定位 bug。随机数据测试生成覆盖常规情况与边界（小规模、极端值、重复元素、空输入等），帮助暴露隐蔽错误。对拍抽取反例后，可缩到最小数据（如 n=1 的小规模）便于人工调试。在模板维护中，对拍用于：新模板上线前验证、重构后回归验证、以及针对特定算法（如字符串、几何、图论）的边界校验。作用在于"用大量随机用例自动验证正确性"，弥补人工推演的不足。

对拍是"用暴力验证高效"的工程方法：暴力正确但慢，高效快但易错，对拍让两者互证。随机数据 + 最小化反例是调试的关键。这是模板维护中保证正确性的标准手段。