简介一套面向竞赛编程的算法模板库适合算法竞赛选手、考研与面试准备者以及需要在复杂场景下快速实现高效算法的开发者。库内按专题系统组织覆盖基础算法、数学算法、数据结构与图论四大板块基础部分包含双指针、离散化、前缀和与差分、二分查找、单调栈与单调队列数学部分涵盖素数筛法、欧拉函数、组合数、扩展欧几里得、线性同余方程、容斥原理、高斯消元、矩阵乘法、莫比乌斯反演、BSGS与FFT数据结构部分支持并查集、稀疏表、Trie、树状数组、线段树、树链剖分、可持久化线段树与莫队图论部分则提供Floyd、Bellman-Ford、SPFA、Dijkstra、差分约束、最小生成树、LCA、二分图匹配、强连通分量与2-SAT等算法模板。资源包共127个文件以123个C源码文件为主体另有2个Markdown说明、1个TeX文档和1个PDF文档便于查阅原理与使用说明压缩后仅730KB轻量紧凑。目前已有76人浏览学习适合希望体系化整理竞赛模板、按需查阅和二次开发的读者。1. 基于C的算法模板库这份源码包到底装了些什么做竞赛编程或者刷题强度上来之后最烦的不是题目本身而是每次都要重敲那几十行基础代码——比如线段树、FFT、SCC 缩点。这份基于 C 的算法模板库解压后是一批互相独立的 .cpp 文件每个文件对应一类算法或数据结构像 geo-jls-template.cpp、Poly.cpp、SegTree.cpp、BipartiteMatch2.cpp 这种命名摆明了就是给人「要用哪个拿哪个」的。它不是工程框架也不是教学课件而是一套可以整段复制进代码编辑器的板子库。适合参加 ACM 这类竞赛的人、刷算法题库的从业者也适合需要快速验证图论或数学算法思路的开发者——抄板子、改参数、跑通验证是这套资源最直接的用法。2. 先从数学和基础算法说起素数筛、FFT、组合数与高精度预处理2.1 素数筛与质因数分解线性筛和埃筛怎么选打开这套模板里数学相关的文件第一个值得细看的是素数筛与质因数分解部分。常见实现有两种埃氏筛写起来短但遇到 1e7 量级的数据就有明显的重复标记开销线性筛每个合数只被它的最小质因子筛掉一次常数虽然略高但胜在复杂度稳定在 O(n)。我一般在比赛里直接上线性筛因为埃筛看似简单实际在多次查询区间素数个数时吃亏。const int N 1e7 5; int primes[N], cnt; bool isComp[N]; void linearSieve(int n) { for (int i 2; i n; i) { if (!isComp[i]) primes[cnt] i; for (int j 0; j cnt 1LL * i * primes[j] n; j) { isComp[i * primes[j]] true; if (i % primes[j] 0) break; } } }这段代码的要点在于if (i % primes[j] 0) break;正是这行保证了每个合数只被最小质因子筛掉。参数N是筛的上限实际使用时按题目给定的 n 调整cnt 用来记录素数个数。质因数分解的模板通常配合这个筛子做预先生成素数表然后逐质数除尽——注意除尽要用 while 而不是 if否则会漏掉幂次。2.2 FFT 与多项式乘法精度、长度和补零的规则Poly.cpp 和 FFT 相关的模板在这套库里属于重量级成员。FFT 解决的是两个多项式乘法从 O(n^2) 降到 O(n log n) 的问题但它的前置条件很苛刻序列长度必须是 2 的幂。所以模板里第一步永远是计算一个lim把所有系数数组补零到大于等于两倍长度的 2 次幂。void fft(vectorComplex a, bool invert) { int n a.size(); for (int i 1, j 0; i n; i) { int bit n 1; for (; j bit; bit 1) j ^ bit; j ^ bit; if (i j) swap(a[i], a[j]); } for (int len 2; len n; len 1) { double ang 2 * M_PI / len * (invert ? -1 : 1); Complex wlen(cos(ang), sin(ang)); for (int i 0; i n; i len) { Complex w(1); for (int j 0; j len / 2; j) { Complex u a[i j], v a[i j len / 2] * w; a[i j] u v; a[i j len / 2] u - v; w * wlen; } } } if (invert) for (auto x : a) x / n; }位逆序置换那一段是很多新手抄板子时容易看懵的地方——它不是在排序而是在把下标按二进制位翻转后的顺序重排保证迭代时能按蝶形运算合并。invert参数控制正变换还是逆变换逆变换最后要除以 n这个容易忘。实际用的时候系数可能是浮点乘完取整要加 0.5 而不是直接 int 强转否则负数和精度误差会让你翻车。2.3 组合数与欧拉函数预处理阶乘和逆元是关键组合数模板的核心不是组合公式本身而是阶乘和逆元的预处理。如果每算一次 C(n, k) 都现场推阶乘复杂度直接爆炸。正确做法是提前开一个 fac 数组存阶乘再开一个 ifac 存逆元这样每次查询就是 O(1)。long long fac[N], ifac[N]; long long modPow(long long a, long long b, long long mod) { long long res 1; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; } void initComb(int n, long long mod) { fac[0] 1; for (int i 1; i n; i) fac[i] fac[i - 1] * i % mod; ifac[n] modPow(fac[n], mod - 2, mod); for (int i n - 1; i 0; --i) ifac[i] ifac[i 1] * (i 1) % mod; } long long C(int n, int k, long long mod) { if (k 0 || k n) return 0; return fac[n] * ifac[k] % mod * ifac[n - k] % mod; }这段要求模数必须是质数因为用了费马小定理求逆元。如果模数不是质数这套板子不能直接套得换扩展欧几里得或者用其他方式。欧拉函数模板和这个搭配使用很常见因为有些组合问题会先对 n 做质因数分解再用欧拉函数做容斥。注意预处理的上限n和实际查询的上限一致不然数组越界是小事结果错得莫名其妙才头疼。3. 数据结构模板实战线段树、树状数组、Sparse Table 与莫队3.1 线段树区间修改区间查询的模板骨架SegTree.cpp 是这套库里被复制频次最高的文件之一。线段树的本质是把区间信息存进一个完全二叉树用空间换查询和修改的时间。模板里最常见的形态是维护区间和的 lazy 版本同时支持区间更新和区间求和。struct SegTree { vectorlong long tree, lazy; int n; SegTree(int n) : n(n), tree(4 * n 5), lazy(4 * n 5) {} void push(int p, int l, int r) { if (lazy[p] 0) return; int mid (l r) 1; tree[p 1] lazy[p] * (mid - l 1); tree[p 1 | 1] lazy[p] * (r - mid); lazy[p 1] lazy[p]; lazy[p 1 | 1] lazy[p]; lazy[p] 0; } void update(int p, int l, int r, int ql, int qr, long long val) { if (ql l r qr) { tree[p] val * (r - l 1); lazy[p] val; return; } push(p, l, r); int mid (l r) 1; if (ql mid) update(p 1, l, mid, ql, qr, val); if (qr mid) update(p 1 | 1, mid 1, r, ql, qr, val); tree[p] tree[p 1] tree[p 1 | 1]; } };这里的核心是push函数它把父节点的懒标记下放到子节点。很多人抄完线段树发现区间查询结果不对多半是push调用时机错了——必须在递归进入子树之前下放否则子节点的值用的是旧的 lazy。4 * n 5是保守估计实际上 4 倍空间基本够用但如果你写的是动态开点版本这个数字就不适用了。线段树能处理的远不止区间和把改成max或min配合不同的合并逻辑就变成区间最值问题模板。3.2 树状数组单点修改前缀查询的轻量级替代树状数组和线段树解决的是同一类问题里的子集但树状数组的常数小、代码短不是所有区间操作都能用它可凡是能用前缀和性质表达的操作我都优先用树状数组。fenwick3.cpp 这个文件名暗示它可能不只是裸的树状数组而是带三维偏序或某种扩展的版本。struct Fenwick { int n; vectorint bit; Fenwick(int n) : n(n), bit(n 1) {} void add(int idx, int delta) { for (; idx n; idx idx -idx) bit[idx] delta; } int sum(int idx) { int res 0; for (; idx 0; idx - idx -idx) res bit[idx]; return res; } };idx -idx是树状数组的灵魂它取出 idx 最低位的 1决定当前节点该往哪个方向跳。单点更新和前缀查询的复杂度都是 O(log n)。如果要把单点修改换成区间修改得用差分思想把问题转成两个树状数组这个在 fenwick3.cpp 里应该有对应实现。树状数组不能像线段树那样随便做区间最值除非操作满足可逆性否则别硬套。3.3 Sparse Table 与莫队离线查询和 RMQ 的两把快刀Sparse Table 解决的是静态 RMQ 问题——数组不修改反复查询区间最值。预处理 O(n log n)单次查询 O(1)靠的是把区间拆成两个可重叠的幂次段。莫队则是对离线区间查询做分块排序把查询顺序重新排列来减少指针移动总距离。这两个模板在这套库里同时出现说明作者对「数组不变、查询多」和「数组可改但可离线」两类场景都给了对应方案。莫队排序的 key 是第一关键字按左端点分块第二关键字根据块编号奇偶决定右端点升降序这个细节能省不少常数。struct Query { int l, r, id, block; bool operator(const Query other) const { if (block ! other.block) return block other.block; if (block 1) return r other.r; return r other.r; } };莫队的分块大小一般取 sqrt(n)但数据量特别大时可以调成 n 的三分之二次方。块编号奇偶优化的原理是蛇形走位减少右端点指针来回跑的次数。这套板子对新手最大的坑是莫队要求操作只增不减或者能回退如果题目需要删除维护就得保证维护的数据结构支持反操作。4. 图论算法模板拆解最短路、最小生成树、网络流与 SCC/2SAT4.1 Dijkstra 与 SPFA堆优化和负环判断的边界图论部分文件最多BipartiteMatch2.cpp、SA.cpp、twoSAT.cpp 各管一摊。最短路模板里 Dijkstra 的堆优化是必背项它的适用前提是边权非负。具体做法是用优先队列维护当前距离最小的节点每弹出一个节点就松弛它的所有出边。SPFA 在竞赛里的地位比较尴尬——平均表现不错但最坏能卡成 O(VE)它的存在意义主要是判断负环和应付某些特殊图。using PII pairint, int; void dijkstra(int s, vectorvectorPII g, vectorint dist) { priority_queuePII, vectorPII, greaterPII pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : g[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }if (d dist[u]) continue;是堆优化 Dijkstra 的正确性关键——这判断能跳过那些已经被更好方案替代的旧节点。如果删掉它算法不会错但会变慢。SPFA 判断负环的做法是记录每个节点入队的次数超过 n 就说明存在负环。注意这里的 n 是节点数不是边数边界条件写错会漏判。分层图最短路模板的思路是把状态拆成多个层每个层代表用了几次特殊机会然后层间用边连接这在本套模板里有体现。4.2 并查集与最小生成树Kruskal 的排序细节并查集在图论里是基建最小生成树的 Kruskal 算法直接建在它上面。流程是先把所有边按权值排序然后逐条尝试如果边的两个端点还不连通就合并并累加答案。关键代码是路径压缩加按秩合并。struct DSU { vectorint fa, sz; DSU(int n) : fa(n), sz(n, 1) { iota(fa.begin(), fa.end(), 0); } int find(int x) { while (fa[x] ! x) { fa[x] fa[fa[x]]; x fa[x]; } return x; } bool unite(int a, int b) { a find(a); b find(b); if (a b) return false; if (sz[a] sz[b]) swap(a, b); fa[b] a; sz[a] sz[b]; return true; } };find里的路径压缩把搜索路径上的每个节点都直接挂到根上复杂度接近阿克曼函数的反函数。unite返回 false 说明两个节点原本就联通Kruskal 里遇到这种情况直接忽略这条边。按秩合并不是必须的但加上之后最坏复杂度更稳。这套模板里的 DSU 文件虽然没列全但并查集几乎是每个图论文件的前置依赖建议单独抽出来存成一个公共头文件。4.3 二分图匹配、SCC 与 2SAT从模板到建模思路BipartiteMatch2.cpp 是匈牙利算法的实现解决的是一个集合中的元素能否在另一集合中找到唯一配对的问题。核心是递归尝试调整已有匹配腾出位置。SCC 强连通分量用 Tarjan 算法SCC.cpp 里维护了 dfn 和 low 两个数组加上一个栈来记录当前强连通分量内的节点。SCC 搞完就顺手能缩点把有向图变成 DAG有些题目需要缩点后做拓扑。twoSAT.cpp 是 2SAT 判定本质是把每个变量拆成两个状态用蕴含关系建边然后跑 SCC看每个变量的两个状态是否在同一个强连通分量里——如果在就无解。// 2SAT 判定核心 for (int i 0; i n; i) { if (sccId[i 1] sccId[i 1 | 1]) { // 无解 } }2SAT 的建边规则是「一个条件推出另一个」必须保证逻辑逆否也建了边漏一条直接错。SCC 的编号顺序还有一个作用tarjan 跑完后按反拓扑序得到的缩点顺序可以直接用于拓扑 DP。二分图匹配输出具体方案时注意存的是 match 数组方向别搞反——match[v] 是右侧节点 v 匹配到的左侧节点遍历右侧输出更直观。5. 避坑指南与常见问题排查实战中高频翻车点实录5.1 整数溢出模运算和乘法链上最容易爆的地方竞赛里数据范围常给到 1e18中间结果却可以轻松溢出。我见过最典型的翻车是在组合数的连乘里fac[i] fac[i - 1] * i % mod如果 i 是 int 而 fac 是 long long 还好但如果是int * int赋值给 long long溢出已经发生了。另一个高发点在快速幂a a * a % mod里的 a 是 long long两个 long long 相乘可能达到 1e36直接 UB。处理办法就是乘法前先判断或者使用__int128模板库里有些乘法可以改成龟速乘但大多数情况下还是把中间变量类型换成long long再乘。提示凡遇两数相乘再取模先确认两个操作数的类型和取值范围必要时用__int128过渡别指望强制转换救你。5.2 数组越界和 REvector 下标与预分配空间的错位很多 .cpp 模板喜欢用vectorint g[N]这种静态数组形式配合题目给的 n但若实际输入的边数超过预设 N运行直接崩溃。我建议把图论模板统一改成vectorvectorint g(n)动态扩容虽然慢一点点但不会越界。线段树的4*n空间在极端递归深度下也可能溢出——当 n 不是 2 的幂且更新频繁时某些实现会访问到接近 4n 的末尾开成4 * n 10是保险做法。5.3 浮点精度FFT 和几何模板的精度陷阱FFT 用 double 存储中间结果但数据一大精度就会掉。当系数超过 1e9 或长度超过 1e5 时卷积结果可能错几位整数。排查方法是用一个小规模样例手算对比若对不上优先怀疑精度问题——可以尝试换成 long double或改用 NTT数论变换用模数代替浮点代价是模数必须是质数且原根存在。几何模板里判断点是否在线段上时用叉积和点积结合的写法避免浮点相等判断统一用 eps 比较。geo-jls-template.cpp 这个文件名暗示了这套库在几何上也有专门实现注意所有几何模板几乎都要先定义const double eps 1e-8;。5.4 递归深度DFS 和 Tarjan 在稠密图上的爆栈Tarjan、匈牙利算法、二分图匹配都是递归实现遇到极端数据比如一条长链递归深度可能达到 1e6默认栈空间直接爆。解决办法有两种一是把递归改成显式栈的迭代版本二是编译时加-Wl,-stack,67108864这类参数扩大栈容量。比赛环境不一定能修改编译选项所以在模板注释里标明哪些函数递归深度风险高用时心里有数。SCC 的 Tarjan 尤其容易踩这个坑因为它对每个节点做一次 DFS图是稠密时递归层数不可控。5.5 莫队排序与块大小的玄学调参莫队的正确性不依赖块大小但复杂度依赖。块大小取 sqrt(n) 是默认实际发现右端点排序用奇偶优化后块大小取n / sqrt(m)反而更快其中 m 是查询数。若模板里硬编码了sqrt(n)建议改成传入参数。还有一个常见错误莫队的add和remove顺序必须保证维护的状态始终合法。如果先 remove 再 add可能中间状态读取到空数据计算答案时炸掉。6. 把模板库改造成自己的高速板子封装验证与代码折叠的实操习惯先别急着把 .cpp 文件全复制进一个头文件——我建议按数据类型分文件整理建一个template/目录数学、数据结构、图论各放一个子目录文件命名带功能标签。然后对每个模板写一段无注释的最小样例跑一遍用-O2编译开启优化看是否有警告和运行时错误。验证通过后在文件头部加一行简短说明标注适用数据范围、复杂度、坑点比如「SegTree: 区间加/求和, O(log n), n1e5 时数组开 4n」这样的注释半年后再翻也不会陌生。接着做封装。把每个模板类的方法名统一成build/update/query把输入输出方式也统一——比赛时切换题目只需改主函数模板本身可以做到零改动。如果模板库里某个实现用scanf/printf建议保留因为竞赛环境下cin虽快但没有scanf那种确定性。封装完可以用一个简单的题目脚本验证写一个test.cpp把模板头文件和若干测试用例直接 include每次改动后跑一遍暴力对拍用随机小数据对照朴素实现。这套流程虽然多花十分钟但能让你在赛场上少花一小时调 bug。代码折叠这个习惯也值得养成。模板文件动辄几百行用编辑器折叠功能把每个类或函数缩成一个标题行查找时按文件名定位改参数时展开对应函数。注意别把折叠状态的代码直接复制进提交文件——很多编辑器会把折叠部分省略掉导致粘贴出来的代码少了关键函数。我一般把模板库当草稿纸用真提交时再手动挑需要的类复制并且复制后立刻全文搜索一遍关键函数名确认没有遗漏。我自己的习惯是每次赛前把模板库整体过一遍编译确认所有文件在当前编译环境下都能通过。这个习惯救过我很多次——有一次某次比赛环境用的是老版本编译器不支持结构化绑定我的 Dijkstra 模板里全是auto [d, u]编译直接报错。从那以后我每次拿到新环境第一件事就是把所有模板用该环境编译一遍而不是在现场对着报错一行行改。希望帮到你。本文还有配套的精品资源点击获取
简介一套面向竞赛编程的算法模板库适合算法竞赛选手、考研与面试准备者以及需要在复杂场景下快速实现高效算法的开发者。库内按专题系统组织覆盖基础算法、数学算法、数据结构与图论四大板块基础部分包含双指针、离散化、前缀和与差分、二分查找、单调栈与单调队列数学部分涵盖素数筛法、欧拉函数、组合数、扩展欧几里得、线性同余方程、容斥原理、高斯消元、矩阵乘法、莫比乌斯反演、BSGS与FFT数据结构部分支持并查集、稀疏表、Trie、树状数组、线段树、树链剖分、可持久化线段树与莫队图论部分则提供Floyd、Bellman-Ford、SPFA、Dijkstra、差分约束、最小生成树、LCA、二分图匹配、强连通分量与2-SAT等算法模板。资源包共127个文件以123个C源码文件为主体另有2个Markdown说明、1个TeX文档和1个PDF文档便于查阅原理与使用说明压缩后仅730KB轻量紧凑。目前已有76人浏览学习适合希望体系化整理竞赛模板、按需查阅和二次开发的读者。1. 基于C的算法模板库这份源码包到底装了些什么做竞赛编程或者刷题强度上来之后最烦的不是题目本身而是每次都要重敲那几十行基础代码——比如线段树、FFT、SCC 缩点。这份基于 C 的算法模板库解压后是一批互相独立的 .cpp 文件每个文件对应一类算法或数据结构像 geo-jls-template.cpp、Poly.cpp、SegTree.cpp、BipartiteMatch2.cpp 这种命名摆明了就是给人「要用哪个拿哪个」的。它不是工程框架也不是教学课件而是一套可以整段复制进代码编辑器的板子库。适合参加 ACM 这类竞赛的人、刷算法题库的从业者也适合需要快速验证图论或数学算法思路的开发者——抄板子、改参数、跑通验证是这套资源最直接的用法。2. 先从数学和基础算法说起素数筛、FFT、组合数与高精度预处理2.1 素数筛与质因数分解线性筛和埃筛怎么选打开这套模板里数学相关的文件第一个值得细看的是素数筛与质因数分解部分。常见实现有两种埃氏筛写起来短但遇到 1e7 量级的数据就有明显的重复标记开销线性筛每个合数只被它的最小质因子筛掉一次常数虽然略高但胜在复杂度稳定在 O(n)。我一般在比赛里直接上线性筛因为埃筛看似简单实际在多次查询区间素数个数时吃亏。const int N 1e7 5; int primes[N], cnt; bool isComp[N]; void linearSieve(int n) { for (int i 2; i n; i) { if (!isComp[i]) primes[cnt] i; for (int j 0; j cnt 1LL * i * primes[j] n; j) { isComp[i * primes[j]] true; if (i % primes[j] 0) break; } } }这段代码的要点在于if (i % primes[j] 0) break;正是这行保证了每个合数只被最小质因子筛掉。参数N是筛的上限实际使用时按题目给定的 n 调整cnt 用来记录素数个数。质因数分解的模板通常配合这个筛子做预先生成素数表然后逐质数除尽——注意除尽要用 while 而不是 if否则会漏掉幂次。2.2 FFT 与多项式乘法精度、长度和补零的规则Poly.cpp 和 FFT 相关的模板在这套库里属于重量级成员。FFT 解决的是两个多项式乘法从 O(n^2) 降到 O(n log n) 的问题但它的前置条件很苛刻序列长度必须是 2 的幂。所以模板里第一步永远是计算一个lim把所有系数数组补零到大于等于两倍长度的 2 次幂。void fft(vectorComplex a, bool invert) { int n a.size(); for (int i 1, j 0; i n; i) { int bit n 1; for (; j bit; bit 1) j ^ bit; j ^ bit; if (i j) swap(a[i], a[j]); } for (int len 2; len n; len 1) { double ang 2 * M_PI / len * (invert ? -1 : 1); Complex wlen(cos(ang), sin(ang)); for (int i 0; i n; i len) { Complex w(1); for (int j 0; j len / 2; j) { Complex u a[i j], v a[i j len / 2] * w; a[i j] u v; a[i j len / 2] u - v; w * wlen; } } } if (invert) for (auto x : a) x / n; }位逆序置换那一段是很多新手抄板子时容易看懵的地方——它不是在排序而是在把下标按二进制位翻转后的顺序重排保证迭代时能按蝶形运算合并。invert参数控制正变换还是逆变换逆变换最后要除以 n这个容易忘。实际用的时候系数可能是浮点乘完取整要加 0.5 而不是直接 int 强转否则负数和精度误差会让你翻车。2.3 组合数与欧拉函数预处理阶乘和逆元是关键组合数模板的核心不是组合公式本身而是阶乘和逆元的预处理。如果每算一次 C(n, k) 都现场推阶乘复杂度直接爆炸。正确做法是提前开一个 fac 数组存阶乘再开一个 ifac 存逆元这样每次查询就是 O(1)。long long fac[N], ifac[N]; long long modPow(long long a, long long b, long long mod) { long long res 1; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; } void initComb(int n, long long mod) { fac[0] 1; for (int i 1; i n; i) fac[i] fac[i - 1] * i % mod; ifac[n] modPow(fac[n], mod - 2, mod); for (int i n - 1; i 0; --i) ifac[i] ifac[i 1] * (i 1) % mod; } long long C(int n, int k, long long mod) { if (k 0 || k n) return 0; return fac[n] * ifac[k] % mod * ifac[n - k] % mod; }这段要求模数必须是质数因为用了费马小定理求逆元。如果模数不是质数这套板子不能直接套得换扩展欧几里得或者用其他方式。欧拉函数模板和这个搭配使用很常见因为有些组合问题会先对 n 做质因数分解再用欧拉函数做容斥。注意预处理的上限n和实际查询的上限一致不然数组越界是小事结果错得莫名其妙才头疼。3. 数据结构模板实战线段树、树状数组、Sparse Table 与莫队3.1 线段树区间修改区间查询的模板骨架SegTree.cpp 是这套库里被复制频次最高的文件之一。线段树的本质是把区间信息存进一个完全二叉树用空间换查询和修改的时间。模板里最常见的形态是维护区间和的 lazy 版本同时支持区间更新和区间求和。struct SegTree { vectorlong long tree, lazy; int n; SegTree(int n) : n(n), tree(4 * n 5), lazy(4 * n 5) {} void push(int p, int l, int r) { if (lazy[p] 0) return; int mid (l r) 1; tree[p 1] lazy[p] * (mid - l 1); tree[p 1 | 1] lazy[p] * (r - mid); lazy[p 1] lazy[p]; lazy[p 1 | 1] lazy[p]; lazy[p] 0; } void update(int p, int l, int r, int ql, int qr, long long val) { if (ql l r qr) { tree[p] val * (r - l 1); lazy[p] val; return; } push(p, l, r); int mid (l r) 1; if (ql mid) update(p 1, l, mid, ql, qr, val); if (qr mid) update(p 1 | 1, mid 1, r, ql, qr, val); tree[p] tree[p 1] tree[p 1 | 1]; } };这里的核心是push函数它把父节点的懒标记下放到子节点。很多人抄完线段树发现区间查询结果不对多半是push调用时机错了——必须在递归进入子树之前下放否则子节点的值用的是旧的 lazy。4 * n 5是保守估计实际上 4 倍空间基本够用但如果你写的是动态开点版本这个数字就不适用了。线段树能处理的远不止区间和把改成max或min配合不同的合并逻辑就变成区间最值问题模板。3.2 树状数组单点修改前缀查询的轻量级替代树状数组和线段树解决的是同一类问题里的子集但树状数组的常数小、代码短不是所有区间操作都能用它可凡是能用前缀和性质表达的操作我都优先用树状数组。fenwick3.cpp 这个文件名暗示它可能不只是裸的树状数组而是带三维偏序或某种扩展的版本。struct Fenwick { int n; vectorint bit; Fenwick(int n) : n(n), bit(n 1) {} void add(int idx, int delta) { for (; idx n; idx idx -idx) bit[idx] delta; } int sum(int idx) { int res 0; for (; idx 0; idx - idx -idx) res bit[idx]; return res; } };idx -idx是树状数组的灵魂它取出 idx 最低位的 1决定当前节点该往哪个方向跳。单点更新和前缀查询的复杂度都是 O(log n)。如果要把单点修改换成区间修改得用差分思想把问题转成两个树状数组这个在 fenwick3.cpp 里应该有对应实现。树状数组不能像线段树那样随便做区间最值除非操作满足可逆性否则别硬套。3.3 Sparse Table 与莫队离线查询和 RMQ 的两把快刀Sparse Table 解决的是静态 RMQ 问题——数组不修改反复查询区间最值。预处理 O(n log n)单次查询 O(1)靠的是把区间拆成两个可重叠的幂次段。莫队则是对离线区间查询做分块排序把查询顺序重新排列来减少指针移动总距离。这两个模板在这套库里同时出现说明作者对「数组不变、查询多」和「数组可改但可离线」两类场景都给了对应方案。莫队排序的 key 是第一关键字按左端点分块第二关键字根据块编号奇偶决定右端点升降序这个细节能省不少常数。struct Query { int l, r, id, block; bool operator(const Query other) const { if (block ! other.block) return block other.block; if (block 1) return r other.r; return r other.r; } };莫队的分块大小一般取 sqrt(n)但数据量特别大时可以调成 n 的三分之二次方。块编号奇偶优化的原理是蛇形走位减少右端点指针来回跑的次数。这套板子对新手最大的坑是莫队要求操作只增不减或者能回退如果题目需要删除维护就得保证维护的数据结构支持反操作。4. 图论算法模板拆解最短路、最小生成树、网络流与 SCC/2SAT4.1 Dijkstra 与 SPFA堆优化和负环判断的边界图论部分文件最多BipartiteMatch2.cpp、SA.cpp、twoSAT.cpp 各管一摊。最短路模板里 Dijkstra 的堆优化是必背项它的适用前提是边权非负。具体做法是用优先队列维护当前距离最小的节点每弹出一个节点就松弛它的所有出边。SPFA 在竞赛里的地位比较尴尬——平均表现不错但最坏能卡成 O(VE)它的存在意义主要是判断负环和应付某些特殊图。using PII pairint, int; void dijkstra(int s, vectorvectorPII g, vectorint dist) { priority_queuePII, vectorPII, greaterPII pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : g[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }if (d dist[u]) continue;是堆优化 Dijkstra 的正确性关键——这判断能跳过那些已经被更好方案替代的旧节点。如果删掉它算法不会错但会变慢。SPFA 判断负环的做法是记录每个节点入队的次数超过 n 就说明存在负环。注意这里的 n 是节点数不是边数边界条件写错会漏判。分层图最短路模板的思路是把状态拆成多个层每个层代表用了几次特殊机会然后层间用边连接这在本套模板里有体现。4.2 并查集与最小生成树Kruskal 的排序细节并查集在图论里是基建最小生成树的 Kruskal 算法直接建在它上面。流程是先把所有边按权值排序然后逐条尝试如果边的两个端点还不连通就合并并累加答案。关键代码是路径压缩加按秩合并。struct DSU { vectorint fa, sz; DSU(int n) : fa(n), sz(n, 1) { iota(fa.begin(), fa.end(), 0); } int find(int x) { while (fa[x] ! x) { fa[x] fa[fa[x]]; x fa[x]; } return x; } bool unite(int a, int b) { a find(a); b find(b); if (a b) return false; if (sz[a] sz[b]) swap(a, b); fa[b] a; sz[a] sz[b]; return true; } };find里的路径压缩把搜索路径上的每个节点都直接挂到根上复杂度接近阿克曼函数的反函数。unite返回 false 说明两个节点原本就联通Kruskal 里遇到这种情况直接忽略这条边。按秩合并不是必须的但加上之后最坏复杂度更稳。这套模板里的 DSU 文件虽然没列全但并查集几乎是每个图论文件的前置依赖建议单独抽出来存成一个公共头文件。4.3 二分图匹配、SCC 与 2SAT从模板到建模思路BipartiteMatch2.cpp 是匈牙利算法的实现解决的是一个集合中的元素能否在另一集合中找到唯一配对的问题。核心是递归尝试调整已有匹配腾出位置。SCC 强连通分量用 Tarjan 算法SCC.cpp 里维护了 dfn 和 low 两个数组加上一个栈来记录当前强连通分量内的节点。SCC 搞完就顺手能缩点把有向图变成 DAG有些题目需要缩点后做拓扑。twoSAT.cpp 是 2SAT 判定本质是把每个变量拆成两个状态用蕴含关系建边然后跑 SCC看每个变量的两个状态是否在同一个强连通分量里——如果在就无解。// 2SAT 判定核心 for (int i 0; i n; i) { if (sccId[i 1] sccId[i 1 | 1]) { // 无解 } }2SAT 的建边规则是「一个条件推出另一个」必须保证逻辑逆否也建了边漏一条直接错。SCC 的编号顺序还有一个作用tarjan 跑完后按反拓扑序得到的缩点顺序可以直接用于拓扑 DP。二分图匹配输出具体方案时注意存的是 match 数组方向别搞反——match[v] 是右侧节点 v 匹配到的左侧节点遍历右侧输出更直观。5. 避坑指南与常见问题排查实战中高频翻车点实录5.1 整数溢出模运算和乘法链上最容易爆的地方竞赛里数据范围常给到 1e18中间结果却可以轻松溢出。我见过最典型的翻车是在组合数的连乘里fac[i] fac[i - 1] * i % mod如果 i 是 int 而 fac 是 long long 还好但如果是int * int赋值给 long long溢出已经发生了。另一个高发点在快速幂a a * a % mod里的 a 是 long long两个 long long 相乘可能达到 1e36直接 UB。处理办法就是乘法前先判断或者使用__int128模板库里有些乘法可以改成龟速乘但大多数情况下还是把中间变量类型换成long long再乘。提示凡遇两数相乘再取模先确认两个操作数的类型和取值范围必要时用__int128过渡别指望强制转换救你。5.2 数组越界和 REvector 下标与预分配空间的错位很多 .cpp 模板喜欢用vectorint g[N]这种静态数组形式配合题目给的 n但若实际输入的边数超过预设 N运行直接崩溃。我建议把图论模板统一改成vectorvectorint g(n)动态扩容虽然慢一点点但不会越界。线段树的4*n空间在极端递归深度下也可能溢出——当 n 不是 2 的幂且更新频繁时某些实现会访问到接近 4n 的末尾开成4 * n 10是保险做法。5.3 浮点精度FFT 和几何模板的精度陷阱FFT 用 double 存储中间结果但数据一大精度就会掉。当系数超过 1e9 或长度超过 1e5 时卷积结果可能错几位整数。排查方法是用一个小规模样例手算对比若对不上优先怀疑精度问题——可以尝试换成 long double或改用 NTT数论变换用模数代替浮点代价是模数必须是质数且原根存在。几何模板里判断点是否在线段上时用叉积和点积结合的写法避免浮点相等判断统一用 eps 比较。geo-jls-template.cpp 这个文件名暗示了这套库在几何上也有专门实现注意所有几何模板几乎都要先定义const double eps 1e-8;。5.4 递归深度DFS 和 Tarjan 在稠密图上的爆栈Tarjan、匈牙利算法、二分图匹配都是递归实现遇到极端数据比如一条长链递归深度可能达到 1e6默认栈空间直接爆。解决办法有两种一是把递归改成显式栈的迭代版本二是编译时加-Wl,-stack,67108864这类参数扩大栈容量。比赛环境不一定能修改编译选项所以在模板注释里标明哪些函数递归深度风险高用时心里有数。SCC 的 Tarjan 尤其容易踩这个坑因为它对每个节点做一次 DFS图是稠密时递归层数不可控。5.5 莫队排序与块大小的玄学调参莫队的正确性不依赖块大小但复杂度依赖。块大小取 sqrt(n) 是默认实际发现右端点排序用奇偶优化后块大小取n / sqrt(m)反而更快其中 m 是查询数。若模板里硬编码了sqrt(n)建议改成传入参数。还有一个常见错误莫队的add和remove顺序必须保证维护的状态始终合法。如果先 remove 再 add可能中间状态读取到空数据计算答案时炸掉。6. 把模板库改造成自己的高速板子封装验证与代码折叠的实操习惯先别急着把 .cpp 文件全复制进一个头文件——我建议按数据类型分文件整理建一个template/目录数学、数据结构、图论各放一个子目录文件命名带功能标签。然后对每个模板写一段无注释的最小样例跑一遍用-O2编译开启优化看是否有警告和运行时错误。验证通过后在文件头部加一行简短说明标注适用数据范围、复杂度、坑点比如「SegTree: 区间加/求和, O(log n), n1e5 时数组开 4n」这样的注释半年后再翻也不会陌生。接着做封装。把每个模板类的方法名统一成build/update/query把输入输出方式也统一——比赛时切换题目只需改主函数模板本身可以做到零改动。如果模板库里某个实现用scanf/printf建议保留因为竞赛环境下cin虽快但没有scanf那种确定性。封装完可以用一个简单的题目脚本验证写一个test.cpp把模板头文件和若干测试用例直接 include每次改动后跑一遍暴力对拍用随机小数据对照朴素实现。这套流程虽然多花十分钟但能让你在赛场上少花一小时调 bug。代码折叠这个习惯也值得养成。模板文件动辄几百行用编辑器折叠功能把每个类或函数缩成一个标题行查找时按文件名定位改参数时展开对应函数。注意别把折叠状态的代码直接复制进提交文件——很多编辑器会把折叠部分省略掉导致粘贴出来的代码少了关键函数。我一般把模板库当草稿纸用真提交时再手动挑需要的类复制并且复制后立刻全文搜索一遍关键函数名确认没有遗漏。我自己的习惯是每次赛前把模板库整体过一遍编译确认所有文件在当前编译环境下都能通过。这个习惯救过我很多次——有一次某次比赛环境用的是老版本编译器不支持结构化绑定我的 Dijkstra 模板里全是auto [d, u]编译直接报错。从那以后我每次拿到新环境第一件事就是把所有模板用该环境编译一遍而不是在现场对着报错一行行改。希望帮到你。本文还有配套的精品资源点击获取
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
