专栏文章

学习笔记-数据结构

YYGBC_
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzrfas
此快照首次捕获于
2025/12/01 18:13
3 个月前
此快照最后确认于
2025/12/01 18:13
3 个月前
查看原文

数据结构

真的非常非常重要。计算机科学等于算法（Algorithm）加数据结构（Data Structure）。

基础数据结构

1. 栈

蒟蒻学的第一个数据结构。
特点，先进先出，只有栈顶可以访问。
下面给出模板题 B3614 的代码。
STL 实现（优点：好写，维护成本低。缺点：常数大，容易报错）：
CPP
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;

int T;

void solve()
{
	stack<ull> st;
	int N; cin>>N;
	while(N--){
		string s; cin>>s;
		if(s=="push"){
			ull x; cin>>x;
			st.push(x);
		}
		if(s=="pop"){
			if(st.empty()) cout<<"Empty\n";
			else st.pop();
		}
		if(s=="query"){
			if(st.empty()) cout<<"Anguei!\n";
			else cout<<st.top()<<'\n';
		}
		if(s=="size"){
			cout<<st.size()<<'\n';
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--) solve();
}
手写实现（优点：常数小，自定义程度高，缺点：难以维护）：
CPP
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;

class Stack{
	private:
		ull st[1000005], top;
	public:
		void init(){
			top=0;
		}
		inline void push(ull x){
			st[++top]=x;
		}
		inline void pop(){
			if(top) top--;
			else cout<<"Empty\n";
		}
		inline ull query(){
			if(top) return st[top];
			cout<<"Anguei!\n";
			return -1;
		}
		inline ull size(){
			return top;
		}
        inline bool empty(){
            return top==0;
        }
}S;

int T;

void solve()
{
	S.init();
	int N; cin>>N;
	while(N--){
		string s; cin>>s;
		if(s=="push"){
			ull x; cin>>x;
			S.push(x);
		}
		if(s=="pop"){
			S.pop();
		}
		if(s=="query"){
			ull x=S.query();
			if(~x) cout<<x<<'\n';
		}
		if(s=="size"){
			cout<<S.size()<<'\n';
		} 
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--) solve();
}

2. 队列

先进后出表，和栈一样运用广泛。
STL 实现：
CPP
#include<bits/stdc++.h>
using namespace std;

int N;
queue<int> q;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>N;
	while(N--){
		int op; cin>>op;
		if(op==1){
			int x; cin>>x;
			q.push(x);
		}
		if(op==2){
			if(q.empty()) cout<<"ERR_CANNOT_POP\n";
			else q.pop();
		}
		if(op==3){
			if(q.empty()) cout<<"ERR_CANNOT_QUERY\n";
			else cout<<q.front()<<'\n';
		}
		if(op==4){
			cout<<q.size()<<'\n';
		}
	}
}
手写实现：
CPP
#include<bits/stdc++.h>
using namespace std;

class Queue{
	private:
		int q[10005],l=0,r=-1;
	public:
		void init(){
			l=0,r=-1;
		}
		inline void push(int x){
			q[++r]=x;
		}
		inline void pop(){
			if(l>r) cout<<"ERR_CANNOT_POP\n";
			else l++;
		}
		inline int query(){
			if(l>r){
				cout<<"ERR_CANNOT_QUERY\n";
				return -1;
			} 
			return q[l];
		}
		inline int size(){
			return r-l+1;
		}
		inline bool empty(){
			return l>r;
		}
}Q;

int N;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>N;
	while(N--){
		int op; cin>>op;
		if(op==1){
			int x; cin>>x;
			Q.push(x);
		}
		if(op==2){
			Q.pop();
		} 
		if(op==3){
			int x=Q.query();
			if(~x) cout<<x<<'\n';
		}
		if(op==4){
			cout<<Q.size()<<'\n';
		}
	}
}

3. 链表

通过记录每一个节点的前驱和后继实现 O(1)O(1) 插入，O(n)O(n)遍历。
码略。

4. 二叉堆（优先队列）

通过对二叉树节点的上浮和下沉实现每次顶端都是最值。
插入，删除都是 O(log⁡n)O(\log n)，查询堆顶是 O(1)O(1) 的。
一般用优先队列（std::priority_queue）实现，代码如下：
CPP
#include<bits/stdc++.h>
using namespace std;

int N;
priority_queue<int,vector<int>,greater<int>> q;

int main()
{
	cin>>N;
	while(N--){
		int op; cin>>op;
		if(op==1){
			int x; cin>>x;
			q.push(x);
		} 
		if(op==2) cout<<q.top()<<'\n';
		if(op==3) q.pop();
	}

}

高级数据结构

1. 并查集

1.1. 并查集

用于解决集合合并，查询两元素是否在一个集合。
模板代码：
CPP
#include<bits/stdc++.h>
using namespace std;

int N,M;

namespace DSU
{
	
int fa[200005];

void init(){
	for(int i=1;i<=N;i++) fa[i]=i;
}
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	int fx=find(x), fy=find(y);
	if(fx==fy) return ;
	fa[fx]=fy;
}

}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>N>>M;
	DSU::init();
	while(M--){
		int z,x,y; cin>>z>>x>>y;
		if(z==1) DSU::merge(x,y);
		if(z==2){
			int fx=DSU::find(x), fy=DSU::find(y);
			if(fx==fy) cout<<"Y\n";
			else cout<<"N\n"; 
		} 
	}
}

1.2. 扩展域并查集

通过对元素拓展多个域进行合并，解决朋友，敌人，捕食等多种复杂关系。
P1892 代码：
CPP
#include<bits/stdc++.h>
using namespace std;

int N,M,P;
int fa[2005];

int find(int x){fu
	if(x==fa[x]) return x;
	else return fa[x]=find(fa[x]);
}

int main()
{
	cin>>N>>M;
	for(int i=1;i<=2*N;i++) fa[i]=i;
	for(int i=1;i<=M;i++){
		char ch;
		int x,y;
		cin>>ch>>x>>y;
		if(ch=='F') fa[find(y)]=find(x);
		else{
			fa[find(N+x)]=find(y);
			fa[find(N+y)]=find(x);
		}
	}
	for(int i=1;i<=N;i++){
		if(fa[i]==i) P++;
	}
	cout<<P;
	return 0;
}

1.3. 带权并查集

记录自己与父亲节点的边权，以处理更复杂的关系。
扩展域并查集与带权并查集的适用范围差不多。
P2024 代码：
CPP
#include<bits/stdc++.h>
using namespace std;

int N,k;
int res;
int fa[100005],d[100005];

int find(int x){
	if(fa[x]!=x){
		int f=fa[x];
		fa[x]=find(fa[x]);
		d[x]=(d[x]+d[f])%3;
	}
	return fa[x];
}

void merge(int x,int y,int w){
	int fx=find(x), fy=find(y);
	if(fx==fy){
		if(((d[x]-d[y]+3)%3)!=w-1) res++;
	}
	else{
		fa[fx]=fy;
		d[fx]=(d[y]-d[x]+w+2)%3;
	}
}

int main()
{
	cin>>N>>k;
	for(int i=1;i<=N;i++) fa[i]=i;
	
	while(k--){
		int w,x,y; cin>>w>>x>>y;
		if(x>N||y>N||x==y&&w==2) res++;
		else merge(x,y,w);
	}
	
	cout<<res;
}

2. 树状数组

2.1. 单点修改&区间查询

模板题 P3374 代码：
CPP
#include<bits/stdc++.h>
using namespace std;

int N,M;
int a[500005];

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

class Tree{
	private:
		int t[500005];
		void update(int p,int x){
			while(p<=N){
				t[p]+=x;
				p+=lowbit(p);
			}
		}
		int get_sum(int p){
			int res=0;
			while(p){
				res+=t[p];
				p-=lowbit(p);
			}
			return res;
		}
	public:
		void modify(int p,int x){
			update(p,x);
		}
		int query(int l,int r){
			return get_sum(r)-get_sum(l-1);
		}
}T;	


int main()
{
	cin>>N>>M;
	for(int i=1;i<=N;i++){
		cin>>a[i];
		T.modify(i,a[i]);
	}
	while(M--){
		int op,x,y; cin>>op>>x>>y;
		if(op==1) T.modify(x,y);
		if(op==2) cout<<T.query(x,y)<<'\n';
	}
}

2.2. 区间修改&单点查询

维护差分数组即可，略。

2.3 区间修改&区间查询

维护两个差分数组。像这样的操作通常用线段树维护，代码略。

3 线段树

直接给出超级线段树代码：
CPP
#include<bits/stdc++.h>
using namespace std;

int N;
int a[100005];

namespace SGT{

struct Node{
	int l,r;
	int dat;
	int maxn,minn;
	int add,mul;
	int ass;
};

class Tree{
	
#define int long long
#define ls i<<1
#define rs i<<1|1

	private:
		Node t[400005];
		void push_up(int i){
			t[i].dat=t[ls].dat+t[rs].dat;
			t[i].maxn=max(t[ls].maxn,t[rs].maxn);
			t[i].minn=max(t[ls].minn,t[rs].minn);
		}
		void tag_add(int i,int x){
			t[i].add+=x;
			t[i].dat+=(t[i].r-t[i].l+1)*x;
			t[i].maxn+=x, t[i].minn+=x;
		}
		void tag_mul(int i,int x){
			t[i].mul*=x, t[i].add*=x;
			t[i].dat*=x, t[i].maxn*=x, t[i].minn*=x;
		}
		void tag_ass(int i,int x){
			t[i].add=0, t[i].mul=1;
			t[i].ass=x;
			t[i].dat=(t[i].r-t[i].l+1)*x;
			t[i].maxn=t[i].minn=x;
		}
		void push_down(int i){
			if(t[i].ass!=-1){
				tag_ass(ls,t[i].ass);
				tag_ass(rs,t[i].ass); 
				t[i].ass=-1;
			}
			if(t[i].mul){
				tag_mul(ls,t[i].mul);
				tag_mul(rs,t[i].mul); 
				t[i].mul=1;
			}
			if(t[i].add){
				tag_add(ls,t[i].add);
				tag_add(rs,t[i].add); 
				t[i].add=0;
			}
		}
		void build(int i,int L,int R,int a[]){
			t[i].l=t[i].r=0, t[i].add=0, t[i].mul=1;
			if(L<=t[i].l&&t[i].r<=R){
				t[i].dat=t[i].maxn=t[i].minn=a[L];
				return ;
			}
			int Mid=L+R>>1;
			build(ls,L,Mid,a);
			build(rs,Mid+1,R,a);
			push_up(i);
		}
		void update_add(int i,int L,int R,int x){
			if(L<=t[i].l&&t[i].r<=R){
				tag_add(i,x);
				return ;
			}
			int mid=t[i].l+t[i].r>>1;
			push_down(i);
			if(L<=mid) update_add(ls,L,R,x);
			if(mid<R) update_add(rs,L,R,x);
			push_up(i);
		}
		void update_mul(int i,int L,int R,int x){
			if(L<=t[i].l&&t[i].r<=R){
				tag_mul(i,x);
				return ;
			}
			int mid=t[i].l+t[i].r>>1;
			push_down(i);
			if(L<=mid) update_mul(ls,L,R,x);
			if(mid<R) update_mul(rs,L,R,x);
			push_up(i);
		}
		void update_ass(int i,int L,int R,int x){
			if(L<=t[i].l&&t[i].r<=R){
				tag_ass(i,x);
				return ;
			}
			int mid=t[i].l+t[i].r>>1;
			push_down(i);
			if(L<=mid) update_ass(ls,L,R,x);
			if(mid<R) update_ass(rs,L,R,x);
			push_up(i);
		}
		int get_sum(int i,int L,int R){
			if(L<=t[i].l&&t[i].r<=R) return t[i].dat;
			int mid=t[i].l+t[i].r>>1, res=0;
			push_down(i);
			if(L<=mid) res+=get_sum(ls,L,R);
			if(mid<R) res+=get_sum(rs,L,R);
		}
		int get_max(int i,int L,int R){
			if(L<=t[i].l&&t[i].r<=R) return t[i].maxn;
			int mid=t[i].l+t[i].r>>1, res=0;
			push_down(i);
			if(L<=mid) res=max(res,get_max(ls,L,R));
			if(mid<R) res=max(res,get_max(rs,L,R));
		}
		int get_min(int i,int L,int R){
			if(L<=t[i].l&&t[i].r<=R) return t[i].minn;
			int mid=t[i].l+t[i].r>>1, res=1e18;
			push_down(i);
			if(L<=mid) res=min(res,get_min(ls,L,R));
			if(mid<R) res=min(res,get_min(rs,L,R));
		}
		
	public:
		void init(int a[]){
			build(1,1,N,a);
		}
		void modify(int op,int L,int R,int x){
			if(op==1) update_add(1,L,R,x);
			if(op==2) update_mul(1,L,R,x);
			if(op==3) update_ass(1,L,R,x);
		}
		int query_sum(int L,int R){
			return get_sum(1,L,R);
		}
		int query_max(int L,int R){
			return get_max(1,L,R);
		}
		int query_min(int L,int R){
			return get_min(1,L,R);
		}
		
#undef int
#undef ls
#undef rs

};

}

 

int main()
{
	
}

4. 分块

4.1 基础分块

数列分块入门 1 代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;

int N;
int a[300005];
int tag[1005];
int B[300005],L[1005],R[1005];

void build(){
	int Bl=sqrt(N);
	int l=1,r=Bl,cnt=1;
	while(true){
		bool flag=0;
		if(r>N) r=N, flag=1;
		L[cnt]=l, R[cnt]=r;
		for(int i=l;i<=r;i++) B[i]=cnt;
		if(flag) break;
		l+=Bl, r+=Bl, cnt++;
	}
}

void modify(int l,int r,int c){
	int lb=B[l], rb=B[r];
	if(lb==rb){
		for(int i=l;i<=r;i++) a[i]+=c;
		return ;
	}
	for(int i=l;i<=R[lb];i++) a[i]+=c;
	for(int i=lb+1;i<=rb-1;i++) tag[i]+=c;
	for(int i=L[rb];i<=r;i++) a[i]+=c;
}

int query(int p){
	int b=B[p];
	return a[p]+tag[b];
}


signed main()
{
	cin>>N;
	build();
	for(int i=1;i<=N;i++) cin>>a[i];
	for(int i=1,op,l,r,c;i<=N;i++){
		cin>>op>>l>>r>>c;
		if(op==0) modify(l,r,c);
		else cout<<query(r)<<'\n';
	}
}
数列分块入门 2 代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;

int N,q,Bl;
int B[1000005],L[30005],R[30005],tag[30005];
int a[1000005],b[1000005];

void build(){
	Bl=sqrt(N);
	int l=1-Bl,r=0,cnt=0;
	while(true){
		l+=Bl, r+=Bl, cnt++;
		if(r>N) r=N;
		L[cnt]=l, R[cnt]=r;
		for(int i=l;i<=r;i++) B[i]=cnt;
		if(r==N) break;
	}
	for(int i=1;i<=N;i++) cin>>a[i];
	for(int i=1;i<=B[N];i++){
		for(int j=L[i];j<=R[i];j++) b[j]=a[j];
		sort(b+L[i],b+R[i]+1);
	}
	
}

void modify(int l,int r,int c){
	int lb=B[l],rb=B[r];
	if(lb==rb){
		for(int i=l;i<=r;i++) a[i]+=c;
		for(int i=L[lb];i<=R[lb];i++) b[i]=a[i];
		sort(b+L[lb],b+R[lb]+1);
		return ;
	}
	
	for(int i=l;i<=R[lb];i++) a[i]+=c;
	for(int i=L[lb];i<=R[lb];i++) b[i]=a[i];
	sort(b+L[lb],b+R[lb]+1);
	
	for(int i=lb+1;i<=rb-1;i++) tag[i]+=c;
	
	for(int i=L[rb];i<=r;i++) a[i]+=c;
	for(int i=L[rb];i<=R[rb];i++) b[i]=a[i];
	sort(b+L[rb],b+R[rb]+1);
}

int query(int l,int r,int c){
	int lb=B[l],rb=B[r],res=0;
	if(lb==rb){
		for(int i=l;i<=r;i++)
			if(a[i]+tag[lb]<c) res++;
		return res;
	}
	
	for(int i=l;i<=R[lb];i++)
		if(a[i]+tag[lb]<c) res++;
	for(int i=L[rb];i<=r;i++)
		if(a[i]+tag[rb]<c) res++;
	
	for(int i=lb+1;i<=rb-1;i++){
		int p=c-tag[i];
		res+=lower_bound(b+L[i],b+R[i]+1,p)-(b+L[i]);
	}
	
	return res;
	
}

signed main()
{
	cin>>N;
	build();
	for(int i=1;i<=N;i++){
		int opt,l,r,c;
		cin>>opt>>l>>r>>c;
		if(!opt) modify(l,r,c);
		else cout<<query(l,r,c*c)<<'\n';
	}
}

4.2 莫队

模板题 P2709 代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;

int N,M,k,B; 
int a[50005],b[50005];
int bel[50005],res[50005];

struct Q{
	int l,r;
	int id,ans;
}q[50005];

vector<Q> G[505];

bool cmp1(Q a,Q b){ return a.r<b.r; }
bool cmp2(Q a,Q b){ return a.id<b.id; }

signed main()
{
	cin>>N>>M>>k; B=sqrt(N);
	for(int i=1;i<=N;i++){
		cin>>a[i];
		bel[i]=(i+B-1)/B;
	}
	for(int i=1;i<=M;i++){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
		G[bel[q[i].l]].push_back(q[i]);
	}
	for(int i=1;i<=2*B;i++)
		sort(G[i].begin(),G[i].end(),cmp1);
	for(int i=1;i<=2*B;i++){
		if(G[i].empty()) continue;
		memset(b,0,sizeof b);
		int lp=G[i][0].l,rp=G[i][0].r,ans=0;
		for(int j=lp;j<=rp;j++){
			ans+=2*b[a[j]]+1;
			b[a[j]]++;
		}
		res[G[i][0].id]=ans;
		for(int j=1;j<G[i].size();j++){
			while(rp<G[i][j].r){
				ans+=2*b[a[++rp]]+1;
				b[a[rp]]++;
			}
			while(lp<G[i][j].l){
				ans-=2*b[a[lp]]-1;
				b[a[lp]]--; lp++;
			}
			while(lp>G[i][j].l){
				ans+=2*b[a[--lp]]+1;
				b[a[lp]]++;
			}
			res[G[i][j].id]=ans;
		}
	} 
	for(int i=1;i<=M;i++) cout<<res[i]<<'\n';
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...