从lxl开始的数据结构

树状数组

#include<bits/stdc++.h>
#define int long long
#define lowbit(x)(x&-x)
using namespace std;
const int N=1e7;
int n,m,a[N],c[N];
void modify(int x,int y){//将x位置的值加y 
	while(x<=n){
		c[x]+=y;
		x+=lowbit(x);
	}
} 
int find(int x){//求序列前x个位置的和
	int ans=0; 
	while(x!=0){
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}
signed main(){
cin>>n>>m;
	for(int i=1;i<=n;i++){
	cin>>a[i];
	modify(i,a[i]);
	}
	for(int i=1;i<=m;i++){
		int opt,x,y;
		cin>>opt>>x>>y;
		if(opt==1){
			modify(x,y);
		}
		else cout<<find(y)-find(x-1)<<endl;
	}
	return 0;
}

并查集

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7;
int n,m,a[N];
int find(int x){
	if(a[x]==x) return x;
	a[x]=find(a[x]);
	return a[x];
} 
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) a[i]=i;
	while(m--){
		int z,b,c;
		cin>>z>>b>>c;
		int x=find(b),y=find(c);
		if(z==1){
			if(x!=y) a[x]=y; 
		}
		if(z==2){
			if(y==x) cout<<"Y"<<endl;
			else cout<<"N"<<endl;
		}
	}
	return 0;
}

路径压缩

线段树，单点操作，可用于大规模区间相同标记不同值

const int N=1e6;
int n,m,a[N],t[4*N];
void build(int cur,int l,int r)//当前建立cur节点，在序列上区间是[l,r]
{
	
	if(l==r){
		t[cur]=a[l];
	}
	else{
		int mid=(l+r)>>1;
		build(2*cur,l,mid);
		build(2*cur+1,mid+1,r);
		t[cur]=t[cur*2]+t[cur*2+1];
	}
}
void modify(int cur,int l,int r,int x,int y)	//当前访问到cur，cur在序列上属于[l,r]区间，修改是将x位置加上y
{
	if(l==r){
		t[cur]+=y; 
	} 
	else{
		int mid=(l+r)>>1;
		if(x>mid)
		{
			modify(2*cur+1,mid+1,r,x,y);
		}
		else
		{
			modify(2*cur,l,mid,x,y);
		}
		t[cur]=t[2*cur]+t[2*cur+1];
	}
}
int find(int cur,int l,int r,int x,int y){
	//当前访问到cur，cur在序列中是[l,r]区间，询问求的是[x,y]区间
	if(l==x&&r==y){
		return t[cur];
	} 
	int mid=(l+r)>>1;
	if(y<=mid){
		return find(2*cur,l,mid,x,y);
	}
	else if(x>mid){
		return find(2*cur+1,mid+1,r,x,y);
	}
	else{
		int a=find(2*cur,l,mid,x,y);
		int b=find(2*cur+1,mid+1,r,x,y);
		return a+b;
	}
}

线段树 区间

void print(){
	cout<<"sum:";
	for(int i=1;i<=2*n-1;i++) cout<<t[i]<<" ";
	cout<<endl<<"add:";
	for(int i=1;i<=2*n-1;i++) cout<<add[i]<<" ";
	cout<<endl;
}
void Add(int cur,int l,int r,int v){
	//给区间 [l,r]所有数加v
	add[cur]+=v;
	t[cur]+=(r-l+1)*v;
	return; 
}
void pushdown(int cur,int l,int r){
	//标记下传
	if(add[cur]==0) return;
	int mid=l+r>>1;
	Add(cur*2,l,mid,add[cur]),Add(cur*2+1,mid+1,r,add[cur]);
	add[cur]=0;//请空标记 
}
void modify(int cur,int l,int r,int x,int y,int v){
	//给区间[x,y]所有数加v
	if(l>=x && r<=y) {
		Add(cur,l,r,v);
		return;
	} 
	int mid=l+r>>1;
	pushdown(cur,l,r);
	if(x<=mid) modify(2*cur,l,mid,x,y,v);
	if(mid<y) modify(2*cur+1,mid+1,r,x,y,v);
	t[cur]=t[2*cur]+t[2*cur+1];
}
int query(int cur,int l,int r,int x,int y){
	if(l>=x&&r<=y) return t[cur];
	int mid=l+r>>1,res=0;
	pushdown(cur,l,r);
	if(x<=mid) res+=query(cur*2,l,mid,x,y);
	if(y>mid) res+=(cur*2+1,mid+1,r,x,y);
	return res;
}

平衡树 Treap

const int INF=1e9;
int pool,rt;
struct node{
	int l,r,key,priority,cnt,size;
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define v(x) t[x].key
	#define p(x) t[x].priority
	#define c(x) t[x].cnt
	#define s(x) t[x].size
}t[N];
inline void update(const int &k){
	s(k)=s(l(k))+s(r(k))+c(k);
	return;
}
inline void Zig(int &k){//右旋 
	int y=l(k);
	l(k)=r(y);
	r(y)=k;
	s(y)=s(k);
	update(k);
	k=y; 
}
inline void Zag(int &k){//左旋 
	int y=r(k);
	r(k)=l(y);
	l(y)=k;
	s(y)=s(k);
	update(k);
	k=y;
}
inline void insert(int &k,const int &key){
	if(!k){
		k=++pool,v(k)=key,p(k)=rand();
		c(k)=s(k)=1;l(k)=r(k)=0;
		return;
	}
	else s(k)++;
	if(v(k)==key) c(k)++;
	else if(key<v(k)){
		insert(l(k),key);
		if(p(l(k))<p(k)) Zig(k);
	}
	else{
		insert(r(k),key);
		if(p(r(k))<p(k)) Zag(k); 
	}
	return;
}
inline void Delete(int &k,const int &key){
	if(v(k)==key){
		if(c(k)>1) c(k)--,s(k)--;	
		else if(!l(k)||!r(k)) k=l(k)+r(k);
			else if(p(l(k))<p(r(k))) Zig(k),Delete(k,key);
				else Zag(k),Delete(k,key);
		return; 
	}
	s(k)--;
	if(key<v(k)) Delete(l(k),key);
	else Delete(r(k),key);
	return;
}
inline int querypre(const int &key){
	int x=rt,res=-INF;
	while(x){
		if(v(x)<=key) res=v(x),x=r(x);
		else x=l(x);
	}
	return res;
}
inline int querysuf(const int &key){
	int x=rt,res=INF;
	while(x){
		if(v(x)>=key) res=v(x),x=l(x);
		else x=r(x);
	}
	return res;
}
inline int querykth(int k){
	int x=rt;
	while(x){
		if(s(l(x))<k&&s(l(x))+c(x)>=k) return v(x);
		if(s(l(x))>=k) x=l(x);
		else k-=s(l(x))+c(x),x=r(x);
	}
	return 0;
}
inline int rank(const int &key){
	int x=rt,res=0;
	while(x){
		if(key==v(x)) return res+s(l(x))+1;
		if(key<v(x)) x=l(x);
		else res+=s(l(x))+c(x),x=r(x);
	}
	return res;
}