一、 数据结构

并查集
树状数组与线段树
单调栈与单调队列

二、 图论

最短路径算法
最小生成树
拓扑排序与关键路径
连通性问题

三、 字符串与搜索

KMP算法
Trie字典树
哈希

四、 高级技巧与优化思想

倍增算法：ST表、最近公共祖先
快速幂
离散化
树上前缀和与差分

一、数据结构

1. 并查集

📌 核心用途

维护动态连通性：快速查询两个元素是否属于同一个集合、快速合并两个集合；带权并查集还能维护元素间的相对关系（如距离、权值、逻辑关系）。

🎯 适用题型

1. 基础：朋友圈 / 岛屿连通、判断两点是否连通
2. 进阶：最小生成树（Kruskal 算法）、带权关系问题（食物链、奇偶游戏）
3. 拓展：动态连通性、离线连通查询

💻 拓展用法：普通并查集 + 带权并查集（核心拓展）

并查集模板题 - 洛谷

#include <iostream>
#include <vector>
using namespace std;

// ===================== 1. 普通并查集（基础版） =====================
struct DSU {
    vector<int> fa; // 父节点数组
    // 初始化：每个元素的父节点是自己
    DSU(int n) { fa.resize(n + 1); for (int i = 1; i <= n; i++) fa[i] = i; }
    
    // 查找根节点 + 路径压缩（核心优化，让树变扁平）
    int find(int x) {
        if (fa[x] != x) fa[x] = find(fa[x]); // 递归找根，路径压缩
        return fa[x];
    }
    
    // 合并两个集合：把x的根挂到y的根上
    void unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx != ry) fa[rx] = ry;
    }
    
    // 判断x和y是否连通
    bool isConnected(int x, int y) { return find(x) == find(y); }
};

// ===================== 2. 带权并查集（拓展：维护节点到根的权值） =====================
// 用途：解决元素间有相对关系的问题（如食物链：A吃B，B吃C）
struct WeightDSU {
    vector<int> fa;  // 父节点
    vector<int> val; // val[x]：x到父节点fa[x]的权值
    
    WeightDSU(int n) {
        fa.resize(n + 1); val.resize(n + 1, 0);
        for (int i = 1; i <= n; i++) fa[i] = i;
    }
    
    // 带权查找 + 路径压缩
    int find(int x) {
        if (fa[x] != x) {
            int f = fa[x]; // 记录原父节点
            fa[x] = find(fa[x]); // 递归更新父节点为根
            val[x] += val[f]; // 更新x到根的权值（核心）
        }
        return fa[x];
    }
};

// 测试
int main() {
    DSU dsu(5);
    dsu.unite(1,2); dsu.unite(2,3);
    cout << dsu.isConnected(1,3); // 输出1（连通）
    return 0;
}

2. 树状数组（Fenwick Tree）

📌 核心用途

高效处理前缀和 / 单点修改：时间复杂度 O(logn)，代码极简、空间占用小；支持单点修改 + 区间查询、区间修改 + 单点查询、区间修改 + 区间查询。

🎯 适用题型

1. 基础：单点更新 + 区间求和、逆序对统计
2. 进阶：动态前缀和、区间增减 + 单点查询
3. 拓展：二维前缀和、离线区间查询

💻 拓展用法：区间修改 + 区间查询（最强拓展）

树状数组模板题 - 洛谷

#include <iostream>
#include <vector>
using namespace std;

// 树状数组：支持 区间修改 + 区间查询（核心拓展）
class FenwickTree {
private:
    vector<long long> tr1, tr2; // 两个树状数组维护差分
    int n;
    // 单点修改
    void add(vector<long long>& tr, int idx, long long val) {
        for (; idx <= n; idx += idx & -idx) tr[idx] += val;
    }
    // 前缀和查询
    long long query(vector<long long>& tr, int idx) {
        long long res = 0;
        for (; idx > 0; idx -= idx & -idx) res += tr[idx];
        return res;
    }
public:
    FenwickTree(int size) : n(size) {
        tr1.resize(n + 1, 0);
        tr2.resize(n + 1, 0);
    }
    // 区间修改：[l, r] 加 val
    void rangeAdd(int l, int r, long long val) {
        add(tr1, l, val);
        add(tr1, r + 1, -val);
        add(tr2, l, val * (l - 1));
        add(tr2, r + 1, -val * r);
    }
    // 区间查询：[1, x] 的前缀和
    long long preQuery(int x) {
        return x * query(tr1, x) - query(tr2, x);
    }
    // 区间查询：[l, r] 的和
    long long rangeQuery(int l, int r) {
        return preQuery(r) - preQuery(l - 1);
    }
};

// 测试
int main() {
    FenwickTree ft(5);
    ft.rangeAdd(1,3,2); // [1,3]加2
    cout << ft.rangeQuery(1,5); // 输出6（1+1+1+0+0=6）
    return 0;
}

3. 线段树

📌 核心用途

全能区间操作：支持区间修改、区间查询（求和 / 最值 /gcd），通过懒标记实现延迟更新，功能覆盖树状数组，适配所有复杂区间问题。

🎯 适用题型

1. 基础：区间加 / 乘 + 区间求和 / 最值
2. 进阶：区间赋值、区间覆盖、动态区间查询
3. 拓展：可持久化线段树、扫描线、动态开点

💻 拓展用法：区间加 + 区间求和（带懒标记，标准模板）

线段树模板题 - 洛谷

#include <iostream>
#include <vector>
using namespace std;

// 线段树：区间加法 + 区间求和（带懒标记）
class SegmentTree {
private:
    vector<long long> sum; // 区间和
    vector<long long> lazy; // 懒标记：延迟更新
    int n;
    // 向上更新：子节点更新父节点
    void pushUp(int p) { sum[p] = sum[p<<1] + sum[p<<1|1]; }
    // 向下更新：懒标记传递给子节点
    void pushDown(int p, int l, int r) {
        if (lazy[p] == 0) return;
        int mid = (l + r) >> 1;
        // 左孩子
        sum[p<<1] += lazy[p] * (mid - l + 1);
        lazy[p<<1] += lazy[p];
        // 右孩子
        sum[p<<1|1] += lazy[p] * (r - mid);
        lazy[p<<1|1] += lazy[p];
        // 清空当前节点懒标记
        lazy[p] = 0;
    }
    // 建树
    void build(int p, int l, int r, vector<long long>& a) {
        if (l == r) { sum[p] = a[l]; return; }
        int mid = (l + r) >> 1;
        build(p<<1, l, mid, a);
        build(p<<1|1, mid+1, r, a);
        pushUp(p);
    }
    // 区间修改
    void rangeAdd(int p, int l, int r, int ul, int ur, long long val) {
        if (ul <= l && r <= ur) {
            sum[p] += val * (r - l + 1);
            lazy[p] += val;
            return;
        }
        pushDown(p, l, r);
        int mid = (l + r) >> 1;
        if (ul <= mid) rangeAdd(p<<1, l, mid, ul, ur, val);
        if (ur > mid) rangeAdd(p<<1|1, mid+1, r, ul, ur, val);
        pushUp(p);
    }
    // 区间查询
    long long rangeQuery(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 += rangeQuery(p<<1, l, mid, ql, qr);
        if (qr > mid) res += rangeQuery(p<<1|1, mid+1, r, ql, qr);
        return res;
    }
public:
    SegmentTree(vector<long long>& a) {
        n = a.size() - 1;
        sum.resize(4 * n);
        lazy.resize(4 * n, 0);
        build(1, 1, n, a);
    }
    void add(int l, int r, long long val) { rangeAdd(1, 1, n, l, r, val); }
    long long query(int l, int r) { return rangeQuery(1, 1, n, l, r); }
};

// 测试
int main() {
    vector<long long> a = {0,1,2,3,4,5}; // 下标从1开始
    SegmentTree st(a);
    st.add(1,3,2); // [1,3]加2 → 3,4,5,4,5
    cout << st.query(1,5); // 输出21
    return 0;
}

4. 单调栈

📌 核心用途

线性时间 \(O(n)\) 找到每个元素 左 / 右边 第一个比它大 / 小的元素，解决矩形面积、接雨水、下一个更大元素等问题。

🎯 适用题型

1. 基础：下一个更大 / 更小元素、每日温度
2. 进阶：柱状图最大矩形、接雨水、矩形最大面积
3. 拓展：环形数组单调栈、区间最值维护

💻 拓展用法：柱状图最大矩形（经典高频题）

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 单调栈：柱状图中最大的矩形（核心拓展题型）
int largestRectangleArea(vector<int>& heights) {
    stack<int> st; // 单调递增栈：存储下标，对应高度递增
    st.push(-1); // 哨兵：避免栈空判断
    int maxArea = 0, n = heights.size();
    for (int i = 0; i < n; i++) {
        // 当前高度 < 栈顶高度：弹出栈顶，计算以栈顶为高的矩形面积
        while (st.top() != -1 && heights[i] < heights[st.top()]) {
            int h = heights[st.top()]; st.pop();
            int w = i - st.top() - 1; // 宽度 = 右边界 - 左边界 -1
            maxArea = max(maxArea, h * w);
        }
        st.push(i);
    }
    // 处理栈中剩余元素
    while (st.top() != -1) {
        int h = heights[st.top()]; st.pop();
        int w = n - st.top() - 1;
        maxArea = max(maxArea, h * w);
    }
    return maxArea;
}

// 测试
int main() {
    vector<int> h = {2,1,5,6,2,3};
    cout << largestRectangleArea(h); // 输出10
    return 0;
}

5. 单调队列

📌 核心用途

线性时间 \(O(n)\) 维护滑动窗口内的最值，是解决滑动窗口问题的最优解，也可优化动态规划。

🎯 适用题型

1. 基础：滑动窗口最大值 / 最小值
2. 进阶：单调队列优化 DP（多重背包、线性 DP）

💻 拓展用法：滑动窗口最大值（标准模板）

单调栈 & 单调队列 入门题单 - 洛谷

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

// 单调队列：滑动窗口最大值
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> q; // 单调递减队列：存储下标，对应数值递减
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        // 1. 移除窗口外的元素（左边界出窗）
        while (!q.empty() && q.front() <= i - k) q.pop_front();
        // 2. 维护单调递减：移除队尾比当前元素小的元素
        while (!q.empty() && nums[i] >= nums[q.back()]) q.pop_back();
        q.push_back(i);
        // 3. 窗口形成后，记录队首（最大值）
        if (i >= k - 1) res.push_back(nums[q.front()]);
    }
    return res;
}

// 测试
int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    vector<int> ans = maxSlidingWindow(nums, 3);
    for (int x : ans) cout << x << " "; // 输出3 3 5 5 6 7
    return 0;
}

二、图论

1. 最短路径算法

📌 核心用途

求图中单源 / 多源最短路径长度，判断负权环；分 4 种算法：

• Dijkstra：无负权边的单源最短路
• SPFA：有负权边 / 判负环
• Floyd：全源最短路

🎯 适用题型

单源最短路、多源最短路、负权边、负环判断、最短路计数、路径还原

💻 拓展用法：堆优化 Dijkstra（最常用）+ Floyd（全源）

【普及】最短路专项训练 - 洛谷

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;

// ===================== 1. 堆优化Dijkstra（无负权单源最短路） =====================
vector<int> dijkstra(int start, int n, vector<vector<pair<int, int>>>& g) {
    vector<int> dis(n + 1, INF); // 距离数组：初始无穷大
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 小根堆
    dis[start] = 0;
    pq.emplace(0, start);
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dis[u]) continue; // 已更新过，跳过
        for (auto [v, w] : g[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.emplace(dis[v], v);
            }
        }
    }
    return dis;
}

// ===================== 2. Floyd（全源最短路） =====================
void floyd(int n, vector<vector<int>>& g) {
    for (int k = 1; k <= n; k++) // 中间节点
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

// 测试
int main() {
    int n = 3;
    vector<vector<pair<int, int>>> g(n + 1);
    g[1].emplace_back(2,1); g[2].emplace_back(3,2); g[1].emplace_back(3,5);
    vector<int> dis = dijkstra(1, n, g);
    cout << dis[3]; // 输出3
    return 0;
}

2. 最小生成树（MST）

📌 核心用途

求无向连通图中连接所有节点的总权值最小的边集，总权值最小。

🎯 适用题型

最小生成树、最小代价连通、次小生成树、最小瓶颈生成树

💻 拓展用法：Kruskal 算法（并查集实现，最常用）

【图论2-3】最小生成树 - 洛谷

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 并查集（复用前文）
struct DSU {
    vector<int> fa;
    DSU(int n) { fa.resize(n+1); for(int i=1;i<=n;i++)fa[i]=i; }
    int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }
    bool unite(int x,int y) {
        int rx=find(x), ry=find(y);
        if(rx==ry) return false;
        fa[rx]=ry; return true;
    }
};

// 边结构体
struct Edge { int u, v, w; };
// Kruskal算法：最小生成树
int kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(), [](Edge& a, Edge& b){return a.w < b.w;}); // 边按权值升序
    DSU dsu(n);
    int total = 0, cnt = 0; // total：总权值，cnt：选中的边数
    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) { // 不连通则选中
            total += e.w;
            cnt++;
            if (cnt == n - 1) break; // 生成树有n-1条边
        }
    }
    return total;
}

// 测试
int main() {
    int n=3;
    vector<Edge> e = {{1,2,1},{2,3,2},{1,3,5}};
    cout << kruskal(n,e); // 输出3
    return 0;
}

3. 拓扑排序

📌 核心用途

对有向无环图（DAG）进行线性排序，判断图是否有环，解决任务依赖 / 调度问题。

🎯 适用题型

课程表、任务调度、判断有向环、依赖关系排序

💻 拓展用法：Kahn 算法（入度 + 队列，标准模板）

【图论】拓扑排序专题训练 - 洛谷

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 拓扑排序：返回拓扑序列，若长度≠n则有环
vector<int> topoSort(int n, vector<vector<int>>& g) {
    vector<int> inDegree(n + 1, 0); // 入度数组
    for (int u = 1; u <= n; u++)
        for (int v : g[u]) inDegree[v]++;
    queue<int> q;
    // 入度为0的节点入队
    for (int i = 1; i <= n; i++)
        if (inDegree[i] == 0) q.push(i);
    vector<int> res;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        res.push_back(u);
        for (int v : g[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) q.push(v);
        }
    }
    return res;
}

// 测试
int main() {
    int n=3;
    vector<vector<int>> g(n+1);
    g[1].push_back(2); g[2].push_back(3);
    vector<int> ans = topoSort(n,g);
    for(int x:ans) cout<<x<<" "; // 输出1 2 3
    return 0;
}

4. 关键路径

📌 核心用途

在AOE 网（带权 DAG）中找工程最短完成时间和关键活动，定位工程瓶颈。

🎯 适用题型

工程调度、关键任务、DAG 最长路径

💻 拓展用法：拓扑排序 + 关键路径计算

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;

// 关键路径算法（AOE网）
void criticalPath(int n, vector<vector<pair<int, int>>>& g) {
    vector<int> in(n+1,0), out(n+1,0);
    vector<int> ve(n+1,0), vl(n+1,INF); // ve：最早开始时间，vl：最晚开始时间
    // 1. 拓扑排序求ve（最早时间）
    queue<int> q; q.push(1); ve[1]=0;
    vector<int> topo;
    while(!q.empty()){
        int u=q.front(); q.pop(); topo.push_back(u);
        for(auto [v,w]:g[u]){
            in[v]--; ve[v]=max(ve[v], ve[u]+w);
            if(in[v]==0) q.push(v);
        }
    }
    // 2. 逆拓扑求vl（最晚时间）
    vl[topo.back()] = ve[topo.back()];
    for(int i=topo.size()-1;i>=0;i--){
        int u=topo[i];
        for(auto [v,w]:g[u]) vl[u]=min(vl[u], vl[v]-w);
    }
    // 3. 输出关键路径（ve[u]==vl[u]的节点）
    cout<<"关键路径：";
    for(int x:topo) if(ve[x]==vl[x]) cout<<x<<" ";
}

// 测试
int main() {
    int n=4;
    vector<vector<pair<int, int>>> g(n+1);
    g[1].emplace_back(2,3); g[1].emplace_back(3,2); g[2].emplace_back(4,2); g[3].emplace_back(4,3);
    criticalPath(n,g); // 输出1 3 4
    return 0;
}

5. 连通性问题（强连通分量 SCC）

📌 核心用途

找有向图的强连通分量，缩点（将分量转为一个点，简化图为 DAG），判断割点 / 桥。

🎯 适用题型

强连通分量、缩点、2-SAT、有向图连通性、割点 / 桥

💻 拓展用法：Tarjan 算法求 SCC + 缩点

连通性问题 - 洛谷

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

// Tarjan算法：求强连通分量
class TarjanSCC {
public:
    vector<vector<int>> g, newG; // 原图、缩点后新图
    vector<int> dfn, low, belong; // dfn：时间戳，low：追溯值，belong：所属分量
    stack<int> st; vector<bool> inSt;
    int idx, cnt; // idx：时间戳，cnt：分量编号
    TarjanSCC(int n, vector<vector<int>>& graph) : g(graph) {
        dfn.resize(n+1,0); low.resize(n+1,0); belong.resize(n+1,0); inSt.resize(n+1,false);
        idx = cnt = 0;
        for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
        buildNewGraph(n); // 缩点建图
    }
    void tarjan(int u) {
        dfn[u]=low[u]=++idx; st.push(u); inSt[u]=true;
        for(int v:g[u]){
            if(!dfn[v]) tarjan(v), low[u]=min(low[u], low[v]);
            else if(inSt[v]) low[u]=min(low[u], dfn[v]);
        }
        if(dfn[u]==low[u]){ // 找到SCC
            cnt++; int v;
            do{ v=st.top(); st.pop(); inSt[v]=false; belong[v]=cnt; }while(v!=u);
        }
    }
    void buildNewGraph(int n) { // 缩点
        newG.resize(cnt+1);
        for(int u=1;u<=n;u++)
            for(int v:g[u])
                if(belong[u]!=belong[v])
                    newG[belong[u]].push_back(belong[v]);
    }
};

// 测试
int main() {
    int n=3;
    vector<vector<int>> g(n+1);
    g[1].push_back(2); g[2].push_back(3); g[3].push_back(2);
    TarjanSCC scc(n,g);
    cout<<scc.cnt; // 输出2（分量：{1},{2,3}）
    return 0;
}

三、字符串与搜索

1. KMP 算法

📌 核心用途

线性时间字符串模式匹配：\(O(n+m)\) 找到模式串在主串中的所有位置，避免暴力回溯。

🎯 适用题型

子串匹配、重复子串、字符串周期、前缀函数应用

💻 拓展用法：KMP 匹配 + 求最小循环节

KMP 相关 - 洛谷

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// KMP算法：模式匹配 + 最小循环节
class KMP {
public:
    vector<int> ne; // 前缀函数数组
    string s, p; // 主串、模式串
    KMP(string& str, string& pat) : s(str), p(pat) {
        int m = p.size(); ne.resize(m,0);
        // 1. 预处理前缀函数
        for(int i=1,j=0;i<m;i++){
            while(j && p[i]!=p[j]) j=ne[j-1];
            if(p[i]==p[j]) j++;
            ne[i]=j;
        }
    }
    // 2. 模式匹配：返回所有匹配起始下标
    vector<int> match() {
        vector<int> res;
        int n=s.size(), m=p.size();
        for(int i=0,j=0;i<n;i++){
            while(j && s[i]!=p[j]) j=ne[j-1];
            if(s[i]==p[j]) j++;
            if(j==m) { res.push_back(i-m+1); j=ne[j-1]; }
        }
        return res;
    }
    // 3. 拓展：求模式串的最小循环节
    int getMinCycle() {
        int m=p.size();
        int len = m - ne.back();
        return m%len==0 ? len : m;
    }
};

// 测试
int main() {
    string s="ababaabab", p="abab";
    KMP kmp(s,p);
    vector<int> ans = kmp.match();
    for(int x:ans) cout<<x<<" "; // 输出0 4
    cout<<kmp.getMinCycle(); // 输出2（ab）
    return 0;
}

2. Trie 字典树

📌 核心用途

高效存储 / 查询字符串：按字符前缀存储，支持前缀匹配、单词检索、去重；01-Trie可求数字异或最值。

🎯 适用题型

前缀匹配、单词检索、字符串去重、最大异或对

💻 拓展用法：字符串 Trie + 01-Trie（求最大异或对）

Trie 树 基础练习 - 洛谷

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// ===================== 1. 字符串Trie =====================
class Trie {
private:
    vector<vector<int>> tr;
    vector<int> cnt;
    int idx;
public:
    Trie() : tr(1, vector<int>(26,0)), cnt(1,0), idx(0) {}
    // 插入字符串
    void insert(string& s) {
        int p=0;
        for(char c:s){
            int u=c-'a';
            if(!tr[p][u]) tr.emplace_back(26,0), cnt.push_back(0), tr[p][u]=++idx;
            p=tr[p][u];
        }
        cnt[p]++;
    }
    // 查询字符串是否存在
    int query(string& s) {
        int p=0;
        for(char c:s){
            int u=c-'a';
            if(!tr[p][u]) return 0;
            p=tr[p][u];
        }
        return cnt[p];
    }
};

// ===================== 2. 01-Trie（拓展：求最大异或对） =====================
class Trie01 {
private:
    vector<vector<int>> tr;
    int idx;
public:
    Trie01() : tr(1, vector<int>(2,0)), idx(0) {}
    void insert(int x) {
        int p=0;
        for(int i=31;i>=0;i--){
            int u=(x>>i)&1;
            if(!tr[p][u]) tr.emplace_back(2,0), tr[p][u]=++idx;
            p=tr[p][u];
        }
    }
    int query(int x) {
        int p=0, res=0;
        for(int i=31;i>=0;i--){
            int u=(x>>i)&1;
            if(tr[p][!u]) res|=(1<<i), p=tr[p][!u];
            else p=tr[p][u];
        }
        return res;
    }
};

// 测试
int main() {
    // 字符串Trie
    Trie t; string s1="abc",s2="ab";
    t.insert(s1); t.insert(s2);
    cout<<t.query("ab")<<" "; // 输出1
    
    // 01-Trie：最大异或对
    Trie01 t01;
    vector<int> nums={1,2,3};
    for(int x:nums) t01.insert(x);
    int maxXor=0;
    for(int x:nums) maxXor=max(maxXor, t01.query(x));
    cout<<maxXor; // 输出3
    return 0;
}

3. 字符串哈希

📌 核心用途

将字符串转为唯一哈希值，\(O(1)\) 比较字符串是否相等，快速查询子串哈希，避免 KMP 的复杂前缀函数。

🎯 适用题型

子串判等、回文串判断、字符串匹配、最长重复子串

💻 拓展用法：自然溢出哈希 + 子串查询（防冲突）

哈希：从入门到入土 - 洛谷

#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef unsigned long long ull;
const int base = 131; // 进制基数

// 字符串哈希：自然溢出 + 子串哈希查询
class StringHash {
public:
    vector<ull> h, p; // h：哈希前缀和，p：基数幂
    StringHash(string& s) {
        int n=s.size();
        h.resize(n+1,0); p.resize(n+1,1);
        for(int i=0;i<n;i++){
            h[i+1]=h[i]*base + s[i];
            p[i+1]=p[i]*base;
        }
    }
    // 查询子串s[l..r]的哈希值（下标从0开始）
    ull getHash(int l, int r) {
        return h[r+1] - h[l]*p[r-l+1];
    }
};

// 测试
int main() {
    string s="abcabc";
    StringHash sh(s);
    // 判断s[0..2]和s[3..5]是否相等
    if(sh.getHash(0,2)==sh.getHash(3,5)) cout<<"相等"; // 输出相等
    return 0;
}

四、高级技巧与优化思想

1. 倍增算法（ST 表 + LCA）

📌 核心用途

• ST 表：\(O(nlogn)\) 预处理，\(O(1)\) 查询静态区间最值（无修改）
• LCA：\(O(nlogn)\) 预处理，\(O(logn)\) 查询树上最近公共祖先

🎯 适用题型

静态区间最值、树上路径查询、LCA 求两点距离

💻 拓展用法：ST 表（区间最值）+ 倍增 LCA

ST表 - 洛谷

倍增练习 - 洛谷

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;
const int LOG = 20;

// ===================== 1. ST表：静态区间最值 =====================
class ST {
public:
    vector<vector<int>> st;
    vector<int> logn;
    ST(vector<int>& a) {
        int n=a.size()-1;
        logn.resize(n+1); st.resize(LOG, vector<int>(n+1));
        // 预处理log2值
        logn[1]=0; for(int i=2;i<=n;i++) logn[i]=logn[i/2]+1;
        // 初始化
        for(int i=1;i<=n;i++) st[0][i]=a[i];
        // 倍增预处理
        for(int j=1;j<LOG;j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
                st[j][i]=max(st[j-1][i], st[j-1][i+(1<<(j-1))]);
    }
    // 查询区间[l,r]最大值
    int query(int l, int r) {
        int k=logn[r-l+1];
        return max(st[k][l], st[k][r-(1<<k)+1]);
    }
};

// ===================== 2. 倍增LCA：树上最近公共祖先 =====================
class LCA {
public:
    vector<vector<int>> g, up;
    vector<int> dep;
    int n;
    LCA(int size, vector<vector<int>>& graph) : n(size), g(graph) {
        up.resize(LOG, vector<int>(n+1));
        dep.resize(n+1,0);
        dfs(1,0); // 根节点1，父节点0
    }
    void dfs(int u, int fa) {
        up[0][u]=fa; dep[u]=dep[fa]+1;
        for(int j=1;j<LOG;j++) up[j][u]=up[j-1][up[j-1][u]];
        for(int v:g[u]) if(v!=fa) dfs(v,u);
    }
    int lca(int u, int v) {
        if(dep[u]<dep[v]) swap(u,v);
        // 把u提到和v同一深度
        for(int j=LOG-1;j>=0;j--)
            if(dep[up[j][u]]>=dep[v]) u=up[j][u];
        if(u==v) return u;
        // 一起向上跳
        for(int j=LOG-1;j>=0;j--)
            if(up[j][u]!=up[j][v]) u=up[j][u], v=up[j][v];
        return up[0][u];
    }
};

// 测试
int main() {
    // ST表测试
    vector<int> a={0,1,3,2,5,4};
    ST st(a);
    cout<<st.query(2,5)<<" "; // 输出5
    
    // LCA测试
    int n=5;
    vector<vector<int>> g(n+1);
    g[1].push_back(2); g[1].push_back(3); g[2].push_back(4); g[2].push_back(5);
    LCA lca(n,g);
    cout<<lca.lca(4,5); // 输出2
    return 0;
}

2. 快速幂

📌 核心用途

\(O(logb)\) 快速计算 \(a^b \mod mod\)，避免暴力循环；矩阵快速幂可优化线性递推（如斐波那契）。

🎯 适用题型

幂运算取模、矩阵快速幂、乘法逆元、斐波那契优化

💻 拓展用法：快速幂 + 矩阵快速幂

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;

// ===================== 1. 快速幂 =====================
ll qpow(ll a, ll b) {
    ll res=1;
    while(b) {
        if(b&1) res=res*a%mod; // 二进制位为1，乘入结果
        a=a*a%mod; // 底数平方
        b>>=1; // 右移一位
    }
    return res;
}

// ===================== 2. 矩阵快速幂（拓展：斐波那契） =====================
typedef vector<vector<ll>> Matrix;
Matrix mul(Matrix& a, Matrix& b) { // 矩阵乘法
    Matrix res(2, vector<ll>(2,0));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                res[i][j]=(res[i][j]+a[i][k]*b[k][j])%mod;
    return res;
}
Matrix matrixQpow(Matrix a, ll n) { // 矩阵快速幂
    Matrix res={{1,0},{0,1}}; // 单位矩阵
    while(n) {
        if(n&1) res=mul(res,a);
        a=mul(a,a);
        n>>=1;
    }
    return res;
}
// 求斐波那契第n项
ll fib(ll n) {
    if(n<=2) return 1;
    Matrix a={{1,1},{1,0}};
    Matrix res=matrixQpow(a,n-2);
    return (res[0][0]+res[0][1])%mod;
}

// 测试
int main() {
    cout<<qpow(2,10)<<" "; // 输出1024
    cout<<fib(10); // 输出55
    return 0;
}

3. 离散化

📌 核心用途

将大范围数值（如 1e9）映射为小范围连续下标（如 1e5），节省空间，适配树状数组 / 线段树。

🎯 适用题型

数据范围大但元素少、逆序对、权值线段树、区间覆盖

💻 拓展用法：去重离散化（标准模板）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 离散化：大数值→小下标
vector<int> discretization(vector<int>& a) {
    vector<int> b = a; // 备份数组
    sort(b.begin(), b.end()); // 排序
    b.erase(unique(b.begin(), b.end()), b.end()); // 去重
    // 映射：a[i] → 离散化后的下标
    for(int& x:a) x=lower_bound(b.begin(), b.end(),x)-b.begin()+1; // +1避免0下标
    return a;
}

// 测试
int main() {
    vector<int> a={100,20,300,20,50};
    vector<int> ans=discretization(a);
    for(int x:ans) cout<<x<<" "; // 输出3 1 4 1 2
    return 0;
}

4. 树上前缀和与差分

📌 核心用途

树上路径修改 / 查询：差分\(O(1)\) 完成路径修改，前缀和\(O(n)\) 统计结果，简化树上复杂操作。

🎯 适用题型

树上路径加、路径求和、子树修改、树上差分优化

💻 拓展用法：树上点差分（路径修改 + 查询）

【算法2-1】前缀和、差分与离散化 - 洛谷

#include <iostream>
#include <vector>
using namespace std;

// 树上点差分：路径[u,v]加val + 单点查询
class TreeDiff {
public:
    vector<vector<int>> g;
    vector<int> val, dep, fa;
    int n;
    TreeDiff(int size, vector<vector<int>>& graph) : n(size), g(graph) {
        val.resize(n+1,0); dep.resize(n+1,0); fa.resize(n+1,0);
        dfs(1,0); // 预处理父节点+深度
    }
    void dfs(int u, int f) {
        fa[u]=f; dep[u]=dep[f]+1;
        for(int v:g[u]) if(v!=f) dfs(v,u);
    }
    // 倍增LCA（复用前文）
    int lca(int u, int v) {
        if(dep[u]<dep[v]) swap(u,v);
        while(dep[u]>dep[v]) u=fa[u];
        while(u!=v) u=fa[u],v=fa[v];
        return u;
    }
    // 路径[u,v]加val
    void addPath(int u, int v, int num) {
        int ancestor=lca(u,v);
        val[u]+=num;
        val[v]+=num;
        val[ancestor]-=num;
        if(fa[ancestor]) val[fa[ancestor]]-=num;
    }
    // 回溯统计：后序遍历求和
    void dfsSum(int u, int f) {
        for(int v:g[u]) if(v!=f) dfsSum(v,u), val[u]+=val[v];
    }
};

// 测试
int main() {
    int n=5;
    vector<vector<int>> g(n+1);
    g[1].push_back(2); g[1].push_back(3); g[2].push_back(4); g[2].push_back(5);
    TreeDiff td(n,g);
    td.addPath(4,5,2); // 路径4-2-5加2
    td.dfsSum(1,0);
    cout<<td.val[2]; // 输出2
    return 0;
}

总结

1. 数据结构：并查集管连通、树状数组 / 线段树管区间、单调栈 / 队列管线性最值；
2. 图论：最短路径求距离、生成树求最小连通、拓扑 / 关键路径管调度、连通性管缩点；
3. 字符串：KMP 精准匹配、Trie 管前缀、哈希快速判等；
4. 高级技巧：倍增提速查询、快速幂提速幂运算、离散化压缩数据、树上差分简化路径操作。