算法模板库¶
本页提供竞赛常用算法的可复制模板代码。每种模板包含：函数签名、完整实现和时间复杂度，部分模板附使用示例。
排序¶
快速排序¶
时间复杂度： 平均 O(n log n)，最坏 O(n^2)
void quickSort(int a[], int l, int r) {
if (l >= r) return;
int i = l, j = r, pivot = a[l + (r - l) / 2];
while (i <= j) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i <= j) {
swap(a[i], a[j]);
i++; j--;
}
}
if (l < j) quickSort(a, l, j);
if (i < r) quickSort(a, i, r);
}
使用示例：
归并排序¶
时间复杂度： O(n log n)
int tmp[N]; // 临时数组
void mergeSort(int a[], int l, int r) {
if (l >= r) return;
int mid = l + (r - l) / 2;
mergeSort(a, l, mid);
mergeSort(a, mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (int t = l; t <= r; t++) a[t] = tmp[t];
}
使用示例：
二分查找¶
整数二分（寻找左边界）¶
时间复杂度： O(log n)
// 在 [l, r] 中找到满足 check(x) == true 的最小 x
int binarySearchL(int l, int r) {
while (l < r) {
int mid = l + (r - l) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l; // 如果无解返回的值需要特判
}
整数二分（寻找右边界）¶
// 在 [l, r] 中找到满足 check(x) == true 的最大 x
int binarySearchR(int l, int r) {
while (l < r) {
int mid = l + (r - l + 1) / 2; // 注意 +1 防止死循环
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
浮点二分¶
double binarySearchDouble(double l, double r) {
while (r - l > 1e-8) { // 精度要求
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
lower_bound / upper_bound¶
// 在有序数组 a[0..n-1] 中
int a[] = {1, 2, 2, 3, 3, 3, 4};
int n = 7;
// lower_bound: 第一个 >= x 的位置
int pos1 = lower_bound(a, a + n, 3) - a; // pos1 = 3
// upper_bound: 第一个 > x 的位置
int pos2 = upper_bound(a, a + n, 3) - a; // pos2 = 6
// 统计 x 的个数 = upper_bound - lower_bound
int cnt = upper_bound(a, a + n, 3) - lower_bound(a, a + n, 3); // cnt = 3
前缀和与差分¶
一维前缀和¶
预处理数组前缀和后，任意区间和可 O(1) 查询。
时间复杂度： 预处理 O(n)，查询 O(1)
long long pre[N]; // pre[0] = 0
void buildPrefix(int n, int a[]) {
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
}
// 区间和 a[l..r]（1-indexed，闭区间）
long long rangeSum(int l, int r) { return pre[r] - pre[l - 1]; }
一维差分¶
前缀和的逆运算：把「区间整体加值」转化为差分数组上的两次单点修改，全部修改完成后做一遍前缀和还原。
时间复杂度： 单次区间修改 O(1)，最终还原 O(n)
long long diff[N];
// 区间 [l, r] 整体加 val
void rangeAdd(int l, int r, long long val) {
diff[l] += val;
diff[r + 1] -= val;
}
// 还原：对 diff 做前缀和，diff[1..i] 之和即为 a[i] 的总增量
二维前缀和¶
用容斥预处理二维前缀和，任意子矩阵和可 O(1) 查询。
时间复杂度： 预处理 O(nm)，查询 O(1)
long long pre2[N][N];
void buildPrefix2D(int n, int m, int a[][N]) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
pre2[i][j] = pre2[i - 1][j] + pre2[i][j - 1] - pre2[i - 1][j - 1] + a[i][j];
}
// 子矩阵 (x1,y1)-(x2,y2) 的和
long long rangeSum2D(int x1, int y1, int x2, int y2) {
return pre2[x2][y2] - pre2[x1 - 1][y2] - pre2[x2][y1 - 1] + pre2[x1 - 1][y1 - 1];
}
二维差分¶
在差分矩阵上用四次单点修改实现「子矩阵整体加值」，最后做二维前缀和还原。
时间复杂度： 单次子矩阵修改 O(1)，最终还原 O(nm)
long long diff2[N][N];
// 子矩阵 (x1,y1)-(x2,y2) 整体加 val
void rangeAdd2D(int x1, int y1, int x2, int y2, long long val) {
diff2[x1][y1] += val;
diff2[x1][y2 + 1] -= val;
diff2[x2 + 1][y1] -= val;
diff2[x2 + 1][y2 + 1] += val;
}
// 还原：对 diff2 做二维前缀和，即得每个位置的总增量
单调栈¶
栈内保持单调性，用于求每个元素左/右侧第一个更大或更小的元素；每个元素至多进出栈一次。
时间复杂度： O(n)
int leftSmaller[N]; // 左边第一个比 a[i] 小的元素下标，不存在为 0
void monoStack(int n, int a[]) {
stack<int> stk; // 存下标，栈内对应的值严格递增
for (int i = 1; i <= n; i++) {
while (!stk.empty() && a[stk.top()] >= a[i]) stk.pop();
leftSmaller[i] = stk.empty() ? 0 : stk.top();
stk.push(i);
}
}
使用示例：
// a[] = {_, 2, 1, 4, 3}（1-indexed）
monoStack(4, a);
// leftSmaller = {_, 0, 0, 2, 2}
// 求「右侧第一个更小」可倒序遍历；求「更大」把 >= 换成 <=
单调队列¶
双端队列维护滑动窗口内的候选最值下标：队头过期弹出、队尾破坏单调性弹出，常用于窗口最值和 DP 优化。
时间复杂度： O(n)
// 求每个长度为 k 的窗口的最大值（1-indexed）
vector<int> slidingMax(int n, int k, int a[]) {
deque<int> dq; // 存下标，对应的值单调递减
vector<int> res;
for (int i = 1; i <= n; i++) {
while (!dq.empty() && dq.front() <= i - k) dq.pop_front(); // 队头移出窗口
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // 维护单调性
dq.push_back(i);
if (i >= k) res.push_back(a[dq.front()]);
}
return res;
}
// 求窗口最小值：两处比较方向取反（值单调递增）
BFS / DFS¶
BFS 模板¶
时间复杂度： O(V + E)
// 图的邻接表
vector<int> adj[N];
bool vis[N];
int dist[N];
void bfs(int start) {
queue<int> q;
memset(vis, false, sizeof(vis));
memset(dist, -1, sizeof(dist));
vis[start] = true;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = true;
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
网格 BFS（四方向）¶
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool vis[N][N];
void bfsGrid(int sx, int sy, int n, int m) {
queue<pair<int, int>> q;
vis[sx][sy] = true;
q.push({sx, sy});
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny]) {
vis[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
DFS 模板¶
vector<int> adj[N];
bool vis[N];
void dfs(int u) {
vis[u] = true;
// 处理节点 u
for (int v : adj[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
最短路¶
Dijkstra（堆优化）¶
时间复杂度： O((V + E) log V)
适用： 非负权图单源最短路
typedef pair<int, int> pii; // (节点, 权重)
typedef pair<long long, int> pli; // (距离, 节点)，距离必须用 long long，防止累加溢出
vector<pii> adj[N];
long long dist[N];
bool done[N];
void dijkstra(int s, int n) {
priority_queue<pli, vector<pli>, greater<pli>> pq;
fill(dist, dist + n + 1, LLONG_MAX);
fill(done, done + n + 1, false);
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (done[u]) continue;
done[u] = true;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}
使用示例：
SPFA¶
时间复杂度： 平均 O(E)，最坏 O(V * E)
适用： 可含负权边，可判负环
vector<pii> adj[N]; // (节点, 权重)
long long dist[N];
int cnt[N]; // 入队次数，用于判负环
bool inq[N];
bool spfa(int s, int n) {
fill(dist, dist + n + 1, LLONG_MAX);
fill(cnt, cnt + n + 1, 0);
fill(inq, inq + n + 1, false);
queue<int> q;
dist[s] = 0;
inq[s] = true;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = false;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n) return true; // 存在负环
if (!inq[v]) {
inq[v] = true;
q.push(v);
}
}
}
}
return false; // 无负环
}
Floyd（全源最短路）¶
时间复杂度： O(V^3)
long long d[N][N]; // 邻接矩阵，d[i][j] 表示 i 到 j 的距离
void floyd(int n) {
// 初始化：d[i][i] = 0, 无边 = INF, 有边 = 权重
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
最小生成树¶
Kruskal¶
时间复杂度： O(E log E)
struct Edge {
int u, v, w;
bool operator<(const Edge& o) const { return w < o.w; }
};
Edge edges[M];
int fa[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
long long kruskal(int n, int m) {
sort(edges, edges + m);
for (int i = 1; i <= n; i++) fa[i] = i;
long long total = 0;
int cnt = 0;
for (int i = 0; i < m; i++) {
int fu = find(edges[i].u), fv = find(edges[i].v);
if (fu != fv) {
fa[fu] = fv;
total += edges[i].w;
cnt++;
if (cnt == n - 1) break;
}
}
return (cnt == n - 1) ? total : -1; // -1 表示不连通
}
拓扑排序¶
时间复杂度： O(V + E)
vector<int> adj[N];
int inDeg[N];
// 返回拓扑序，空表示有环
vector<int> topoSort(int n) {
vector<int> res;
queue<int> q;
for (int i = 1; i <= n; i++)
if (inDeg[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
res.push_back(u);
for (int v : adj[u]) {
if (--inDeg[v] == 0)
q.push(v);
}
}
if ((int)res.size() != n) return {}; // 有环
return res;
}
并查集¶
时间复杂度： 近似 O(1)（路径压缩 + 按秩合并）
int fa[N], rk[N];
void init(int n) {
for (int i = 1; i <= n; i++) {
fa[i] = i;
rk[i] = 0;
}
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]); // 路径压缩
}
void merge(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (rk[x] < rk[y]) swap(x, y); // 按秩合并
fa[y] = x;
if (rk[x] == rk[y]) rk[x]++;
}
bool same(int x, int y) {
return find(x) == find(y);
}
背包问题¶
0-1 背包¶
时间复杂度： O(n * W)
int dp[W + 1]; // 一维滚动数组
void knapsack01(int n, int W, int w[], int v[]) {
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++)
for (int j = W; j >= w[i]; j--) // 逆序遍历
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
// dp[W] 即为最大价值
}
完全背包¶
时间复杂度： O(n * W)
int dp[W + 1];
void knapsackComplete(int n, int W, int w[], int v[]) {
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++)
for (int j = w[i]; j <= W; j++) // 正序遍历
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
// dp[W] 即为最大价值
}
线段树（区间求和 + 懒标记）¶
时间复杂度： 单次操作 O(log n)
#define ls (p << 1)
#define rs (p << 1 | 1)
long long sum[N * 4], lazy[N * 4];
void pushUp(int p) {
sum[p] = sum[ls] + sum[rs];
}
void pushDown(int p, int l, int r) {
if (lazy[p]) {
int mid = (l + r) >> 1;
sum[ls] += lazy[p] * (mid - l + 1);
sum[rs] += lazy[p] * (r - mid);
lazy[ls] += lazy[p];
lazy[rs] += lazy[p];
lazy[p] = 0;
}
}
void build(int p, int l, int r, long long a[]) {
lazy[p] = 0;
if (l == r) { sum[p] = a[l]; return; }
int mid = (l + r) >> 1;
build(ls, l, mid, a);
build(rs, mid + 1, r, a);
pushUp(p);
}
void update(int p, int l, int r, int ql, int qr, long long val) {
if (ql <= l && r <= qr) {
sum[p] += val * (r - l + 1);
lazy[p] += val;
return;
}
pushDown(p, l, r);
int mid = (l + r) >> 1;
if (ql <= mid) update(ls, l, mid, ql, qr, val);
if (qr > mid) update(rs, mid + 1, r, ql, qr, val);
pushUp(p);
}
long long query(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return sum[p];
pushDown(p, l, r);
int mid = (l + r) >> 1;
long long res = 0;
if (ql <= mid) res += query(ls, l, mid, ql, qr);
if (qr > mid) res += query(rs, mid + 1, r, ql, qr);
return res;
}
使用示例：
build(1, 1, n, a); // 建树
update(1, 1, n, l, r, val); // 区间 [l,r] 加 val
long long ans = query(1, 1, n, l, r); // 查询 [l,r] 区间和
树状数组¶
时间复杂度： 单次操作 O(log n)
long long bit[N];
void add(int i, long long val) {
for (; i < N; i += i & (-i))
bit[i] += val;
}
long long sum(int i) {
long long res = 0;
for (; i > 0; i -= i & (-i))
res += bit[i];
return res;
}
long long rangeSum(int l, int r) {
return sum(r) - sum(l - 1);
}
使用示例：
KMP¶
前缀函数¶
时间复杂度： O(n)
// pi[i] = s[0..i] 中最长的既是前缀又是后缀的长度
vector<int> prefixFunction(const string& s) {
int n = s.size();
vector<int> pi(n, 0);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j])
j = pi[j - 1];
if (s[i] == s[j]) j++;
pi[i] = j;
}
return pi;
}
KMP 匹配¶
时间复杂度： O(n + m)
// 在 text 中查找 pattern 的所有出现位置
vector<int> kmpSearch(const string& text, const string& pattern) {
string s = pattern + "#" + text;
vector<int> pi = prefixFunction(s);
vector<int> positions;
int m = pattern.size();
for (int i = m + 1; i < (int)s.size(); i++) {
if (pi[i] == m)
positions.push_back(i - 2 * m); // 0-indexed 位置
}
return positions;
}
字符串哈希¶
时间复杂度： 预处理 O(n)，查询 O(1)
typedef unsigned long long ull;
const ull BASE = 131;
ull h[N], pw[N]; // h[0] = 0
void initHash(const string& s, int n) {
pw[0] = 1;
for (int i = 1; i <= n; i++) {
h[i] = h[i - 1] * BASE + (s[i - 1] - 'a' + 1);
pw[i] = pw[i - 1] * BASE;
}
}
// s[l..r] 的哈希值（1-indexed, 闭区间）
ull getHash(int l, int r) {
return h[r] - h[l - 1] * pw[r - l + 1];
}
使用示例：
string s = "abcabc";
initHash(s, s.size());
// 比较 s[0..2] 和 s[3..5] 是否相等
if (getHash(1, 3) == getHash(4, 6)) { /* 相等 */ }
Trie（字典树）¶
时间复杂度： 插入/查询 O(L)，L 为字符串长度
int trie[N][26]; // N = 节点总数
int cnt[N]; // 以该节点结尾的单词数
int tot = 0; // 节点计数
void insert(const string& s) {
int p = 0;
for (char c : s) {
int ch = c - 'a';
if (!trie[p][ch]) trie[p][ch] = ++tot;
p = trie[p][ch];
}
cnt[p]++;
}
int search(const string& s) {
int p = 0;
for (char c : s) {
int ch = c - 'a';
if (!trie[p][ch]) return 0;
p = trie[p][ch];
}
return cnt[p];
}
Tarjan 算法¶
强连通分量（SCC）¶
时间复杂度： O(V + E)
vector<int> adj[N];
int dfn[N], low[N], scc[N], stk[N];
bool inStk[N];
int timeStamp, sccCnt, top;
void tarjan(int u) {
dfn[u] = low[u] = ++timeStamp;
stk[++top] = u;
inStk[u] = true;
for (int v : adj[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (inStk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
sccCnt++;
while (true) {
int v = stk[top--];
inStk[v] = false;
scc[v] = sccCnt;
if (v == u) break;
}
}
}
// 初始化后对所有未访问节点调用 tarjan(i)
// scc[i] 为节点 i 所属的 SCC 编号
割点¶
vector<int> adj[N];
int dfn[N], low[N], timeStamp;
bool isCut[N]; // isCut[i] = true 表示 i 是割点
void tarjanCut(int u, int root) {
dfn[u] = low[u] = ++timeStamp;
int child = 0;
for (int v : adj[u]) {
if (!dfn[v]) {
tarjanCut(v, root);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u] && u != root)
isCut[u] = true;
if (u == root) child++;
} else {
low[u] = min(low[u], dfn[v]);
}
}
if (u == root && child >= 2)
isCut[root] = true;
}
桥¶
vector<pii> adj[N]; // (节点, 边编号)
int dfn[N], low[N], timeStamp;
bool isBridge[M]; // isBridge[i] = true 表示边 i 是桥
void tarjanBridge(int u, int fromEdge) {
dfn[u] = low[u] = ++timeStamp;
for (auto [v, eid] : adj[u]) {
if (eid == fromEdge) continue;
if (!dfn[v]) {
tarjanBridge(v, eid);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u])
isBridge[eid] = true;
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
数学模板¶
快速幂¶
时间复杂度： O(log b)
long long qpow(long long a, long long b, long long mod) {
long long res = 1;
a %= mod;
while (b > 0) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
扩展欧几里得（exGCD）¶
时间复杂度： O(log(min(a, b)))
// 求 ax + by = gcd(a, b) 的一组解
long long exgcd(long long a, long long b, long long& x, long long& y) {
if (b == 0) { x = 1; y = 0; return a; }
long long g = exgcd(b, a % b, y, x);
y -= a / b * x;
return g;
}
欧拉筛（线性筛质数）¶
时间复杂度： O(n)
int primes[N], cnt;
bool isNotPrime[N];
void eulerSieve(int n) {
cnt = 0;
fill(isNotPrime, isNotPrime + n + 1, false);
for (int i = 2; i <= n; i++) {
if (!isNotPrime[i]) primes[cnt++] = i;
for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
isNotPrime[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
组合数预处理¶
时间复杂度： 预处理 O(n^2)，查询 O(1)
// 方法一：杨辉三角（适合 n 较小）
long long C[N][N];
void initComb(int n) {
C[0][0] = 1;
for (int i = 1; i <= n; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
// 方法二：阶乘逆元（适合 n 较大）
long long fac[N], invFac[N];
void initCombFact(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
invFac[n] = qpow(fac[n], MOD - 2, MOD);
for (int i = n - 1; i >= 0; i--) invFac[i] = invFac[i + 1] * (i + 1) % MOD;
}
long long comb(int n, int m) {
if (m < 0 || m > n) return 0;
return fac[n] % MOD * invFac[m] % MOD * invFac[n - m] % MOD;
}
矩阵快速幂¶
时间复杂度： O(n^3 log k)
typedef vector<vector<long long>> Matrix;
Matrix mul(const Matrix& A, const Matrix& B, long long mod) {
int n = A.size();
Matrix C(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++)
for (int k = 0; k < n; k++)
for (int j = 0; j < n; j++)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
return C;
}
Matrix matPow(Matrix A, long long k, long long mod) {
int n = A.size();
Matrix res(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++) res[i][i] = 1; // 单位矩阵
while (k > 0) {
if (k & 1) res = mul(res, A, mod);
A = mul(A, A, mod);
k >>= 1;
}
return res;
}
使用示例（斐波那契第 n 项）：