算法模板(C++)

摘要：适用于各种算法的模板框架(C++/Java)。

分类：数据结构与算法

标签：后端, 数据结构, 效率提升, 算法

发布时间：2025-08-14T13:23:33

---

我的算法模板

适用于各种算法的模板框架(C++/Java)。

C++模板

#include<iostream>
#include<algorithm>
#include<string>
#include<bits/stdc++.h>
#define it int
#define lli long long int
#define ll long long int
#define ld long double
#define ul unsigned long long int
#define dl double
#define st string
#define vb vector<bool>
#define vll vector <ll>
#define lll list <ll>
#define ls list<string>
#define lc list <char>
#define qll queue <ll>
#define stll stack <ll>
#define sll set <ll>
#define sts set <string>
#define vs vector <string>
#define pll pair <ll,ll>
#define mll map <ll,ll>
#define msl map <string,ll>
#define vecp vector < pair <ll, ll> >
#define vecpp vector < pair <ll, pair <ll, ll> > >
#define pb push_back
#define MP make_pair
#define pf push_front
#define in insert
#define eb emplace_back
#define ppb pop_back
#define ppf pop_front
 
using namespace std;
int main(){
        ios::sync_with_stdio(false);
         
        return 0;
}

快排O（logN）

void quickSort(int a[],int left,int right)
{
        //特判
        if(left>=right)
        {
             return;
        }
        //边界指针变量
        int i=left-1;
        int j=right+1;
        //划分依据（值划分）
        int x = a[right+left>>1];
        //对左右两部分进行排序
        while(i<j)
        {
             do i++;while(a[i]<x);
             do j--;while(a[j]>x);
         if(i<j)
         {
         swap(a[i],a[j]);
         }
        }
        //递归排序左边
        quickSort(a,left,j);
        //递归排序右边
        quickSort(a,j+1,right);
}

归排O（logN）

void mergeSort(int a[],int left,int right)
{        //特判
        if(left>=right)
        {
             return;
        }
        //划分依据（按值）
        int mid = right+left>>1;
        //递归排序左右部分
        mergeSort(a,left,mid);
        mergeSort(a,mid+1,right);
        //定义指针变量
        int k=0,i=left,j=mid+1;
        //对左右进行排序（双指针技巧）
        while(i<=mid && j<=right)
        {
         if(a[i]<a[j]) tmp[k++] = a[i++];
         else tmp[k++] = a[j++];
        }
        //将单个部分剩余的元素进行copy追加
        while(i<=mid) tmp[k++] = a[i++];
        while(j<=right) tmp[k++] = a[j++];
        //将排好序的元素从中间数值tmpCopy到原数组
        for(i=left,j=0;i<=right;i++,j++)
        {
             a[i] = tmp[j];
        }
}

整数二分

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分

//浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

高精度减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度乘法

vector<int> mul(vector<int> &A,int b)
{
    vector<int> ans;
    int t=0;
    for(int i=0;i<A.size()||t;i++)
    {
        if(i<A.size()) t+=A[i] * b;
        ans.push_back(t%10);
        t/=10;
    }
    while(ans.size()>1 && ans.back()==0) ans.pop_back();
    return ans;
}

高精度除法

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{    //商
    vector<int> C;
    //余数
    r = 0;
    //从最高位开始计算
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        //计算下一个余数
        r %= b;
    }
    //反转结果
    reverse(C.begin(), C.end());
    //除去前导0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

一维前缀和

S[i] = a[1] + a[2] + ... a[i]
//前缀和预处理(索引从1开始)
 s[i] = s[i-1]+a[i];
 //如果索引从开始
 s[i] = s[i-1]+a[i-1];
 //计算范围[l,r]前缀和
a[l] + ... + a[r] = S[r] - S[l - 1]
 //计算范围[l,r]前缀和（另一种情况）
a[l] + ... + a[r] = S[r+1] - S[l]

二维前缀和

S[i, j] = 第i行j列格子左上部分所有元素的和
S[i][j] = S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1] + a[i][j]; // 求前缀和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

一维差分

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x][y1] += c,
S[x2 + 1][ y1] -= c,
S[x][y2 + 1] -= c, 
S[x2 + 1][y2 + 1] += c

位运算

求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

双指针

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

离散化

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

区间合并

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

单链表(数组模拟)

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

//在某个位置后插入一个新节点
void insert(int k,int x)
{
    e[idx] = x,ne[idx] = ne[k],ne[k] = idx++;
}

//遍历链表
for(int i=head;i!=-1;i=ne[i])
{
cout<<e[i]<<" ";
}

双链表（数组模拟）

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a;
    r[idx] = r[a];
    l[r[a]] = idx;
    r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

//遍历链表
for(int i=R[0];i!=1;i = R[i])
{
        cout<<e[i]<<" ";
}

模拟栈

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0)
{

}

模拟队列

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt)
{

}

单调栈

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

单调队列

常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

KMP算法

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

//改进后的兼容版本【字符串或字符数组新式均可】

    /*计算模式串的next数组*/
    ne[0]=0;//特判
    for (int i = 1, j = 0; i <n; i ++ )
    {
        while (j && p[i] != p[j]) j = ne[j-1];
        if (p[i] == p[j]) j ++ ;
        ne[i] = j;
    }
       
    /*KMPp匹配*/
    for (int i = 0, j = 0; i <m; i ++ )
    {
        while (j && s[i] != p[j]) j = ne[j-1];
        if (s[i] == p[j]) j ++ ;
        if (j == n)
        {
            //printf("%d ", i - j+1);
            j = ne[j-1];
            //匹配成功后的逻辑
        }
    }

Trie树

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

并查集

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

模拟堆

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);