算法竞赛（高级数据结构）
《算法竞赛》第 4 章 高级数据结构
1. 并查集
并查集的基本操作
DSU用于处理一些不相交结合的合并问题。
初始化：表示 s[i] 是元素 i 所属的并查集。
s[i]=i;
查询：查找元素属于哪个并查集。（路径压缩）
int find_set(int x){
if(x!=s[x]) s[x]=find_set(s[x]);
return s[x];
}
合并：将两个元素并查集合并一起。
void join(int x,int y){
int fx=find_set(x),fy=find_set(y);
if(fx!=fy) s[fx]=s[fy];
}
统计：s[i]=i 的数量就是并查集的数量。
带权并查集
额外定义一个权值数组 d[] ，把节点 i 到父节点的权值记为 d[i] 。
带权路径压缩查询
int find_set(int x){
if(x!=s[x]){
int t=s[x];//记录父节点
s[x]=find_set(s[x]);//路径压缩
d[x]+=d[t];//更新x到祖宗节点的权值
}
return s[x];
}
带权合并：根据具体题意修改
例题
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,s[N],d[N],ans;
int find_set(int x){
if(x!=s[x]){
int t=s[x];//记录父节点
s[x]=find_set(s[x]);//路径压缩
d[x]+=d[t];//更新x到祖宗节点的权值
}
return s[x];
}
void join(int x,int y,int z){//合并
int fx=find_set(x),fy=find_set(y);
if(fx==fy){
if(d[x]-d[y]!=z) ans++;
}else{
s[fx]=fy;
d[fx]=d[y]-d[x]+z;
}
}
void solve(){
for(int i=0;i<N;i++) s[i]=i,d[i]=0;
ans=0;
for(int i=1;i<=m;i++){
int x,y,z;cin>>x>>y>>z;
join(x-1,y,z);
}
cout<<ans<<"\n";
}
int main(){
while(cin>>n>>m) solve();
return 0;
}
int n,m,k,s[N],d[N],ans;
int find_set(int x){
if(x!=s[x]){
int t=s[x];//记录父节点
s[x]=find_set(s[x]);//路径压缩
d[x]=(d[t]+d[x])%3;//更新x到祖宗节点的权值
}
return s[x];
}
void join(int x,int y,int z){//合并
int fx=find_set(x),fy=find_set(y);
if(fx==fy){
if((z-1)!=((d[x]-d[y]+3)%3)) ans++;
}else{
s[fx]=fy;
d[fx]=(d[y]-d[x]+z-1)%3;
}
}
void solve(){
cin>>n>>m;
for(int i=0;i<N;i++) s[i]=i,d[i]=0;
ans=0;
while(m--){
int x,y,z;cin>>z>>x>>y;
if(x>n||y>n||(z==2&&x==y)) ans++;
else join(x,y,z);
}
cout<<ans<<"\n";
}
2.树状数组
树状数组可以 \(O(log_2n)\) 的时间查询和维护前缀和，前缀和可以用来区间修改或者区间查询。
需要借助一个神奇的函数 #define lowbit(x) ((x)&-(x))。
如果当前节点为 x ，父节点为 x+lowbit(x)。
在树状数组中，每个元素 \(tree[]\) 中存储的是区间 \([x-lowbit(x)+1,x]\) 中每个数之和。
单点修改+区间查询
#define lowbit(x) ((x)&-(x))
int tree[N];
void update(int x,int d){//单点修改
while(x<=N){
tree[x]+=d;
x+=lowbit(x);
}
}
int sum(int x){//查询前缀和
int ans=0;
while(x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
void solve(){
for(int i=1,x;i<=10;i++) update(i,x);//初始计算tree[]数组
cout<<"[5,8]="<<sum(8)-sum(4)<<"\n";
}
区间修改+单点查询
#define lowbit(x) ((x)&-(x))
int tree[N],n;
void update(int x,int d){//单点修改
while(x<N){
tree[x]+=d;
x+=lowbit(x);
}
}
int sum(int x){//查询前缀和
int ans=0;
while(x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
void solve(){
memset(tree,0,sizeof(tree));
for(int i=1;i<=n;i++){
int l,r;cin>>l>>r;
update(l,1);
update(r+1,-1);
}
for(int i=1;i<=n;i++){
if(i!=n) cout<<sum(i)<<" ";
else cout<<sum(i)<<"\n";
}
}
区间修改+区间查询
ll tree1[N],tree2[N],n,m;
void update1(ll x,ll d){while(x<N){tree1[x]+=d;x+=lowbit(x);}}
void update2(ll x,ll d){while(x<N){tree2[x]+=d;x+=lowbit(x);}}
ll sum1(ll x){ll ans=0;while(x>0){ans+=tree1[x];x-=lowbit(x);} return ans;}
ll sum2(ll x){ll ans=0;while(x>0){ans+=tree2[x];x-=lowbit(x);} return ans;}
void solve(){
cin>>n>>m;
ll old=0,x;
for(int i=1;i<=n;i++){
cin>>x;
update1(i,x-old);//差分数组初始化
update2(i,(i-1)*(x-old));
old=x;
}
while(m--){
ll q,l,r,d;cin>>q;
if(q==1){
cin>>l>>r>>d;
update1(l,d);
update1(r+1,-d);
update2(l,d*(l-1));
update2(r+1,-d*r);
}else{
cin>>l>>r;
cout<<(r*sum1(r)-sum2(r)-(l-1)*sum1(l-1)+sum2(l-1))<<"\n";
}
}
}
二维区间修改+区间查询
采用CDQ分治更好。
int t1[N][N],t2[N][N],t3[N][N],t4[N][N],n,m;
void update(int x,int y,int d){
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j)){
t1[i][j]+=d;t2[i][j]+=x*d;
t3[i][j]+=y*d;t4[i][j]+=x*y*d;
}
}
int sum(int x,int y){
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
ans+=(x+1)*(y+1)*t1[i][j]-(y+1)*t2[i][j]-(x+1)*t3[i][j]+t4[i][j];
return ans;
}
void solve(){
char ch;cin>>ch;
cin>>n>>m;
while(cin>>ch){
int a,b,c,d,del;cin>>a>>b>>c>>d;
if(ch=='L'){
cin>>del;
update(a,b,del);update(c+1,d+1,del);
update(a,d+1,-del);update(c+1,b,-del);
}
else cout<<sum(c,d)+sum(a-1,b-1)-sum(a-1,d)-sum(c,b-1)<<"\n";
}
}
3.线段树
线段树与树状数组都是用于解决区间问题的数据结构，时间复杂度一样，但是线段树更清晰易懂，代码长度更长，功能更强大。
线段树模板
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll tree[N*4],tag[N*4];
ll ls(int p){return p<<1;}//左儿子,p*2
ll rs(int p){return p<<1|1;}//右儿子,p*2+1
ll a[N];
int n,m;
void push_up(int p){//从下往上传递区间值
tree[p]=tree[ls(p)]+tree[rs(p)];//求区间和
}
void build(int p,int pl,int pr){//建树
tag[p]=0;
if(pl==pr){tree[p]=a[pl];return;}//叶子节点
int mid=(pl+pr)>>1;
build(ls(p),pl,mid);//递归左儿子
build(rs(p),mid+1,pr);//递归右儿子
push_up(p);//往上传递区间值
}
void addtag(int p,int pl,int pr,ll d){//标记tag,更新tree
tag[p]+=d;
tree[p]+=d*(pr-pl+1);
}
void push_down(int p,int pl,int pr){//tag传给子树
if(tag[p]){
int mid=(pl+pr)>>1;
addtag(ls(p),pl,mid,tag[p]);
addtag(rs(p),mid+1,pr,tag[p]);
tag[p]=0;
}
}
void update(int l,int r,int p,int pl,int pr,ll d){//区间修改,[l,r]+d
if(l<=pl&&pr<=r){
addtag(p,pl,pr,d);return ;
}
push_down(p,pl,pr);
ll mid=(pl+pr)>>1;
if(l<=mid) update(l,r,ls(p),pl,mid,d);
if(r>mid) update(l,r,rs(p),mid+1,pr,d);
push_up(p);
}
//调用方式：query(l,r,1,1,n);
ll query(int l,int r,int p,int pl,int pr){//查询区间[l,r]的和
if(l<=pl&&pr<=r) return tree[p];
push_down(p,pl,pr);
ll res=0;
int mid=(pl+pr)>>1;
if(l<=mid) res+=query(l,r,ls(p),pl,mid);
if(r>mid) res+=query(l,r,rs(p),mid+1,pr);
return res;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(m--){
int flag,x,y;cin>>flag>>x>>y;
if(flag==1){
ll k;cin>>k;
update(x,y,1,1,n,k);
}else cout<<query(x,y,1,1,n)<<"\n";
}
}
int main(){
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
solve();
return 0;
}
区间最值
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll sum[N*4],ma[N*4],se[N*4],num[N*4];//区间和,最大值,次大值,最大值个数
ll ls(int p){return p<<1;}//左儿子,p*2
ll rs(int p){return p<<1|1;}//右儿子,p*2+1
//ll a[N];
int n,m;
void push_up(int p){//从下往上传递区间值
sum[p]=sum[ls(p)]+sum[rs(p)];
ma[p]=max(ma[ls(p)],ma[rs(p)]);
if(ma[ls(p)]==ma[rs(p)]){
se[p]=max(se[ls(p)],se[rs(p)]);
num[p]=num[ls(p)]+num[rs(p)];
}else{
se[p]=max(se[ls(p)],se[rs(p)]);
se[p]=max(se[p],min(ma[ls(p)],ma[rs(p)]));
num[p]=ma[ls(p)]>ma[rs(p)]?num[ls(p)]:num[rs(p)];
}
}
void build(int p,int pl,int pr){//建树
if(pl==pr){
cin>>sum[p];
ma[p]=sum[p];se[p]=-1;num[p]=1;
return;
}
int mid=(pl+pr)>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
push_up(p);
}
void addtag(int p,int x){
if(x>=ma[p]) return;
sum[p]-=num[p]*(ma[p]-x);
ma[p]=x;
}
void pushdown(int p){
addtag(ls(p),ma[p]);
addtag(rs(p),ma[p]);
}
void update(int l,int r,int p,int pl,int pr,int x){
if(x>=ma[p]) return;
if(l<=pl&&pr<=r&&se[p]<x){addtag(p,x);return ;}
pushdown(p);
ll mid=(pl+pr)>>1;
if(l<=mid) update(l,r,ls(p),pl,mid,x);
if(r>mid) update(l,r,rs(p),mid+1,pr,x);
push_up(p);
}
//调用方式：query(l,r,1,1,n);
int queryMax(int l,int r,int p,int pl,int pr){//查询区间[l,r]的和
if(l<=pl&&pr<=r) return ma[p];
pushdown(p);
int res=0;
ll mid=(pl+pr)>>1;
if(l<=mid) res=queryMax(l,r,ls(p),pl,mid);
if(r>mid) res=max(res,queryMax(l,r,rs(p),mid+1,pr));
return res;
}
ll querySum(int l,int r,int p,int pl,int pr){
if(l<=pl&&r>=pr) return sum[p];
pushdown(p);
ll res=0;
ll mid=(pl+pr)>>1;
if(l<=mid) res+=querySum(l,r,ls(p),pl,mid);
if(r>mid) res+=querySum(l,r,rs(p),mid+1,pr);
return res;
}
void solve(){
cin>>n>>m;
build(1,1,n);
while(m--){
int q,l,r,x;cin>>q>>l>>r;
if(q==0){cin>>x;update(l,r,1,1,n,x);}
if(q==1){cout<<queryMax(l,r,1,1,n)<<"\n";}
if(q==2){cout<<querySum(l,r,1,1,n)<<"\n";}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--)
solve();
return 0;
}
区间合并
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+10;
ll tree[N*4],pre[N*4],suf[N*4];
ll ls(int p){return p<<1;}//左儿子,p*2
ll rs(int p){return p<<1|1;}//右儿子,p*2+1
int history[N];//记录村庄被毁历史
int n,m;
void push_up(int p,int len){
pre[p]=pre[ls(p)];//父节点接收子节点的前缀信息
suf[p]=suf[rs(p)];
if(pre[ls(p)]==(len-(len>>1))) pre[p]=pre[ls(p)]+pre[rs(p)];//左儿子都是1
if(suf[rs(p)]==(len>>1)) suf[p]=suf[ls(p)]+suf[rs(p)];//右儿子都是1
}
void build(int p,int pl,int pr){//建树
if(pl==pr){
tree[p]=pre[p]=suf[p]=1;
return;
}
int mid=(pl+pr)>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
push_up(p,pr-pl+1);
}
void update(int x,int c,int p,int pl,int pr){
if(pl==pr){tree[p]=suf[p]=pre[p]=c;return ;}//更新叶子节点
int mid=(pl+pr)>>1;
if(x<=mid) update(x,c,ls(p),pl,mid);
else update(x,c,rs(p),mid+1,pr);
push_up(p,pr-pl+1);
}
int query(int x,int p,int pl,int pr){//查询区间[l,r]的和
if(pl==pr) return tree[p];
ll mid=(pl+pr)>>1;
if(x<=mid){
if(x+suf[ls(p)]>mid) return suf[ls(p)]+pre[rs(p)];
else return query(x,ls(p),pl,mid);
}else{
if(mid+pre[rs(p)]>=x) return pre[rs(p)]+suf[ls(p)];
else return query(x,rs(p),mid+1,pr);
}
}
void solve(){
int tot=0,x;
build(1,1,n);
while(m--){
char op;cin>>op;
if(op=='Q'){
cin>>x;
cout<<query(x,1,1,n)<<"\n";
}else if(op=='D'){
cin>>x;history[++tot]=x;
update(x,0,1,1,n);
}else{
x=history[tot--];
update(x,1,1,1,n);
}
}
}
int main(){
while(cin>>n>>m)
solve();
return 0;
}
扫描线
扫描线是线段树的一种经典运用，能解决矩形面积并、矩形周长并、多边形面积等几何问题。
二维线段树（树套树）
4. 可持久化线段树（主席树）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,m,cnt,a[N],b[N],root[N];//a为原数组,b为离散化数组,root为第i颗树根节点编号
struct nod{
int L,R,sum;//L左儿子,R右儿子,sum为节点i的权值
}tree[N<<5];//32*N差不多够用
int build(int pl,int pr){//初始化一颗空树，可以省略
int rt=++cnt;//当前节点编号
tree[rt].sum=0;
int mid=(pl+pr)>>1;
if(pl<pr){
tree[rt].L=build(pl,mid);
tree[rt].R=build(mid+1,pr);
}
return rt;//返回当前节点的编号
}
int update(int pre,int pl,int pr,int x){//建立新线段树
int rt=++cnt;;
tree[rt].L=tree[pre].L;
tree[rt].R=tree[pre].R;
tree[rt].sum=tree[pre].sum+1;//新加的数
int mid=(pl+pr)>>1;
if(pl<pr){//从根节点向下建log2 n个节点
if(x<=mid)//x出现在左子树，修改左子树
tree[rt].L=update(tree[pre].L,pl,mid,x);
else //x出现在右子树，修改右子树
tree[rt].R=update(tree[pre].R,mid+1,pr,x);
}
return rt;
}
int query(int u,int v,int pl,int pr,int k){//查询区间(u,v]中的第k小数
if(pl==pr) return pl;//到达叶子节点，找到第k小数
int x=tree[tree[v].L].sum-tree[tree[u].L].sum;//线段树相减
int mid=(pl+pr)>>1;
if(x>=k)//左儿子数字>=k,说明第k小数在左子树
return query(tree[u].L,tree[v].L,pl,mid,k);
else return query(tree[u].R,tree[v].R,mid+1,pr,k-x);
}
void solve(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];b[i]=a[i];
}
sort(b+1,b+n+1);//对b排序，离散化
int size=unique(b+1,b+n+1)-b-1;//size等于b中不重复元素个数
//root[0]=build(1,size);
for(int i=1;i<=n;i++){
int x=lower_bound(b+1,b+size+1,a[i])-b;
root[i]=update(root[i-1],1,size,x);
}
while(m--){
int x,y,k;cin>>x>>y>>k;
int t=query(root[x-1],root[y],1,size,k);
cout<<b[t]<<"\n";
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
solve();
return 0;
}
5. 分块与莫队算法
分块就是将数列分成很多块，对涉及的块做整体性的维护操作。类似与一个多分线段树。
代码比树状数组和线段树简单，效率比暴力高的，时间复杂度 \(O(m \sqrt{n})\)。
- 块的大小（块的长度），
block=sqrt(n) - 块的数量，
t - 块的左右边界，
st[]和ed[] - 每个元素所属块，
pos[i]=(i-1)/block+1
分块定义，初始化
int block=sqrt(n);
int t=n/block;
if(n%block) t++;
for(int i=1;i<=t;i++){
st[i]=(i-1)*block+1;
ed[i]=i*block;
}
ed[t]=n;
for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;
ll n,m,a[N],b[N],add[N];
ll t,st[N],ed[N],pos[N];
void change(int L,int R,ll d){//对[L,R]区间操作
int p=pos[L],q=pos[R];//左右区间端点对应块
if(p==q){//同一块，碎片
for(int i=L;i<=R;i++) b[i]+=d;//暴力操作区间
for(int i=st[p];i<=ed[p];i++) a[i]=b[i];//维护a数组
sort(a+st[p],a+ed[p]+1);
}else{
for(int i=p+1;i<=q-1;i++) add[i]+=d;//整块操作
for(int i=L;i<=ed[p];i++) b[i]+=d;//左碎片操作
for(int i=st[p];i<=ed[p];i++) a[i]=b[i];
sort(a+st[p],a+ed[p]+1);
for(int i=st[q];i<=R;i++) b[i]+=d;//右碎片操作
for(int i=st[q];i<=ed[q];i++) a[i]=b[i];
sort(a+st[q],a+ed[q]+1);
}
}
ll query(int L,int R,ll c){//在[L,R]中查询
int p=pos[L],q=pos[R];//区间端点对应块
ll ans=0;
if(p==q){
for(int i=L;i<=R;i++)//暴力操作碎片
if(b[i]+add[p]>=c) ans++;
}else{
for(int i=p+1;i<=q-1;i++){//整块操作
int x=lower_bound(a+st[i],a+ed[i]+1,c-add[i])-a;
ans+=(ed[i]-x+1);
}
for(int i=L;i<=ed[p];i++)//左碎片暴力查询
if(b[i]+add[p]>=c) ans++;
for(int i=st[q];i<=R;i++)//右碎片暴力查询
if(b[i]+add[q]>=c) ans++;
}
return ans;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i];};//复制数组
int block=sqrt(n);//块大小
t=(n+block-1)/block;//块数量
for(int i=1;i<=t;i++){
st[i]=(i-1)*block+1;//块的左端点
ed[i]=i*block;//块的右端点
}
ed[t]=n;//防止最后一块越界
for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;//元素对应块
for(int i=1;i<=n;i++) sort(a+st[i],a+ed[i]+1);//块内排序
while(m--){
char c;cin>>c;
ll l,r,w;cin>>l>>r>>w;
if(c=='M') change(l,r,w);//区间操作
else cout<<query(l,r,w)<<"\n";//区间查询
}
}
基础莫队算法
莫队算法=离线+暴力+分块
基础莫队算法用于不修改只查询的一类区间问题，复杂度为 \(O(n\sqrt{n})\) 。
一次性存储所有询问，按照查询区间 左端点所在块序号排序，块相同再按 右端点排序。
ll n,m,a[N],tmp;
struct nod{//记录查询,用来排序
int L,R,k;
}q[N];
ll t,sum[N],ans[N],pos[N];
bool cmp(nod a,nod b){//莫队排序
if(pos[a.L]!=pos[b.L]) return pos[a.L]<pos[b.L];
if(pos[a.L]&1) return a.R>b.R;//奇偶性优化
return a.R<b.R;
}
void add(int x){sum[a[x]]++;if(sum[a[x]]==1) tmp++;}
void del(int x){sum[a[x]]--;if(sum[a[x]]==0) tmp--;}
void solve(){
cin>>n;
int block=sqrt(n);
for(int i=1;i<=n;i++){
cin>>a[i];pos[i]=(i-1)/block+1;//记录对应块
}
cin>>m;
for(int i=1;i<=m;i++){//记录查询
cin>>q[i].L>>q[i].R;q[i].k=i;
}
sort(q+1,q+m+1,cmp);//查询排序
int L=1,R=0;
for(int i=1;i<=m;i++){//查询处理
while(L<q[i].L) del(L++);
while(R>q[i].R) del(R--);
while(L>q[i].L) add(--L);
while(R<q[i].R) add(++R);
ans[q[i].k]=tmp;
}
for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
}
带修改的莫队算法
如果只是简单的单点修改，也能使用莫队算法，但是复杂度为 \(O(mn^{2/3})\)
树上莫队
SP10707 COT2 - Count on a tree II - 洛谷
将树转换成欧拉序变为一维数组。
6. 块状链表
块状链表=分块+链表
7. 简单树上问题
判断一个图是否为树：
- 找根节点：只有出边没有入边的点，只有一个，无向图任何点都可以
- 判断环：从根DFS遍历图，每个节点只被访问一次
- 检查联通性：判断环后，检查所有点是否都访问到
- 时间复杂度为 \((n+m)\)
树的重心
删除重心这个节点后，得到的最大子树的节点数最少。
