算法竞赛代码模板库：从Dijkstra到线段树，构建你的夺冠武器库-开发者社区

简介：本资源是一套面向OI、ACM、PAT、CSP等编程竞赛选手的高频代码模板合集，聚焦算法竞赛中反复出现的核心问题求解范式，助力参赛者在限时高压环境下快速编码、减少低级错误、提升AC率。压缩包共53个文件，以41篇Markdown文档为主干（系统讲解算法原理、适用场景与边界条件），辅以11个可直接编译运行的C++模板代码（如快读、KMP、Dijkstra、并查集、线性DP等），另含1个.gitignore用于开发管理；整体仅51KB，轻量易集成。已有740人学习下载，内容覆盖基础算法、动态规划、贪心与回溯、数学与字符串、图论与网络流、计算几何及位运算优化等十大模块，目录按知识域分层组织，每类模板均附典型题目映射与关键注释，支持即查即用与深度理解双路径学习。

1. 从“刷题小白”到“赛场老手”：为什么你需要一份代码模板库？

如果你刚开始接触编程竞赛或者准备机试，可能会觉得“代码模板”这个词有点玄乎。看着网上流传的各种“祖传模板”、“万能板子”，是不是感觉一头雾水？这些动辄几十上百行的代码片段，到底有什么用？难道比赛不是考察算法思维和编码能力吗，直接背代码算不算“作弊”？

作为一个在算法竞赛圈混迹多年的老选手，我想告诉你一个残酷的现实：在OI（信息学奥林匹克）、ACM-ICPC（国际大学生程序设计竞赛）、PAT（浙江大学计算机程序设计能力考试）、CSP（计算机软件能力认证）乃至各大高校的机试OJ（在线评测系统）中，拥有一个经过千锤百炼、烂熟于心的个人代码模板库，是你从“能做题”到“快速、稳定、无差错地AC（Accept，通过）”之间最关键的一道分水岭。这绝不是作弊，而是顶尖选手的必备素养。

想象一下这个场景：比赛时间还剩30分钟，你终于理清了最后一道难题的思路，是一个复杂的图论问题，需要用到Dijkstra算法求最短路，并且要记录路径。此时，你有两个选择：A. 从头开始，边回忆边敲打priority_queue的用法、dist数组的初始化、松弛操作的条件判断，还要小心处理前驱节点数组，最后调试可能出现的下标越界或逻辑错误。B. 从你的模板库中，找到已经封装好的Dijkstra函数，输入顶点数、边集，直接调用，然后专注于处理题目特有的输入输出和逻辑。选择A，你可能在紧张中功亏一篑；选择B，你就有极大可能在封榜前再下一城。

这份模板的价值，远不止是“复制粘贴”节省时间。它更是一个个人化的、经过实战检验的“武器库”。里面每一行代码，都凝结了你对某个算法最深刻的理解——哪里容易写错边界，哪种数据结构的实现效率最高，如何为特定题型（如需要取模的大数运算）做适配。当你在考场上遇到一个似曾相识的问题时，可靠的模板能给你巨大的信心，让你把宝贵的脑力和时间集中在问题建模和策略选择上，而不是底层代码的反复调试上。

接下来，我将为你系统性地梳理在OI、OJ、ACM、PAT、CSP等场景下，那些最高频、最实用、最需要模板化的代码模块。我不会给你一个“万能”但臃肿的模板，而是带你理解每个模板为什么这么写，在什么场景下用，以及使用时最容易踩哪些坑。我们的目标是，让你能亲手搭建并真正内化一个属于自己的“夺冠代码库”。

2. 算法竞赛模板的核心构成：一个模块化的工具箱

一个成熟的竞赛代码模板，绝不是一个大杂烩的单一文件。它应该像一套精密的组合工具，模块清晰，随取随用。根据我的经验，一个高效的模板库通常包含以下几个核心部分，我会逐一解释其必要性和设计思路。

2.1 输入输出加速：一切效率的起点

这是所有模板的“开门第一件事”，尤其是在C++中。C++默认的cin/cout为了兼容C的stdio，默认是与stdin/stdout同步的，这会导致额外的性能开销。在PAT、CSP或者数据量巨大的OJ题目中，这很可能成为你TLE（Time Limit Exceeded，超时）的第一个元凶。

为什么必须加速？假设一道题需要读入10^5个整数，普通的cin可能比scanf慢数倍。在ACM赛制中，时间是按毫秒计的，这种开销绝对无法忍受。

经典且安全的加速模板：

#include <bits/stdc++.h> // 竞赛常用万能头文件 using namespace std; int main() { // 关键加速语句 ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // 非必须，但保持对称是好习惯 // 此后，可以安全地混用cin/cout和scanf/printf，但更推荐纯用cin/cout int n; cin >> n; // ... 你的代码逻辑 return 0; }

ios::sync_with_stdio(false);：解除C++标准流与C标准流的同步，关闭后cin/cout速度大幅提升。
cin.tie(nullptr);：解除cin与cout的绑定。默认情况下，每次cin前都会强制刷新cout缓冲区，以保证输出在输入前显示。竞赛中我们通常不需要这个特性，关闭它可以进一步提升效率。

注意：一旦使用了这两行代码，就绝对不要再混用cin/cout和scanf/printf，因为流已不同步，会导致输入输出顺序混乱和错误。统一使用cin/cout即可。

针对大量数据读入的优化：对于需要读入百万级整数的情况，可以手写快读函数，但这通常只在极端卡常的OI赛题中需要。对于ACM、PAT、CSP，上述关闭同步流的方法已经足够。

2.2 数据结构模板：STL的威力与局限

C++ STL（Standard Template Library）是竞赛的利器，但直接使用有时不够高效或功能不全。我们需要对其进行封装和增强。

2.2.1 并查集 (Disjoint Set Union, DSU)这是处理元素分组、连通性问题的神器。裸的并查集容易写，但加上“路径压缩”和“按秩合并”优化后，效率才是接近O(α(n))的。

class DSU { private: vector<int> parent, rank; // rank也可以是size，用于按大小合并 public: DSU(int n) : parent(n), rank(n, 0) { iota(parent.begin(), parent.end(), 0); // 初始化每个元素的父节点为自己 } // 查找（带路径压缩） int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } // 合并（按秩合并） bool unite(int x, int y) { int rx = find(x), ry = find(y); if (rx == ry) return false; // 已在同一集合 if (rank[rx] < rank[ry]) { parent[rx] = ry; } else if (rank[rx] > rank[ry]) { parent[ry] = rx; } else { parent[ry] = rx; rank[rx]++; } return true; } bool connected(int x, int y) { return find(x) == find(y); } };

使用场景：动态连通性问题、最小生成树Kruskal算法、判断图中是否有环等。

2.2.2 树状数组 (Fenwick Tree) 与线段树 (Segment Tree)两者都用于处理数组区间查询和单点/区间更新。树状数组代码简洁、效率高，但功能受限（主要维护前缀和型信息，如和、异或）；线段树功能强大，可维护任意满足结合律的信息（如最大值、最小值、区间和、区间平方和等），但代码复杂。

树状数组模板（维护前缀和）：

class Fenwick { private: vector<int> tree; int n; public: Fenwick(int size) : n(size), tree(size + 1, 0) {} // 单点增加 void add(int idx, int delta) { for (; idx <= n; idx += idx & -idx) { tree[idx] += delta; } } // 前缀和查询 [1, idx] int query(int idx) { int sum = 0; for (; idx > 0; idx -= idx & -idx) { sum += tree[idx]; } return sum; } // 区间和查询 [l, r] (1-indexed) int rangeQuery(int l, int r) { return query(r) - query(l - 1); } };

选择策略：如果问题可以转化为前缀和操作（如逆序对、区间求和、单点更新），优先用树状数组。如果需要区间赋值、求区间最值、更复杂的懒标记更新，则必须用线段树。

2.3 图论算法模板：建模与实现的桥梁

图论题是竞赛大户，清晰的模板能让你快速将思路转化为代码。

2.3.1 图的存储邻接表和邻接矩阵是最常用的。对于稀疏图（边数远小于顶点数平方），必须使用邻接表，否则会MLE（内存超限）。

// 邻接表（使用vector，最通用） int n, m; // 顶点数，边数 vector<vector<int>> adj(n); // 无权图 vector<vector<pair<int, int>>> adj(n); // 带权图，pair<邻居, 边权> // 添加边示例（无向图） adj[u].push_back(v); adj[v].push_back(u); // 添加带权边 adj[u].push_back({v, w}); adj[v].push_back({u, w}); // 邻接矩阵（适用于稠密图或Floyd算法） vector<vector<int>> graph(n, vector<int>(n, INF)); graph[u][v] = w; // 有向边

2.3.2 Dijkstra 单源最短路径（优先队列优化）这是必须模板化的经典算法。核心是使用小顶堆（priority_queue）每次取出当前距离最小的点进行松弛。

const int INF = 0x3f3f3f3f; // 一个很大的数，常用作无穷大 vector<int> dijkstra(int start, const vector<vector<pair<int, int>>>& adj) { int n = adj.size(); vector<int> dist(n, INF); dist[start] = 0; // 优先队列，存储 pair<当前距离, 顶点编号> priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // 关键！过滤掉队列中过时的、非最短的距离 for (auto &[v, w] : adj[u]) { if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; }

关键点解释：

if (d > dist[u]) continue;这行至关重要。因为同一个节点可能被多次加入优先队列（当发现更短路径时），这行代码确保了只有当前最短距离对应的状态才会被处理，避免了无效操作。
使用greater<>使优先队列成为小顶堆。
时间复杂度 O((V+E)logV)，适用于边权非负的图。

2.3.3 拓扑排序（Kahn算法）用于有向无环图的节点排序，或检测图中是否有环。

vector<int> topologicalSort(int n, vector<vector<int>>& adj) { vector<int> inDegree(n, 0); for (int u = 0; u < n; ++u) { for (int v : adj[u]) { inDegree[v]++; } } queue<int> q; for (int i = 0; i < n; ++i) { if (inDegree[i] == 0) q.push(i); } vector<int> order; while (!q.empty()) { int u = q.front(); q.pop(); order.push_back(u); for (int v : adj[u]) { if (--inDegree[v] == 0) { q.push(v); } } } // 如果排序后的节点数小于n，说明图中有环 if (order.size() != n) return {}; // 返回空数组表示有环 return order; }

2.4 动态规划（DP）的常用技巧与初始化模板

DP题千变万化，但有一些通用技巧可以模板化，以减少错误。

2.4.1 记忆化搜索框架对于思路清晰但递推顺序不好确定的DP，记忆化搜索（递归+缓存）是很好的选择。

vector<vector<int>> memo; // 记忆化数组，维度根据状态数定 vector<int> values; // 或其他输入数据 int dfs(int state1, int state2) { if (/* 边界条件 */) return /* 边界值 */; if (memo[state1][state2] != -1) return memo[state1][state2]; // 已计算过 int res = 0; // 根据状态转移方程进行计算 // 例如：res = max(dfs(next_state1, next_state2) + cost, ...); memo[state1][state2] = res; // 保存结果 return res; } int main() { // 初始化memo为-1（或一个不可能出现的值） memo.assign(N, vector<int>(M, -1)); int ans = dfs(start_state1, start_state2); cout << ans << endl; }

2.4.2 背包问题模板01背包和完全背包的经典一维数组优化写法必须熟练掌握。

// 01背包：物品数量N，背包容量V，价值val，体积vol vector<int> dp(V + 1, 0); for (int i = 0; i < N; ++i) { for (int j = V; j >= vol[i]; --j) { // 逆序枚举容量！！！ dp[j] = max(dp[j], dp[j - vol[i]] + val[i]); } } // 最终 dp[V] 即为最大价值 // 完全背包：物品无限取用 vector<int> dp(V + 1, 0); for (int i = 0; i < N; ++i) { for (int j = vol[i]; j <= V; ++j) { // 正序枚举容量！！！ dp[j] = max(dp[j], dp[j - vol[i]] + val[i]); } }

核心区别：内层循环的枚举顺序。01背包逆序是为了保证每个物品只被计算一次；完全背包正序则允许物品被重复选取。这个细节是背包问题的精髓，必须理解透彻并形成肌肉记忆。

3. 数学与字符串：隐蔽的卡分点与模板化策略

这部分内容看似基础，但在竞赛中因细节处理不当而丢分的情况比比皆是。

3.1 质数与模运算

3.1.1 质数筛法（埃氏筛与欧拉筛）判断单个质数用试除法，但需要预处理一段区间内的所有质数时，筛法是唯一选择。

// 埃拉托斯特尼筛法 (Sieve of Eratosthenes) - 简单易懂，O(n log log n) const int MAX_N = 1e6 + 5; vector<bool> isPrime(MAX_N, true); vector<int> primes; void eratosthenes(int n) { isPrime[0] = isPrime[1] = false; for (int i = 2; i <= n; ++i) { if (isPrime[i]) { primes.push_back(i); // 从 i*i 开始标记，因为 2*i, 3*i, ..., (i-1)*i 已被更小的质数标记过 if ((long long)i * i <= n) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } } } // 欧拉筛 (线性筛) - 效率更高，O(n)，每个合数只被其最小质因子筛一次 void eulerSieve(int n) { vector<bool> isPrime(n+1, true); vector<int> primes; for (int i = 2; i <= n; ++i) { if (isPrime[i]) primes.push_back(i); for (int p : primes) { if (i * p > n) break; isPrime[i * p] = false; if (i % p == 0) break; // 关键！保证每个合数只被最小的质因子筛掉 } } }

选择：埃氏筛代码简单，在n<=10^6时完全够用。欧拉筛效率理论更优，但代码稍复杂，在需要极致性能或同时求其他数论函数时使用。

3.1.2 快速幂与模逆元在涉及取模的计数问题中，快速幂是基础。

// 快速幂 (a^b % mod) long long fastPow(long long a, long long b, long long mod) { long long res = 1 % mod; // 注意mod=1的情况 a %= mod; while (b > 0) { if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; } // 费马小定理求模逆元 (要求mod为质数，且a与mod互质) // a在模mod下的逆元 inv(a) = a^(mod-2) % mod long long modInverse(long long a, long long mod) { return fastPow(a, mod - 2, mod); }

3.2 字符串处理：KMP与Trie树

3.2.1 KMP算法（字符串匹配）理解next数组（或称为fail数组、lps数组）是核心。它表示模式串前缀的最长相等真前后缀长度。

// 构建next数组 vector<int> buildNext(const string& pattern) { int m = pattern.size(); vector<int> next(m, 0); for (int i = 1, j = 0; i < m; ++i) { while (j > 0 && pattern[i] != pattern[j]) { j = next[j - 1]; // 回退 } if (pattern[i] == pattern[j]) { j++; } next[i] = j; } return next; } // KMP搜索 int kmpSearch(const string& text, const string& pattern) { vector<int> next = buildNext(pattern); int n = text.size(), m = pattern.size(); for (int i = 0, j = 0; i < n; ++i) { while (j > 0 && text[i] != pattern[j]) { j = next[j - 1]; } if (text[i] == pattern[j]) { j++; } if (j == m) { // 找到一个匹配，位置在 i - m + 1 // return i - m + 1; // 返回第一个匹配位置 // 如果找所有匹配，可以： // matches.push_back(i - m + 1); j = next[j - 1]; // 继续寻找下一个匹配 } } return -1; // 未找到 }

关键理解：next数组让我们在匹配失败时，不用回溯文本串的指针i，而是将模式串指针j回退到一个可能的位置继续匹配，实现了O(n+m)的时间复杂度。

3.2.2 Trie树（前缀树）用于高效存储和检索字符串集合，特别是处理前缀相关查询。

class Trie { private: struct TrieNode { vector<TrieNode*> children; bool isEnd; TrieNode() : children(26, nullptr), isEnd(false) {} // 假设只包含小写字母 }; TrieNode* root; public: Trie() : root(new TrieNode()) {} void insert(const string& word) { TrieNode* node = root; for (char ch : word) { int idx = ch - 'a'; if (!node->children[idx]) { node->children[idx] = new TrieNode(); } node = node->children[idx]; } node->isEnd = true; } bool search(const string& word) { TrieNode* node = root; for (char ch : word) { int idx = ch - 'a'; if (!node->children[idx]) return false; node = node->children[idx]; } return node->isEnd; } bool startsWith(const string& prefix) { TrieNode* node = root; for (char ch : prefix) { int idx = ch - 'a'; if (!node->children[idx]) return false; node = node->children[idx]; } return true; } };

4. 实战演练：将模板应用于经典赛题场景

理解了模板的构成，更重要的是知道在什么题目、什么时机去调用它们。我们通过几个融合了上述模板的经典场景来分析。

4.1 场景一：PAT甲级或CSP认证中的“图论+最短路+路径输出”

题目特征：给出一张城市公路网或通信网络，每个节点有名称或编号，边有权值（距离、成本、时间）。要求计算从起点到终点的最短路径，并输出具体路径。通常还会附加条件，如“在距离最短的前提下，选择成本最低的路径”或“在成本相同的前提下，选择经过节点最少的路径”。

解题思路与模板应用：

建模：明确顶点和边。顶点通常是城市或节点编号，边是带权（可能多权重）的有向或无向边。
数据结构选择：使用vector<vector<pair<int, int>>>或vector<vector<Edge>>（Edge是自定义结构体，包含目标点和多个权值）存储图。
算法选择：单源最短路，首选Dijkstra算法（边权非负）。如果存在第二标尺（如成本），需要在dist数组和状态转移时进行额外处理。
路径记录：在Dijkstra算法的松弛操作中，如果找到了到节点v的更短路径，不仅要更新dist[v]，还要更新pre[v] = u（前驱节点）。最终从终点递归或迭代pre数组即可得到逆序路径。
多标尺处理：这是难点。通常有两种方法：
- 方法A（两次Dijkstra）：第一次求第一标尺（如距离）的最短路，并记录下所有最短路径（可以用vector<int> pre[N]记录所有可能的前驱）。第二次在这些最短路径子图上，用DFS或再次Dijkstra求第二标尺（如成本）最优。
- 方法B（一次Dijkstra，多维度判断）：将dist数组定义为结构体，包含多个权值。在松弛时，先比较第一标尺，若更优则无条件更新；若相等，则比较第二标尺，若更优则更新。这种方法更高效，但逻辑稍复杂。

模板增强示例（带路径记录和多标尺的Dijkstra）：

struct Node { int id; int dist; // 第一标尺：距离 int cost; // 第二标尺：花费 bool operator>(const Node& other) const { if (dist != other.dist) return dist > other.dist; return cost > other.cost; // 距离相同时，按花费排序 } }; void dijkstra(int start, int end) { vector<int> dist(n, INF), cost(n, INF), pre(n, -1); dist[start] = 0; cost[start] = 0; priority_queue<Node, vector<Node>, greater<>> pq; pq.push({start, 0, 0}); while (!pq.empty()) { auto [u, d, c] = pq.top(); pq.pop(); if (d > dist[u]) continue; // 关键剪枝 for (auto &[v, edgeDist, edgeCost] : adj[u]) { int newDist = dist[u] + edgeDist; int newCost = cost[u] + edgeCost; // 核心比较逻辑 if (newDist < dist[v] || (newDist == dist[v] && newCost < cost[v])) { dist[v] = newDist; cost[v] = newCost; pre[v] = u; // 记录前驱 pq.push({v, newDist, newCost}); } } } // 输出路径 vector<int> path; for (int v = end; v != -1; v = pre[v]) path.push_back(v); reverse(path.begin(), path.end()); for (int node : path) cout << node << " "; }

4.2 场景二：ACM区域赛中的“动态规划+状态压缩”

题目特征：问题规模中有一个维度很小（通常n <= 20），但状态复杂。典型问题如“旅行商问题（TSP）”、“铺瓷砖”、“棋盘覆盖”等。这类问题通常需要枚举所有可能的状态组合。

解题思路与模板应用：

识别状态：定义dp[state][...]，其中state是一个整数，它的二进制位表示某个元素是否被选中/访问过/占据。例如，在TSP中，state的二进制第i位为1表示城市i已被访问过。
状态转移：从已知状态state转移到新状态state | (1 << next)。转移方程通常是求最小代价或最大收益。
初始化与答案：dp[1<<start][start] = 0。最终答案可能是min(dp[(1<<n)-1][i])对所有i。
时间复杂度：状态数O(2^n * n)，转移O(n)，总复杂度O(2^n * n^2)。当n<=20时（2^20 ≈ 1e6），通常可接受。

模板示例（状态压缩DP解决最短哈密顿路径问题）：

int n; int weight[20][20]; // 城市间距离 int dp[1 << 20][20]; // dp[state][i]: 访问过state表示的城市集合，当前在i城市的最小花费 const int INF = 0x3f3f3f3f; int solve() { memset(dp, 0x3f, sizeof(dp)); dp[1][0] = 0; // 从城市0出发，只访问了城市0的状态 for (int state = 1; state < (1 << n); ++state) { for (int i = 0; i < n; ++i) { if (!(state >> i & 1)) continue; // 状态state必须包含i if (dp[state][i] == INF) continue; // 无效状态 for (int j = 0; j < n; ++j) { if (state >> j & 1) continue; // j不能在已访问集合中 int newState = state | (1 << j); dp[newState][j] = min(dp[newState][j], dp[state][i] + weight[i][j]); } } } int finalState = (1 << n) - 1; int ans = INF; // 最终要回到起点城市0，形成环路 for (int i = 1; i < n; ++i) { if (weight[i][0] != INF) { ans = min(ans, dp[finalState][i] + weight[i][0]); } } return ans; }

关键技巧：使用位运算高效处理状态。state >> i & 1检查第i位是否为1，state | (1 << j)将第j位置1。

4.3 场景三：OJ日常训练中的“区间查询与更新”

题目特征：给你一个数组，需要频繁进行两种操作：1. 查询某个区间的和/最大值/最小值等；2. 更新某个位置的值或给某个区间所有值加上一个数。数据量在10^5级别。

解题思路与模板应用：

分析操作：
- 单点更新，区间查询：树状数组或线段树。
- 区间更新，单点查询：使用差分数组+树状数组（转化为单点更新区间查询），或线段树（带懒标记）。
- 区间更新，区间查询：必须使用带懒标记的线段树。
选择数据结构：如果问题可以转化为前缀和操作（如区间和），优先考虑树状数组，因为代码简单不易错。如果涉及区间最值、区间赋值、复杂合并操作，必须用线段树。
懒标记线段树模板要点：这是竞赛中的重点和难点。核心是每个节点维护一个lazy标记，表示该节点对应区间需要更新但还未下传给子节点的值。在查询和更新时，如果当前节点区间被完全包含在目标区间内，就更新当前节点的值并打上lazy标记，然后返回，不再继续下探。只有当需要访问子节点时，才将lazy标记下传（pushdown操作）。

带懒标记的线段树模板（区间加，区间求和）：

class SegTree { private: struct Node { int l, r; long long sum; // 区间和 long long lazy; // 懒标记，表示区间内每个数要加的值 }; vector<Node> tree; vector<int>& arr; // 原数组引用 void build(int p, int l, int r) { tree[p].l = l; tree[p].r = r; tree[p].lazy = 0; if (l == r) { tree[p].sum = arr[l]; return; } int mid = (l + r) / 2; build(p*2, l, mid); build(p*2+1, mid+1, r); pushup(p); } void pushup(int p) { tree[p].sum = tree[p*2].sum + tree[p*2+1].sum; } void pushdown(int p) { if (tree[p].lazy != 0) { int lc = p*2, rc = p*2+1; tree[lc].sum += tree[p].lazy * (tree[lc].r - tree[lc].l + 1); tree[rc].sum += tree[p].lazy * (tree[rc].r - tree[rc].l + 1); tree[lc].lazy += tree[p].lazy; tree[rc].lazy += tree[p].lazy; tree[p].lazy = 0; } } public: SegTree(vector<int>& nums) : arr(nums) { int n = nums.size(); tree.resize(4 * n); build(1, 0, n-1); } // 区间 [l, r] 内每个数加 val void update(int p, int l, int r, int val) { if (l <= tree[p].l && tree[p].r <= r) { tree[p].sum += (long long)val * (tree[p].r - tree[p].l + 1); tree[p].lazy += val; return; } pushdown(p); int mid = (tree[p].l + tree[p].r) / 2; if (l <= mid) update(p*2, l, r, val); if (r > mid) update(p*2+1, l, r, val); pushup(p); } // 查询区间 [l, r] 的和 long long query(int p, int l, int r) { if (l <= tree[p].l && tree[p].r <= r) return tree[p].sum; pushdown(p); int mid = (tree[p].l + tree[p].r) / 2; long long res = 0; if (l <= mid) res += query(p*2, l, r); if (r > mid) res += query(p*2+1, l, r); return res; } };

使用心得：线段树的pushdown操作是灵魂，一定要在访问子节点之前调用。区间更新时，如果完全覆盖当前节点，就更新并打标记返回，这个“完全覆盖”的判断是保证效率的关键。

5. 模板的个性化、调试与赛场策略

拥有模板只是第一步，如何让它真正成为你的一部分，并在高压的赛场环境下稳定发挥，才是最终目标。

5.1 如何构建与记忆你的个人模板库

从模仿到理解：不要死记硬背。找一份高质量的模板（如算法竞赛经典书籍或知名选手的模板），先逐行理解，然后自己默写。默写时思考每一行的作用，尝试用不同的方式实现同一功能（比如用数组还是vector实现DSU）。
在实战中打磨：在OJ上找对应模板的裸题进行练习。例如，练习Dijkstra就找最短路裸题，练习线段树就找区间求和裸题。在AC之后，尝试修改模板以适应题目的微小变化（如多输出一个路径）。
整理与分类：建立自己的代码仓库（如本地的文件夹或Git仓库）。按算法分类：图论、数据结构、数学、字符串、动态规划等。每个大类下再细分，如图论下分最短路、最小生成树、网络流等。每个模板文件要有清晰的注释，说明功能、复杂度、使用示例和注意事项。
制作“一句话提示卡”：对于复杂的模板（如带懒标记线段树），可以制作一个简短的“口诀”或关键步骤提示，帮助你在紧张时快速回忆。例如：“线段树四函数：build,pushup,pushdown,update/query。更新查询先pushdown，完全覆盖打标记。”
定期复习与重构：每隔一段时间，回顾你的模板。你可能会发现更优雅的实现，或者对某个算法的理解更深了，这时就更新你的模板库。保持模板的“活性”。

5.2 赛场上的模板使用策略与调试技巧

赛前准备：将最核心、最常用的模板预先敲在IDE里。很多比赛允许带纸质资料，可以将关键模板、复杂度的公式、数学定理打印出来。
谨慎复制粘贴：从模板库复制代码后，第一件事是修改变量名和参数以匹配当前题目。盲目粘贴导致变量名冲突是常见错误。例如，模板里的全局变量n, m可能和题目定义冲突。
编写“测试桩”：对于复杂的算法，在模板旁写一个简单的main函数和测试数据。在比赛开局时，花1-2分钟用这个测试数据跑一下模板，确保它在当前环境下编译通过且结果正确。这能极大避免因环境差异或手误导致的低级错误。
防御性编程：
- 数组大小：使用const int MAXN = 1e5 + 10;定义数组，比直接用数字更安全。
- 无穷大：对于int，常用0x3f3f3f3f，因为它满足INF + INF不会溢出成负数，且memset(arr, 0x3f, sizeof(arr))可以方便地设置为该值。
- 初始化：特别是全局变量，每次处理新样例前要记得初始化vis,dist,dp等数组。
调试三板斧：
- 小数据测试：自己构造边界情况（n=0, n=1, 最大最小值）和简单情况，用脑算或暴力程序验证。
- 输出中间变量：在怀疑的代码段前后，输出关键变量（如循环索引、状态值、计算结果）。这是最直接的调试方法。
- 对拍：对于不确定正确性的复杂算法，可以写一个绝对正确但效率低的暴力算法（Brute Force），用脚本生成大量随机数据，比较两个程序的输出。这是找出隐蔽错误的大杀器。

5.3 不同赛事对模板的侧重与差异

OI (信息学奥林匹克)：极其注重算法效率和对问题本质的洞察。模板要求高度优化，可能涉及位运算、读入优化、内存池等底层技巧。对数学、数据结构（如平衡树、树套树）的要求也更深。
ACM-ICPC：强调团队合作、快速解题和罚时。模板要求正确、稳定、清晰胜过极致的优化。因为代码需要队友也能快速看懂和调试。图论、动态规划、计算几何、字符串的模板是重点。
PAT/CSP：属于能力认证考试，题目通常模拟实际应用场景。对标准库（STL）的熟练运用要求很高。排序、查找、哈希映射(unordered_map)、字符串处理(string,stringstream)等是常客。图论和树的问题也比较多，但难度通常低于ACM。输入输出格式必须严格符合题目要求，这是容易丢分的地方。
高校OJ/考研机试：题目来源多样，可能偏向经典算法和数据结构的直接应用。打好基础模板（排序、二分、BFS/DFS、简单DP）是关键。

最后，我想分享一个最深的体会：模板的本质，是将你反复验证过的、正确的思维过程固化下来。它节省的不是思考的时间，而是将思考成果可靠重现的时间。当你看到一个题目，能立刻反应出“这需要用Dijkstra，我的模板在graph/dijkstra.cpp里，需要稍作修改加入路径记录”，你就已经超越了大部分还在纠结于priority_queue用法的选手。从这个角度看，构建模板库的过程，本身就是一次对算法知识的深度梳理和强化。现在，就从整理你的第一个快速幂模板开始吧。

本文还有配套的精品资源，点击获取