算法代码板子速查

树状数组、线段树、KMP、Dijkstra、矩阵快速幂等板子

最后更新于:
|
|
|

← 返回高级数据结构学习笔记

零、通用头文件 & 宏定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int MAXN = {};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;

一、树状数组 (BIT)

场景：单点修改 + 区间查询 / 求逆序对
复杂度：修改 O(log n)，查询 O(log n)
注意：下标必须从 1 开始

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int tree[MAXN], n;

int lowbit(int x) { return x & -x; }

// 单点增加：a[i] += val
void add(int i, int val) {
    while (i <= n) { tree[i] += val; i += lowbit(i); }
}

// 前缀和：[1, i]
int query(int i) {
    int sum = 0;
    while (i > 0) { sum += tree[i]; i -= lowbit(i); }
    return sum;
}

// 区间和：[l, r]
int range_sum(int l, int r) { return query(r) - query(l - 1); }

扩展 — 求逆序对（需先离散化）：

1
2
3
4
5
6
7

ll swaps = 0;
for (int i = 0; i < n; i++) {
    int x; cin >> x;
    swaps += i - query(x);  // 比 x 大的已出现个数
    add(x, 1);
}
cout << swaps << endl;

扩展 — BIT + 差分实现区间修改：区间 [a, b] 统一 +1 → add(a, 1); add(b+1, -1);，query(i) 即点 i 的真实值。

二、线段树 (Segment Tree)

场景：区间修改 + 区间查询
复杂度：建树 O(n)，修改/查询 O(log n)
关键约束：维护的值必须满足区间加法（和/max/min/gcd）

2.1 无 Lazy — 单点修改 + 区间查询

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#define MAXN 100007
int A[MAXN];

struct SegNode { int val; } seg[MAXN << 2];

void push_up(int rt) {
    seg[rt].val = seg[rt << 1].val + seg[rt << 1 | 1].val;
}

// 建树：build(1, n, 1)
void build(int l, int r, int rt) {
    if (l == r) { seg[rt].val = A[l]; return; }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    push_up(rt);
}

// 单点更新：A[pos] += C
void update(int pos, int C, int l, int r, int rt) {
    if (l == r) { seg[rt].val += C; return; }
    int m = (l + r) >> 1;
    if (pos <= m) update(pos, C, l, m, rt << 1);
    else          update(pos, C, m + 1, r, rt << 1 | 1);
    push_up(rt);
}

// 区间查询 [L, R]
int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) return seg[rt].val;
    if (L > r || R < l)   return 0;
    int m = (l + r) >> 1;
    return query(L, R, l, m, rt << 1) + query(L, R, m + 1, r, rt << 1 | 1);
}

2.2 Lazy 版 — 区间修改 + 区间查询

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

struct SegNode { int val, lazy; } seg[MAXN << 2];

void push_down(int rt, int ln, int rn) {
    if (seg[rt].lazy) {
        seg[rt << 1].lazy     += seg[rt].lazy;
        seg[rt << 1 | 1].lazy += seg[rt].lazy;
        seg[rt << 1].val      += seg[rt].lazy * ln;
        seg[rt << 1 | 1].val  += seg[rt].lazy * rn;
        seg[rt].lazy = 0;
    }
}

// 区间更新：[L,R] += C
void update(int L, int R, int C, int l, int r, int rt) {
    if (L <= l && r <= R) {
        seg[rt].val  += C * (r - l + 1);
        seg[rt].lazy += C;
        return;
    }
    int m = (l + r) >> 1;
    push_down(rt, m - l + 1, r - m);
    if (L <= m) update(L, R, C, l, m, rt << 1);
    if (R > m)  update(L, R, C, m + 1, r, rt << 1 | 1);
    push_up(rt);
}

// 区间查询 [L, R]（带 lazy）
int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) return seg[rt].val;
    if (L > r || R < l)   return 0;
    int m = (l + r) >> 1;
    push_down(rt, m - l + 1, r - m);
    return query(L, R, l, m, rt << 1) + query(L, R, m + 1, r, rt << 1 | 1);
}

适用变体：把 push_up 中的 + 换成 max/min/gcd 即可支持 RMQ。

三、二分模板

3.1 二分答案标准框架

场景：最大值最小化 / 最小值最大化 / 第 k 小
前提：check(x) 必须单调（x 增大，结果单调变化）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

ll l = lo, r = hi, ans = r;
while (l <= r) {
    ll mid = (l + r) >> 1;
    if (check(mid)) {
        ans = mid;
        r = mid - 1;   // 求最小满足值
        // l = mid + 1;  // 求最大满足值（二选一）
    } else {
        l = mid + 1;
        // r = mid - 1;
    }
}
return ans;

3.2 贪心判定：序列划分为 m 段

场景：最小化最大段和。check(x) 判断每段和 ≤ x 时，段数 ≤ m？

1
2
3
4
5
6
7
8
9

int check(ll x) {
    ll sum = 0; int cnt = 1;
    for (int i = 1; i <= n; i++) {
        if (a[i] > x) return INF;       // 单元素超上限
        if (sum + a[i] <= x) sum += a[i];
        else sum = a[i], cnt++;
    }
    return cnt;  // 返回最少段数
}

3.3 双指针统计

场景：两个有序数组 a[1..n]、b[1..m]，求满足 a[i] + b[j] ≤ x 的对数

1
2
3
4
5
6
7
8

ll count_le(ll x) {
    ll cnt = 0; int j = m;
    for (int i = 1; i <= n; i++) {
        while (j > 0 && a[i] + b[j] > x) j--;
        cnt += j;
    }
    return cnt;
}

四、KMP 字符串匹配

场景：在母串 A（长 n）中找模式串 B（长 m）的所有出现位置
复杂度：O(n + m)
注意：字符串下标从 1 开始

4.1 next 数组预处理

P[j] 含义：匹配到 j 失败时，j 回退到的位置。P[1] = 0。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int P[MAXN];  // next 数组（有时命名 next 与 std 冲突，故用 P）

void pre() {
    P[1] = 0;
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && B[j + 1] != B[i + 1])
            j = P[j];
        if (B[j + 1] == B[i + 1])
            j++;
        P[i + 1] = j;
    }
}

4.2 KMP 匹配

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int kmp_count() {
    int ans = 0, j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && B[j + 1] != A[i + 1])
            j = P[j];
        if (B[j + 1] == A[i + 1])
            j++;
        if (j == m) {
            ans++;  // 匹配成功一次
            j = P[j];  // 允许重叠，继续匹配
        }
    }
    return ans;
}

4.3 扩展：最长公共前后缀

求 S1 的前缀 ∩ S2 的后缀的最长串：拼 S1 + "#" + S2，跑 KMP，最后的 P[len] 即为答案长度。

五、矩阵快速幂

场景：大 n 递推（n ≤ 10⁹），如斐波那契
复杂度：O(k³ log n)，k 为矩阵维度

5.1 整数快速幂

1
2
3
4
5
6
7
8
9

ll qpow(ll a, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

5.2 矩阵乘（cache 优化版）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

struct Matrix {
    ll m[K][K];  // K 为最大维度
    Matrix() { memset(m, 0, sizeof(m)); }
};

// cache-friendly 循环顺序：i → k → j（b 的行优先访问）
Matrix mul(Matrix a, Matrix b, int n) {
    Matrix c;
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            if (a.m[i][k])                        // 稀疏优化
                for (int j = 0; j < n; j++)
                    c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
    return c;
}

5.3 矩阵快速幂

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Matrix mat_pow(Matrix a, ll n, int dim) {
    Matrix res;
    for (int i = 0; i < dim; i++) res.m[i][i] = 1;  // 单位矩阵
    while (n) {
        if (n & 1) res = mul(res, a, dim);
        a = mul(a, a, dim);
        n >>= 1;
    }
    return res;
}

5.4 递推 → 矩阵构造速查

递推式转移矩阵 B状态向量 C(n)
f(n) = a·f(n-1) + b·f(n-2)[[a,b],[1,0]][f(n), f(n-1)]ᵀ
f(n) = a·f(n-1) + b·f(n-3) + c[[a,0,b,1],[1,0,0,0],[0,1,0,0],[0,0,0,1]][f(n),f(n-1),f(n-2),c]ᵀ

关键：C(n) = B^(n-start) × C(start)，其中 start 为已知初值的最小下标。

前缀和嵌入：在状态向量末尾加一个 S[n] 分量，转移矩阵对应行填好递推系数 + 对角线 1 即可。

六、数论 — 逆元

场景：模运算中"除以一个数"（乘法逆元代替除法）
前提：模数 P 为质数时用费马小定理；一般模数用扩欧

6.1 欧几里得 (gcd)

1

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

6.2 扩展欧几里得

求 ax + by = gcd(a, b) 的一组解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

ll ex_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll d = ex_gcd(b, a % b, x, y);
    ll tmp = x; x = y; y = tmp - (a / b) * y;
    return d;
}

// 求 a 在模 m 下的逆元（gcd(a, m) == 1）
ll mod_inv(ll a, ll m) {
    ll x, y;
    ex_gcd(a, m, x, y);
    return (x % m + m) % m;  // 保证非负最小解
}

6.3 费马小定理求逆元（模数必须为质数）

1

ll inv(ll x) { return qpow(x, MOD - 2); }  // x^(p-2) mod p

6.4 线性求逆元（O(n) 预处理 1..n 的逆元）

1
2
3
4

ll inv[MAXN];
inv[1] = 1;
for (int i = 2; i <= N; i++)
    inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;

七、中国剩余定理 (CRT)

场景：求解同余方程组 x ≡ a[i] (mod m[i])

7.1 标准 CRT — 模数两两互质

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// m[] 两两互质，a[] 为余数，n 为方程个数，M = ∏m[i]
ll crt(ll m[], ll a[], int n) {
    ll M = 1, ans = 0;
    for (int i = 0; i < n; i++) M *= m[i];

    for (int i = 0; i < n; i++) {
        ll Mi = M / m[i];
        ll xi = mod_inv(Mi, m[i]);     // Mi 在模 m[i] 下的逆元
        ans = (ans + a[i] * Mi % M * xi) % M;
    }
    return ans;
}

7.2 扩展 CRT — 模数不互质

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

ll ex_crt(ll m[], ll a[], int n) {
    ll M = m[0], x = a[0];  // 前 i 个方程的 lcm 和解

    for (int i = 1; i < n; i++) {
        ll c = ((a[i] - x) % m[i] + m[i]) % m[i];  // 防负数
        ll t, y;
        ll d = ex_gcd(M, m[i], t, y);
        if (c % d) return -1;  // 无解

        t = (__int128)t * (c / d) % (m[i] / d);  // 注意防溢出
        // 或用：t = (t * (c / d) % (m[i] / d) + m[i] / d) % (m[i] / d);
        x = x + t * M;
        M = M / d * m[i];    // M = lcm
        x = (x % M + M) % M;
    }
    return x;
}

八、Dijkstra 堆优化

场景：稀疏图单源最短路，无负权边
复杂度：O(E log E)
核心组件：链式前向星存图 + priority_queue 小根堆

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

const int MAXN = 100005, MAXM = 200005;  // 无向边数×2

int head[MAXN], dist[MAXN], vis[MAXN], cnt;

struct Edge {
    int to, w, next;
} edge[MAXM];

void add_edge(int u, int v, int w) {
    edge[++cnt] = {v, w, head[u]};
    head[u] = cnt;
}

struct Node {
    int id, d;
    bool operator<(const Node &o) const { return d > o.d; }  // 小根堆
};

void dijkstra(int s, int n) {
    priority_queue<Node> q;
    fill(dist, dist + n + 1, INF);
    dist[s] = 0; q.push({s, 0});

    while (!q.empty()) {
        int u = q.top().id; q.pop();
        if (vis[u]) continue;          // 关键：已确定最短路则跳过
        vis[u] = 1;

        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to, w = edge[i].w;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                q.push({v, dist[v]});  // 可能多次入队，vis 处理冗余
            }
        }
    }
}

九、最短路径全家桶

9.1 Floyd — 全源最短路

场景：n ≤ 400，求任意两点最短路，可处理负权
复杂度：O(n³)

1
2
3
4
5
6
7
8
9

int dis[MAXN][MAXN];  // 初始化：dis[i][i]=0, 无边为 INF

void floyd(int n) {
    for (int k = 1; k <= n; k++)          // 注意：k 必须在最外层
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dis[i][k] < INF && dis[k][j] < INF)
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

9.2 Bellman-Ford — 单源最短路（可负权）

场景：有负权边，需检测负环
复杂度：O(n·m)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

struct Edge { int u, v, w; } edges[MAXM];
int dist[MAXN];

bool bellman_ford(int s, int n, int m) {
    fill(dist, dist + n + 1, INF);
    dist[s] = 0;

    for (int i = 1; i <= n - 1; i++) {        // n-1 轮松弛
        bool updated = false;
        for (int j = 0; j < m; j++) {
            int u = edges[j].u, v = edges[j].v, w = edges[j].w;
            if (dist[u] < INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;                   // 提前退出
    }

    // 第 n 轮检测负环
    for (int j = 0; j < m; j++) {
        int u = edges[j].u, v = edges[j].v, w = edges[j].w;
        if (dist[u] < INF && dist[u] + w < dist[v])
            return false;  // 存在负环
    }
    return true;  // 无负环
}

9.3 SPFA — 队列优化版

场景：稀疏图 + 负权（但可能被卡）
平均复杂度：O(E)，最坏 O(V·E)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int head[MAXN], dist[MAXN], inq[MAXN], cnt;  // inq: 是否在队列中

void spfa(int s, int n) {
    queue<int> q;
    fill(dist, dist + n + 1, INF);
    dist[s] = 0; inq[s] = 1; q.push(s);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = 0;

        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to, w = edge[i].w;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inq[v]) { inq[v] = 1; q.push(v); }
            }
        }
    }
}

9.4 算法选择速查

场景算法复杂度
稀疏图 + 无负权堆优化 DijkstraO(E log E)
稠密图 + 无负权 (n ≤ 2000)朴素 DijkstraO(n²)
全源 + n ≤ 400FloydO(n³)
有负权 + 稳定Bellman-FordO(n·m)
有负权 + 图稀疏SPFAO(E) 平均
检测负环Bellman-Ford / SPFA—

十、图论基础工具

10.1 链式前向星图遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// BFS — 适合无权图最短路（层序遍历）
void bfs(int start) {
    queue<int> q; q.push(start); vis[start] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (!vis[v]) { vis[v] = 1; q.push(v); }
        }
    }
}

// DFS — 连通分量 / 拓扑序 / 环检测
void dfs(int u) {
    vis[u] = 1;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (!vis[v]) dfs(v);
    }
}

10.2 map 映射建图

场景：节点名为字符串（如城市名），映射到整数编号

1
2
3
4
5
6
7
8
9

map<string, int> idx;
int get_id(string s) {
    if (!idx.count(s)) idx[s] = idx.size() + 1;  // 编号从 1 开始
    return idx[s];
}

// 建边
int u = get_id("杭州"), v = get_id("北京");
add_edge(u, v, w);
最后更新于 2026-06-5, 10:51 CST