经典算法和数据结构

2026-03-05

数据结构算法 Cpp

对顶堆

用于解决数据流中位数问题

使用小根堆$A$和大根堆$B$

$A$存储数据中较大的一部分数据，$B$存储数据中较小的一部分数据

如果$A$和$B$元素个数相同，那么中位数为$A.top+B.top/2$

否则令$A$元素个数比$B$ 元素多一个，中位数为$A.top$

单调栈

应用一：$O(N)$时间求数组每个元素左右两边第一个比它大/小的元素下标

树状数组

int lowbit(int x){
	return x&-x;
}
void add(int x,int k){
	while(x<=n){
		s[x]+=k;
		x+=lowbit(x);
	}
}
int qr(int x){
	int res=0;
	while(x){
		res+=s[x];
		x-=lowbit(x);
	}
	return res;
}

线段树

一颗包含区间信息的完全二叉树

注意懒标记向下传递时先更新当前区间的信息，再向下更新儿子结点的信息

#define ls p<<1
#define rs p<<1|1
int n;
int m;
const int M = 1e5+5;
int a[M];
struct node{
    int l,r,sum,tag;
};
node tr[M<<2];
void pull(int p){
    tr[p].l=tr[ls].l;tr[p].r=tr[rs].r;
    tr[p].sum=tr[ls].sum+tr[rs].sum;
}
void push(int p){
    tr[ls].sum+=(tr[ls].r-tr[ls].l+1)*tr[p].tag;
    tr[rs].sum+=(tr[rs].r-tr[rs].l+1)*tr[p].tag;
    tr[ls].tag+=tr[p].tag;
    tr[rs].tag+=tr[p].tag;
    tr[p].tag=0;
}
void build(int p,int l,int r){
    if(l==r){
        tr[p].l=l;
        tr[p].r=r;
        tr[p].sum=a[l];
        tr[p].tag=0;
        return ;
    }
    int mid = l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pull(p);
}
void add(int p,int l,int r,int k){
    if(l<=tr[p].l&&tr[p].r<=r){
        tr[p].tag+=k;
        tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
        return;
    }
    push(p);
    int mid = tr[p].l+tr[p].r>>1;
    if(l<=mid)add(ls,l,r,k);
    if(r>mid)add(rs,l,r,k);
    pull(p);
}
int qr(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r){
        return tr[p].sum;
    }
    push(p);
    int mid=tr[p].l+tr[p].r>>1;
    int ans = 0;
    if(l<=mid)ans+=qr(ls,l,r);
    if(r>mid)ans+=qr(rs,l,r);
    pull(p);
    return ans;
}

质数筛

求出$1$~$n$的所有质数

1.试除法

一个数是质数，则该数的因数只有$1$和它本身

vector<int>prime;
for(int i=2;i<=n;i++){
	int ok = 1;
	for(int j=2;j*j<=i;j++){
		if(i%j==0){
			ok=0;break;
		}
	}
	if(ok)prime.push_back(i);
}

时间复杂度$O(n\cdot sqrt(n))$

2.埃氏筛

质数的整数倍是合数

因此只要标记哪些数是合数就可以获得质数

vector<int>isprime(n+1,1);
for(int i=2;i<=n;i++){
	if(isprime[i]){
		for(int j=i*i;j<=n;j+=i){
			isprime[j]=0;
		}
	}
}

时间复杂度$O(nloglogn)$

3.欧拉筛

在埃氏筛的基础上把重复判断是合数的部分去掉

vector<int>prime;
vector<int>isprime(n+1,1);
for(int i=2;i<=n;i++){
	if(isprime[i])prime.push_back(i);
	for(int j=0;j<prime.size()&&i*prime[j]<=n;j++){
		isprime[i*prime[j]]=0;
		if(i%prime[j]==0)break;
	}
}

时间复杂度$O(n)$

排序算法

1.快速排序

确定主元
将小于主元的元素放在左边，大于主元的元素放在右边
递归执行

时间复杂度$O(nlogn)$

最坏情况$O(n^2)$

空间复杂度$O(n)$（系统栈）

代码需要注意数组越界的情况

void quicksort(int l,int r){
    if(l>=r)return;
    int mid =l+r>>1;
    int pivot =a[mid];
    int i=l-1,j=r+1;
    while(i<j){
        do i++; while(a[i]<pivot);
        do j--; while(a[j]>pivot);
        if(i<j)swap(a[i],a[j]);
    }
    quicksort(l,j);
    quicksort(j+1,r);
}

2.归并排序

先递归至一个元素的区间
合并两个有序数组只需要两个指针顺序遍历
合并完子区间就可合并父区间

时间复杂度$O(nlogn)$

空间复杂度$O(n)$(使用辅助数组的情况)

PS：有$O(1)$的写法

int a[M];
int tmp[M];
void merge(int l,int k,int r){
    int i = l, j = k+1;
    int p =l;
    for(;i<=k&&j<=r;p++){
        if(a[i]<a[j]){
            tmp[p]=a[i];
            i++;
        }else{
            tmp[p]=a[j];
            j++;
        }
    }
    for(;i<=k;i++,p++)tmp[p]=a[i];
    for(;j<=r;j++,p++)tmp[p]=a[j];
    for(int t=l;t<=r;t++)a[t]=tmp[t];
}
void mergesort(int l,int r){
    if(l>=r){
        return ;
    }
    int mid = l+r>>1;
    mergesort(l,mid);
    mergesort(mid+1,r);
    merge(l,mid,r);
}

最小生成树

给定一张无向带权图，求其最小生成树（使所有顶点连通且树边权值最小）

1.Prim算法

适用于稠密图

从顶点出发连接另一个顶点以此“生长”最小生成树

实现方式类似于dijkstra

priority_queue<pii,vector<pii>,greater<pii>>pq;
pq.push((pii){0,1});
int ans = 0;
while(pq.size()){
	auto[d,u]=pq.top();
	pq.pop();
	if(vis[u])continue;
	vis[u]=1;
	ans+=d;
	for(auto[v,w]:e[u]){
		if(vis[v])continue;
		pq.push((pii){w,v});
	}
}

2.Kruskal算法

适用于稀疏图

先生成若干连通块，再合并

先将所有边取出从小到大排序
然后利用并查集合并

ST表和倍增算法

1.ST表

ST表通常用于解决区间可重复贡献问题（区间最值）

考虑这样的问题：

给定一个长度为$n$ 的数组，$q$次询问，每次询问要求查询$[l,r]$范围的数组元素最大值

基于ST表进行$O(nlogn)$预处理，$O(1)$查询

令$f[i][j]$表示区间$[i,i+2^j-1]$的最大值

区间$[l,r]$的长度为$r-l+1$,令$k=log_2(r-l+1)$

那么$ans = max(f[l][k],f[r-2^k+1][k])$

预处理过程如下：

int f[M][32];
int a[M];
int Log[M];
int n;
void build(){
    Log[1]=0;
    for(int i=2;i<=n;i++){
        Log[i]=Log[i/2]+1;
    }
    for(int i=1;i<=n;i++)f[i][0]=a[i];
    for(int j=1;j<=31;j++){
        for(int i=1;i<=n&&(i+(1ll<<j-1))<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1ll<<j-1)][j-1]);
        }
    }
}

询问

int qr(int l,int r){
	int k = Log[r-l+1];
	return max(f[l][k],f[r-(1ll<<k)+1][k]);
}

除RMQ以外，ST表还可以处理区间按位与，按位或，区间GCD等问题

但是，ST 表能维护的信息非常有限，不能较好地扩展，并且不支持修改操作

2.倍增

基于二进制的划分思想

考虑这样的问题：

给定一个单调不减序列，多次查询，每次查询给定一个数，求该数在序列中第一次出现的位置。

可以二分答案，但也可以使用倍增

int x;cin>>x;
int p=0,step=1;
while(step){
	if(p+step<=n&&a[p+step]<x){
		p=p+step;
		step<<=1;
	}else{
		step>>=1;
	}
}
if(p<n&&a[p+1]==x){
	cout<<p+1<<' ';
}else{
	cout<<-1<<' ';
}

像这样先翻倍增长步长，再翻倍减少步长是倍增的实现方式之一

快速幂

$O(logn)$求$a^b$同样运用到了倍增

int ksm(int a,int b){
	int ans = 1;
	while(b){
		if(b&1)ans=ans%mod*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans%mod;
}

求LCA

倍增法求一颗树上的两个结点的LCA

预处理$dep$数组和$f[i][0]$（$i$结点的父节点编号）
预处理出整个$f$数组
对于查询结点$u$和$v$，先让两个结点跳到同一深度，再向上判断$LCA$

int n,m,s;
vector<int>e[M];
int f[M][32];
int dep[M];
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int v:e[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
}
int find(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int j=31;j>=0;j--){
        if(dep[f[u][j]]>=dep[v]){
            u=f[u][j];
        }
        if(u==v)return u;
    }
    for(int j=31;j>=0;j--){
        if(f[u][j]!=f[v][j]){
            u=f[u][j];v=f[v][j];
        }
    }
    return f[u][0];
}
void solve(){
    cin>>n>>m>>s;
    for(int i=1;i<=n-1;i++){
        int x,y;cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dep[0]=-1;
    dfs(s,0);
    for(int i=1;i<=31;i++){
        for(int j=1;j<=n;j++){
            f[j][i]=f[f[j][i-1]][i-1];
        }
    }
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        cout<<find(u,v)<<endl;
    }
}

辗转相除法求gcd

求$a$,$b$两个数的最小公约数

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

时间复杂度$O(logn)$

证明：

设$a$,$b$两个数的$gcd$是$c$($b \lt a$)

那么$a=x \cdot b +y$

因为$b%c=0$ 且$a%c=0$，所以$y%c=0$ ($x \cdot b$可以被$c$除成$0$)

因此$a$和$b$的最小公约数等同于$b$和$y$的最小公约数

并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素．

支持两种操作

合并
查询

优化方法：

按秩合并（高度小的树合并到高度大的数或是结点个数少的合并到结点个数大的，均能保证树高不超过$O(logn)$）
路径压缩

平均时间复杂度$O(a(n))$

int p[maxn];
int sz[maxn];
int n;
void init(){
	for(int i=1;i<=n;i++){
		p[i]=i;sz[i]=1;
	}
}
int find(int x){
	if(p[x]!=x){
		p[x]=find(p[x]);
	}return p[x];
}
void merge(int x,int y){
	int px = find(x);
	int py = find(y);
	if(sz[px]>=sz[py]){
		p[py]=px;
		sz[px]+=sz[py];
	}else{
		p[px]=py;
		sz[py]+=sz[px];
	}
}