简介面向竞赛编程的C算法模板库主要服务于需要快速套用可靠模板的算法竞赛选手、考研复试或日常刷题开发者。模板按功能分为基础算法、数学算法、数据结构与图论四大板块覆盖双指针、离散化、前缀和与差分、二分查找、单调栈、素数筛法、欧拉函数、组合数、扩展欧几里得、并查集、树状数组、线段树、树链剖分、可持久化线段树、莫队、弗洛伊德、迪杰斯特拉、最小生成树、最近公共祖先、二分图匹配、二-SAT等常见算法实现注重效率与大数据量场景内容预览中还涉及几何计算、多项式运算、后缀数组等进阶模板便于按需扩展。资源包共一百二十七个文件其中一百二十三个C源文件为主体可直接复制或包含到项目中另有二份Markdown说明、一份tex公式文档和一份pdf概述压缩包仅约七百三十KB轻量易用。目前已有七十六人学习浏览适合备赛冲刺、算法专题复习或建立个人模板库时参考。1. 一个 C 算法模板库源码包解决的是“需要时能立刻用上”的问题很多同学收到“基于C的算法模板库”的源码包时第一反应是把它当电子资料收藏。但这类包真正值钱的点不在“收藏”而在“可编译、可改造、可复用”你拿到的是源码而不是编译好的黑盒意味着线段树、最短路、字符串匹配这类高频算法可以很快接进自己的工程或刷题环境。我一般建议三类人认真对待这种包需要准备笔试面试、需要手撕算法的人工程里经常写图论或字符串逻辑的 C 开发者想看看别人怎么组织模板、怎么写边界处理的初学者。一个组织良好的模板库源码能让你从“我知道这个算法”直接跳到“我现在就能跑起来”。接下来我会按真实接入顺序拆解它的目录结构、接入流程、核心模板读法和常见坑。2. 拆开 C 算法模板库压缩包目录结构、代码风格与依赖约定2.1 先看顶层目录按“算法分类”组织是这类库的默认标准解压之后第一件事不是急着翻代码而是先扫一遍顶层结构。常见做法是把所有代码按用途分成几个大类目录基础的数组、链表、栈、队列、堆放在一个目录树相关二叉树、线段树、树状数组、平衡树单独放图论下的最短路、最小生成树、网络流、LCA 再放一起字符串的 KMP、AC 自动机、后缀数组另起一块数学相关的素数筛、快速幂、扩展欧几里得、组合数、FFT 也有独立目录。几乎每一个可用的算法模板库源码包都会在顶层放一个 README 或说明文档把每个文件对应的算法、复杂度、依赖关系列清楚。这类包的布局一般长这样不同包的命名略有出入但分层思路一致. ├── README.md # 使用说明、文件索引、编译要求 ├── basic/ # 基础数据结构与工具函数 │ ├── linked_list.hpp │ ├── stack_queue.hpp │ └── heap.hpp ├── tree/ # 树相关模板 │ ├── seg_tree.hpp │ ├── fenwick.hpp │ └── lca.hpp ├── graph/ # 图论模板 │ ├── dijkstra.hpp │ ├── mst.hpp │ └── maxflow.hpp ├── string/ # 字符串算法模板 │ ├── kmp.hpp │ ├── ac_automaton.hpp │ └── suffix_array.hpp ├── math/ # 数论与数学模板 │ ├── fast_pow.hpp │ ├── prime.hpp │ └── combinatorics.hpp └── tests/ # 部分包会携带的验证代码判断这个包值不值得接入之前先做两件小事第一打开 README 看它声明支持的 C 标准第二看 tests 目录里有没有对拍用例。自带测试的文件比只有实现的文件可靠得多因为模板的正确性要靠实际数据证明光看代码很难发现边界错误。如果一个包连 README 都没有还能用但你要做好逐个文件试错的准备。2.2 代码风格头文件为主、模板化、不依赖第三方库这类源码包和普通工程代码最大的风格差异在于几乎全部是“头文件 内联实现”很少有 .cpp 源文件。原因很直接——算法模板是给不同调用方复用的头文件形式意味着使用者只需要 include 就能拿到实现不必经历单独的编译链接而模板类、模板函数本来就要求定义对调用方可见放在头文件里是标准做法。第二个特征是全模板化。你会发现大多数数据结构都写成类模板或函数模板比如线段树用 T 做元素类型图论算法用邻接表的边权类型做参数这是为了让同一个实现能同时支持 int、long long 和自定义类型。代价是编译时报错信息会变得很长——这在同类库里可接受毕竟模板库追求的是泛用性。第三个特征是没有第三方依赖。组织良好、为“拷进新工程”设计的模板库不会要求你额外装 Boost 或某个专有库所有实现只依赖 C 标准库。这一点在接入时很重要如果你在一个不允许装额外依赖的团队环境里这种库可以直接进代码库而不引入新依赖风险。2.3 进入代码前先确认三件事编译标准、命名空间、数据规模假设开始读代码之前我会建议你先确认三个“接入层面的约束”。第一编译标准。这也是最大的接入分歧点。有的包为了兼容老旧环境用 C11 写有的包把 C17 特性用得很顺手少数前沿的包会要求 C20。先看 README 声明或直接在命令行里跑一句编译检查echo #include bits/stdc.h /tmp/std_test.cpp g -stdc17 /tmp/std_test.cpp -o /tmp/std_test echo C17 OK如果没有 bits/stdc.h就替换成实际要 include 的头文件来测。这一步能把后续大概率出现的“编译不过”问题提前暴露。第二命名空间。有些模板库把所有东西放在全局命名空间用一个前缀字母区分有些包把函数名写成大写下划线风格还有极少数把工具塞进 std 命名空间不推荐。如果你把两个模板库同时接进一个工程命名冲突概率不小具体处理方式在避坑章节展开。第三数据规模假设。模板库里若有静态数组、MAXN 这类写死的常量它一定隐含了对最大数据量的假设。这个数值适合竞赛场景通常压到 1e6 量级但不一定适合工程场景——如果你的输入范围超过上限问题不会在编译时报出来只会在数据最大的那次运行中爆发。3. 接入工程从解压到用最小用例跑通一个模板3.1 解压、确认文件完整性、跑一遍自带测试对 zip 包解压命令本身没什么可多说的但解压之后的几个习惯建议养成。首先确认压缩包里的文件是不是完整的用 unzip -t 校验然后扫一遍 README把它声明的编译命令、支持标准记下来。常见的完整流程是这样unzip -q 基于C的算法模板库.zip -d algolib cd algolib unzip -t 基于C的算法模板库.zip # 校验压缩包完整性 find . -maxdepth 2 -name *.hpp | head -20我在接入前还会做一件事把包内自带的 tests 目录如果有编译一次。大多数模板包的测试代码会声明算法后跑小规模数据再把结果和标准答案比较。这一跑能帮你确认“包里的代码在当前环境能编译、能运行”也给你一个基准结果——之后改造或裁剪模板时还要回到这组测试上回归。3.2 最小编译验证一个 demo 文件 一条编译命令如果包里没有测试代码或者只想验证某一个数据结构的可用性最快的方式是自己写一个演示文件。我一般会新建一个 demo.cpp 放在包目录外面避免改动包内原始文件、也方便清理。下面以验证一个线段树模板为例写一个能直接编译的玩具程序// demo.cpp #include cassert #include tree/seg_tree.hpp // 按实际目录调整 include 路径 int main() { // 假设模板库提供 SegTree构造函数为 SegTree(size, identity) SegTreeint seg(5, 0); // 区间置值和区间求和具体接口以包内声明为准 seg.update(0, 4, 3); // 区间 [0,4] 加上 3 seg.update(2, 2, 1); // 单点加 1 assert(seg.query(1, 3) 10); // [1,3] 区间和34310 return 0; }这里有一个前提写 demo 时你并不知道包里线段树的具体类名和接口签名上面只是演示调用方式。实际接入时要先打开 seg_tree.hpp 看类名叫什么、构造函数和 update/query 的参数顺序是什么。这是接任何模板库都必须经历的“接口对齐”过程省不掉。编译命令相应写为g -stdc17 -O2 -Wall -I./algolib demo.cpp -o demo ./demo echo basic template works这条命令里有几个参数值得解释。-stdc17 显式指定编译标准防止编译器默认标准低于模板库要求-O2 开启优化模板库里的内联模板在优化开启下才有合理性能-Wall 把警告全部打开接手初期看到的警告越多越说明这段代码和你环境的兼容性有待验证。-I./algolib 让 include 能直接找到包内目录。如果编译通过说明模板库基本可用如果报错去读第一个错误——模板实例化报错经常是一大串真正有价值的信息在最前面或最后面。3.3 收进 CMake 工程两种 include 组织方式大多数实际工程用 CMake 管理构建。把模板库收进来通常有两种方式。第一种是直接把模板库目录当成纯头文件目录挂进工程适合“库比较小、不想改任何东西”的阶段# CMakeLists.txt 片段 add_library(algolib INTERFACE) target_include_directories(algolib INTERFACE ${CMAKE_CURRENT_SOURCE_DIR}/algolib) target_link_libraries(your_target PRIVATE algolib)把带 INTERFACE 的 target 当“头文件集合”来链接是这类场景的标准做法因为模板库没有 .cpp 需要编译它只需要对外暴露 include 路径。第二种方式是把要用的模板文件复制进你自己工程的 include/algorithm 目录只保留实际用到的文件。这样做的收益是构建依赖面变小、仓库更清晰代价是模板库上游更新时需要手工同步。我个人更推荐第二种方式。模板库的价值在于“用的时候能看懂、能改”而不是“追新”。把用到的文件收编进自己工程加上自己的头文件保护宏和命名空间前缀它会慢慢长成一套属于你自己的工具集。4. 高频模板源码解读线段树、堆优化最短路与 KMP 的实现取舍4.1 线段树模板递归写法里的三个必要基础设施线段树是模板库里出场率最高的数据结构没有之一。多数库选择递归写法而不是迭代写法原因是递归写法思路直观区间修改、区间查询的覆盖逻辑更容易和题面一一对应。这类模板通常包含三个核心成员sum区间和、lazy懒标记用于区间更新的延后应用、以及 build/update/query 三个接口。一个典型的递归线段树实现骨架如下template typename T class SegTree { int n; std::vectorT sum, lazy; std::vectorchar has_lazy; // 标记节点是否有未下传的懒标记 void push_up(int p) { sum[p] sum[p 1] sum[p 1 | 1]; } void push_down(int p, int l, int r) { if (!has_lazy[p]) return; int mid (l r) 1; int lc p 1, rc p 1 | 1; sum[lc] lazy[p] * (mid - l 1); sum[rc] lazy[p] * (r - mid); lazy[lc] lazy[p]; lazy[rc] lazy[p]; has_lazy[lc] has_lazy[rc] 1; has_lazy[p] 0; lazy[p] T{}; } public: SegTree(int n) : n(n) { sum.assign(4 * n 4, T{}); lazy.assign(4 * n 4, T{}); has_lazy.assign(4 * n 4, 0); } void update(int ql, int qr, T val, int p, int l, int r) { if (ql l r qr) { sum[p] val * (r - l 1); lazy[p] val; has_lazy[p] 1; return; } push_down(p, l, r); int mid (l r) 1; if (ql mid) update(ql, qr, val, p 1, l, mid); if (qr mid) update(ql, qr, val, p 1 | 1, mid 1, r); push_up(p); } T query(int ql, int qr, int p, int l, int r) { if (ql l r qr) return sum[p]; push_down(p, l, r); int mid (l r) 1; T res T{}; if (ql mid) res res query(ql, qr, p 1, l, mid); if (qr mid) res res query(ql, qr, p 1 | 1, mid 1, r); return res; } };这个实现有几个必须留心的参数。sum 数组大小固定为 4*n这是递归线段树的经验值当 n 不是 2 的幂时二叉树节点数最多也到不了 4n所以开 4n 可以免去最后一层越界判断。另一个关键点在 push_down 和 has_lazy 的配合lazy[p] 只记录该节点区间整体增加了多少真正把增量传给子树要等到下次查询或更新覆盖到子区间时进行如果不单独记录“是否有未下传标记”单纯看 lazy[p] 是否为 0 会漏掉“下传过但增量为 0”的情况。接入线段树时最常翻车的位置是 update 和 query 的递归入口。上面写法要求调用方显式传四个参数 p1, l0, rn-1多数模板会再包一层公开函数补齐这些参数。接入时优先找这种包装函数找不到再手写递归入口否则每处调用都要拼一遍四个参数很容易在某个分支把 r 写成 n应当是 n-1而出问题。4.2 堆优化的 Dijkstra邻接表与 priority_queue 的配套写法最短路相关模板里堆优化的 Dijkstra 几乎每个库都有。实现相对固定vector 邻接表存图priority_queue 存当前距离节点编号每次取出未访问的最小距离节点做松弛。库之间的差异主要在两个地方邻接表用 vector 还是链式前向星以及 INF 的定义方式。最常用的是前者代码直观、调试时容易打印#include queue #include vector using PII std::pairlong long, int; // (dist, node) std::vectorlong long dijkstra( const std::vectorstd::vectorPII g, int start) { const long long INF (1LL 62); // 远大于所有可能路径长度 int n (int)g.size(); std::vectorlong long dist(n, INF); std::vectorchar vis(n, 0); std::priority_queuePII, std::vectorPII, std::greaterPII pq; dist[start] 0; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; // 过期条目直接跳过 vis[u] 1; for (auto [w, v] : g[u]) { // pair 顺序先距离再邻点 if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist; }拿到库里的 Dijkstra 时按四个点逐项核对。第一priority_queue 第三个模板参数必须配 greater 否则优先队列默认是大顶堆取出来的永远是最大距离节点算法直接退化成错误的贪心。第二vis 数组的作用只是跳过过期堆条目它不能替代 dist 的初始 INF 判断如果漏了 vis算法仍然正确但稠密图上会多跑大量重复松弛。第三INF 定值很关键1e18 或 1LL62 适合 long long 距离如果沿用 int 的 0x3f3f3f3f超过 20 亿的距离会被截断结果错得毫无规律。第四看 g 到底是 vectorvectorpairint,int 还是边数组这决定调用方要不要额外做一次构图转换。4.3 KMP 模板前缀函数实现与匹配入口的边界约定字符串算法里KMP 是典型的“短小、高频、边界多”模板。库里的 KMP 一般拆成两部分计算前缀函数的 build_pi 和用 pi 数组做匹配的 match。许多新手第一次看会困惑“为什么边界条件这么多”其实边界都集中在预处理函数里。一个常见写法// 返回 pattern 的 pi 数组pi[i] 表示 s[0..i] 最长相同真前后缀长度 std::vectorint build_pi(const std::string pat) { int m (int)pat.size(); std::vectorint pi(m, 0); for (int i 1; i m; i) { int j pi[i - 1]; while (j 0 pat[i] ! pat[j]) j pi[j - 1]; if (pat[i] pat[j]) j; pi[i] j; } return pi; } // 在 text 中查找 pattern返回所有匹配起点下标 std::vectorint kmp_match(const std::string text, const std::string pat) { auto pi build_pi(pat); std::vectorint pos; int j 0; for (int i 0; i (int)text.size(); i) { while (j 0 text[i] ! pat[j]) j pi[j - 1]; if (text[i] pat[j]) j; if (j (int)pat.size()) { pos.push_back(i - j 1); // i-j1 是匹配起点下标 j pi[j - 1]; // 允许重叠匹配时回退 } } return pos; }这里最容易被忽略的边界是 pi 数组下标语义和 while 回退条件的对齐。build_pi 中 i 从 1 开始pi[0] 恒为 0这是为了避免把单个字符算成“真前后缀”。匹配入口里 while 回退条件是 j 0 text[i] ! pat[j]——如果 j 已经等于 0 还是不匹配说明当前字符开不了头循环不必再做第二次回退直接让 i 前进。模板库里这两处如果有一处写错症状往往是“答案少一个匹配”或“死循环”用随机生成的小字符串对拍最容易暴露。接入 KMP 还有一个容易忽略的细节如果 pattern 为空字符串pi 长度为 0build_pi 循环不执行但 kmp_match 里匹配循环可能直接越界访问 pat[j]。成熟模板会在 build_pi 或匹配入口加显式判空如果你的包没加调用方要自己做一层防御。这个细节常被忽视但实际工程输入里空 pattern 并不罕见。5. 模板库接入避坑五个高频翻车现场与排查顺序5.1 链接报重复定义头文件里混进了非模板实现现象把两个模板文件 include 进同一个工程的多个 cpp链接阶段报 duplicate symbol。原因这个头文件里除了模板之外还写了一个普通全局函数的实现比如某个工具函数没有加 inline也没有放到 cpp。模板函数的多重包含没问题但普通函数的定义在多个 cpp 里各编译一份链接时就会产生重复符号。解决在头文件里给普通函数加上 inline 关键字或改写成函数模板如果是第三方源码不方便改就把这个文件拷贝到自己的目录再修改。这也是我坚持模板库要“收编进自己工程”而不是直接引用的原因之一。5.2 类模板参数推导报错默认编译标准太老现象一段模板代码看起来没问题编译却报 template argument deduction failed 或类似错误提示无法推断模板参数。原因代码里用了 C17 才支持的类模板参数推导CTAD比如直接写 SegTree seg(5, 0) 而不是 SegTree seg(5, 0)。如果你的编译器默认标准是 C14这段代码自然编不过。解决编译命令显式加 -stdc17或按模板库要求调整标准如果想保留旧标准就得把构造调用逐个改成显式类型参数。排查顺序有个技巧先看错误第一行文件路径是不是模板库头文件内部是的话说明头文件自身用了较新的语言特性再看编译器版本和默认标准。5.3 递归版算法在大数据上段错误栈空间默认只有 8MB现象用模板库里的递归 DFS、递归线段树处理 1e6 以上规模的数据运行到一半程序直接段错误。原因多数系统默认线程栈 8MB递归深度加深栈帧累积超过上限直接崩溃而模板库为了可读性优先采用递归写法。解决临时方案是在启动命令里增大栈上限Linux 下用 ulimit -s 65536 或 ulimit -s unlimited更工程化的做法是把递归实现替换成库内可能提供的迭代版本或自己改成显式栈。先确认“是栈溢出”而不是逻辑问题用 gdb 跑一次看崩溃栈是不是停在某个深度递归的调用链上。5.4 INF 取值不够大最短路算着算着距离被截断现象图论模板在大规模正权图上输出结果比预期小很多甚至出现负值但算法逻辑看起来没错。原因模板库里 INF 定义为 int 类型的 0x3f3f3f3f约 10.7 亿刚好大于大多数 int 场景的最大路径长度但调用方把边权和数据都换成了 long long路径长度轻松超过 10 亿时dist 数组初始化的 INF 无法承载更大的数值累加溢出变成负数或截断值。解决把 INF 换成语义更安全的 (1LL 62)并且接入第一步就检查类型一致性数据元素类型、dist 数组类型、INF 类型三者必须配套。这是模板库里“类型一换常数必换”的典型教训。5.5 全局数组 MAXN 越界小数据没问题大数据莫名诡异现象模板库里用静态全局数组 char vis[MAXN]、int st[MAXN] 之类的写法数据量超过 MAXN 后程序表现时好时坏改一下无关代码就多跑一轮崩溃点完全随机。原因数组越界是未定义行为编译器不保证报错越界写可能恰好没踩到关键内存也可能踩坏堆结构行为完全取决于内存布局。解决凡是用到模板库里全局数组的地方优先改成 std::vector 动态分配把 MAXN 替换成实际 n 传入如果确实需要固定上限就在读取输入后立即做 if (n MAXN) 检查并明确报错而不是让程序带着隐患跑。排查这类问题最有效的工具是编译时加 -fsanitizeaddress它能在越界写的那一刻直接定位到代码行。6. 把算法模板库改造成自己的工具箱压测、裁剪与积累习惯6.1 半小时压测模板不是黑匣子跑过对拍才算数接进来的模板不能只在 demo 上跑一次就放心用。我的习惯是写一个几十行的随机数据生成器把模板输出和另一个暴力实现输出对拍跑几千组随机数据不一致就停下来看差距。生成器和对照组都能很快写完被测程序就是你的模板调用代码。用 bash 循环驱动对拍for i in $(seq 1 500); do ./gen in.txt ./brute in.txt ans.txt ./solve in.txt out.txt if ! diff -q ans.txt out.txt /dev/null; then echo mismatch at case $i; break fi donegen 生成随机输入brute 是暴力实现solve 是模板调用版本。一旦出现 mismatch就把这组输入存下来留着调试。模板库的代码往往为了通用性牺牲直观性边界条件下的行为只有对拍能验证这个习惯能帮你把“能用”变成“确定能用”。6.2 按需裁剪只留高频文件顺便统一命名风格模板库每个文件都收进来会让工程 include 目录越来越乱。我会定期做一次裁剪把近三个月真正用过的模板保留其余先移到 archive 目录同时把文件内命名空间从库自带前缀统一成工程内部前缀。每裁剪一个文件前先跑一遍它对应的测试确认这个模板没有被别的文件反向依赖——剪掉一个看似孤立的头文件结果另一个模板在编译时少了辅助函数这类事我碰过不止一次。6.3 每次新增模板都留下三行注释我给自己定的规范是每个进入工程的新模板必须带三行注释——输入规模假设、时间复杂度的常量因子、边界行为说明。比如 KMP 模板写“空 pattern 不匹配任何位置、重叠匹配返回全部起点”最短路模板写“INF 按 long long 路径长度取 1LL62”。这三行注释看着简单但能救命几个月后调一个线上问题突然要用到模板的某种边界行为注释直接告诉你答案不用再把源码从头读一遍。这类模板库的源码本身是可贵的但你真正积累下来的是解读、改造、压测这套流程。现在我已经把目录结构、接入方式、核心模板和常见坑都过了一遍剩下的就需要你手头的编译器替你验证了。希望帮到你。本文还有配套的精品资源点击获取