数据结构6——平衡树
rogeryi
·
2024-09-30 22:45:47
·
个人记录
01-Trie
适用范围：
1.（整数）普通平衡树
2.位运算最值/操作
时间复杂度：O(log(V))
核心思想：
1.将整数看作N位二进制数，从高位向低位插入Trie
2.由于Trie的前缀性质，任意左子树节点小于右子树节点
3.在Trie中查找时，可以二分递归+整体计算
插入/删除：按照01-Trie进行操作
排名-权值：在01-Trie中递归，直到叶节点/空节点
前驱/后继：查找对应排名，按照排名查询权值
负数操作：加入偏移量，权值整体修改/*
cnt：01-Trie节点总数
Update：带权插入整数
get_rank：查找排名（小于x的数的个数）
get_val：查找权值
Insert：插入
Erase：删除
get_pre：查找前驱
get_suf：查找后继
*/
struct Trie{int p[2],cnt;};
struct Trie A[maxN*20];
int cnt;
void Update(int x,int val){
int p=0;
for(int i=28;i>=0;i--){
int k=((x+del)>>i)&1;
if(!A[p].p[k]) A[p].p[k]=++cnt;
p=A[p].p[k];A[p].cnt+=val;
}
}
int get_rank(int x){
int p=0,ans=0;
for(int i=28;i>=0;i--){
int k=((x+del)>>i)&1;
if(k) ans+=A[A[p].p[0]].cnt;
p=A[p].p[k];
if(!p) return ans;
}
return ans;
}
int get_val(int x){
int p=0,ans=0;
for(int i=28;i>=0;i--){
if(A[A[p].p[0]].cnt<x){x-=A[A[p].p[0]].cnt;p=A[p].p[1];ans|=(1<<i);}
else p=A[p].p[0];
}
return ans-del;
}
void Insert(int x){Update(x,1);}
void Erase(int x){Update(x,-1);}
int get_pre(int x){return get_val(get_rank(x));}
int get_suf(int x){return get_val(get_rank(x+1)+1);}笛卡尔树
适用范围：多区间最值问题
基本性质：
1.节点值满足二叉搜索树性质
2.权值满足堆性质
时间复杂度（节点值有序）：O(n)
核心思想：
1.对于任意节点，记左边第一个权值更小的节点为L，右边第一个权值更小的节点为R
2.对于任意节点x，左子节点为(L,x)中权值最小点，右子节点为(x,R)中权值最小点
3.使用单调栈维护子节点struct Treap{
int lc,rc;
int val;
};
struct Treap Tp[maxN];
struct node{int id,val;};
void build(){
deque<node> q;
for(int i=1;i<=n;i++){
while(!q.empty()&&q.back().val>Tp[i].val){Tp[i].lc=q.back().id;q.pop_back();}
if(!q.empty()) Tp[q.back().id].rc=i;
q.push_back(node{i,Tp[i].val});
}
}无旋Treap
适用范围：
1.可以快速合并的问题
2.运算满足结合律的问题
3.序列结构发生改变的问题
4.动态排序+数据维护问题
5.（有序）集合类问题
6.与前驱/后继相关的问题
7.动态插入/删除问题
8.（动态）相邻判定问题
9.（大跨度/广义顺序）数据维护
时间复杂度：
1.建立平衡树：O(n)
2.修改：O(log(n))
3.查询：O(log(n))
核心思想：
1.使用笛卡尔树，通过随机赋权保证平衡
2.通过分裂、合并维护平衡
3.使用分裂提取单点/区间，操作后使用合并放回平衡树
4.分裂：按照节点值的大小关系递归，直到空节点
5.合并：选择权值较大的节点为根，递归合并
6.序列平衡树：使用排名代替下标，动态维护排名基本数据维护（值域平衡树）：
1.前驱/后继查询：按照对应权值分裂+单向递归
2.值域区间/连续数（代数式）：查找对应权值+分裂区间
3.集合插入/删除：分离对应权值分裂+单点修改
4.集合整体（值域区间）操作：分裂对应区间+延迟标记
5.排名查询：递归至对应节点
基本数据维护（序列平衡树）：
1.序列插入/删除：按照排名分裂+平衡树插入/删除
2.序列区间删除：按照排名分裂+左右合并
3.普通数据维护：区间合并+单点修改/延迟标记
4.区间翻转：子树翻转+端点数据翻转+延迟标记
5.区间旋转：查找旋转点+左右交换
6.区间平移/交换：分离对应区间+交换位置/*
data：存储数据，自定义加法运算
Tag：延迟标记
root：平衡树根节点
cnt：节点总数
Init：节点初始化
Modify：节点修改
build：新建节点（动态开点）
Push_up：信息合并
Push_down：下传延迟标记
split_val：按照权值分裂（权值平衡树）
split_cnt：按照排名分裂（序列平衡树）
merge：平衡树合并
*/
struct FHQ_Treap{
int lc,rc;
data now,sum;
Tag lazy;
};
struct FHQ_Treap Tp[maxN];
int root,cnt;
int build(int val){Tp[++cnt].rnd=rand();Tp[cnt]=Init(val);return cnt;}
void Push_up(int id){
Tp[id].sum=data{0};
if(Tp[id].lc) Tp[id].sum=Tp[id].sum+Tp[Tp[id].lc].sum;
Tp[id].sum=Tp[id].sum+Tp[id].now;
if(Tp[id].rc) Tp[id].sum=Tp[id].sum+Tp[Tp[id].rc].sum;
}
void Push_down(int id){
if(Tp[id].lc) Modify(Tp[id].lc,Tp[id].lazy);
if(Tp[id].rc) Modify(Tp[id].rc,Tp[id].lazy);
Tp[id].lazy=Tag{0};
}
void split_val(int id,int &p,int &q,int val){
if(!id){p=0;q=0;return;}
Push_down(id);
if(Tp[id].val<=val){p=id;split_val(Tp[id].rc,Tp[p].rc,q,val);Push_up(p);}
else{q=id;split_val(Tp[id].lc,p,Tp[q].lc,val);Push_up(q);}
}
void split_cnt(int id,int &p,int &q,int cnt){
if(!id){p=0;q=0;return;}
Push_down(id);
if(Tp[Tp[id].lc].cnt<cnt){q=id;split_cnt(Tp[id].lc,p,Tp[id].lc,cnt);Push_up(q);}
else{p=id;split_cnt(Tp[id].rc,Tp[id].rc,q,cnt-Tp[Tp[id].lc].cnt-1);Push_up(p);}
}
int merge(int p,int q){
if(!p||!q) return p^q;
Push_down(p);Push_down(q);
if(Tp[p].rnd<Tp[q].rnd){Tp[p].rc=merge(Tp[p].rc,q);Push_up(p);retu;rn p}
else{Tp[q].lc=merge(p,Tp[q].lc);Push_up(q);return q;}
}
void Update(int l,int r,Tag val){
int p1,p2,p3;
split(root,p1,p3,r);split(p1,p1,p2,l-1);
Modify(p2,val);root=merge(merge(p1,p2),p3);
}
data query(int l,int r){
int p1,p2,p3;
split(root,p1,p3,r);split(p1,p1,p2,l-1);
data ans=Tp[p2].sum;root=merge(merge(p1,p2),p3);
return ans;
}平衡树二分
适用范围：
1.使用平衡树维护的二分问题
2.结构改变的二分问题
3.符合一定条件的最值数据
核心思想：
1.递归平衡树，利用节点储存的数据判断二分方向
2.将节点数据分为左子树、当前节点、右子树三类
3.将当前二分值与三类数据分别比较，判断二分区间data query(int id,int val){
if(!id) return data{0};
if(Tp[id].rc&&check(Tp[Tp[id].rc].sum,val)) return query(Tp[id].rc,val);
if(check(Tp[id].now,val)) return Tp[id].now;
return query(Tp[id].lc,val);
}平衡树合并
适用范围：（值域相交+修改操作）平衡树合并
时间复杂度：均摊O(log(n)*log(V))
核心思想：
1.将平衡树划分为多棵值域不交的平衡树，依次合并
2.枚举P的最小节点，查找Q中对应的前驱+后继
3.分裂P中前驱-后继之间的节点，整体插入Q
4.使用并查集，查找+合并边界的相同节点
5.重复合并操作，直到树P为空int f[maxV];
int Join(int p,int q){
while(p&&q){
if(A[p].val>A[q].val) swap(p,q);
int p1=p;Push_down(p1);while(A[p1].lc){p1=A[p1].lc;Push_down(p1);}
int p2,p3;split(q,p2,p3,A[p1].val);
int p4=p2;Push_down(p4);while(A[p4].rc){p4=A[p4].rc;Push_down(p4);}
if(p4&&p1&&A[p4].val==A[p1].val){f[getf(p1)]=getf(p4);split(p,p1,p,A[p1].val);}
int p5=p3;Push_down(p5);while(A[p5].lc){p5=A[p5].lc;Push_down(p5);}
int p6;split(p,p6,p,A[p5].val);
int p7=p6;Push_down(p7);while(A[p7].rc){p7=A[p7].rc;Push_down(p7);}
if(p7&&p5&&A[p7].val==A[p5].val){f[getf(p7)]=getf(p5);split(p6,p6,p7,A[p7].val-1);}
q=merge(merge(p2,p6),p3);
}
return p^q;
}KD-Tree
适用范围：高维矩形问题/高维偏序问题/多维度数据维护
时间复杂度：O(n^(1-1/k))
核心思想：
1.使用平衡树维护所有节点
2.每层选择一个维度，按照对应维度划分数据
3.交替选择维度，建立KD-Tree
4.在每一层维护对应数据+维度极值
5.查询操作：使用维度极值剪枝+递归查询
6.替罪重构：合并/插入时，将KD-Tree重构为完全二叉树
7.二进制分组：建立log(n)棵KD-Tree，插入时依次合并
8.虚拟插入：将节点一次性插入+重构，递归更新数据/*
二维KD-Tree：
build：新建节点
Push_up：数据合并
rebuild：重构KD-Tree
cycle：回收节点
query：KD-Tree查询
Update：KD-Tree插入
ask：数据查询
*/
struct node{int x,y;data val;};
struct node Q[maxN];
bool cmp_1(int x,int y){return Q[x].x<Q[y].x;}
bool cmp_2(int x,int y){return Q[x].y<Q[y].y;}
int pos[maxN],cntp;
struct KD_Tree{
int lc,rc,Id;
int val[2][2];
data sum;
};
struct KD_Tree A[maxN];
int S[maxN],cntS;
int root[32],cnt;
int build(int Id){
int now=(cntS?S[cntS--]:++cnt);
A[now].lc=0;A[now].rc=0;A[now].Id=Id;A[now].sum=Q[Id].val;
A[now].val[0][0]=Q[Id].x;A[now].val[1][0]=Q[Id].x;
A[now].val[0][1]=Q[Id].y;A[now].val[1][1]=Q[Id].y;
return now;
}
void Push_up(int id){
A[id].sum=Q[A[id].Id].val;
if(A[id].lc){
A[id].sum=A[A[id].lc].sum+A[id].sum;
A[id].val[0][0]=min(A[id].val[0][0],A[A[id].lc].val[0][0]);A[id].val[0][1]=min(A[id].val[0][1],A[A[id].lc].val[0][1]);
A[id].val[1][0]=max(A[id].val[1][0],A[A[id].lc].val[1][0]);A[id].val[1][1]=max(A[id].val[1][1],A[A[id].lc].val[1][1]);
}
if(A[id].rc){
A[id].sum=A[id].sum+A[A[id].rc].sum;
A[id].val[0][0]=min(A[id].val[0][0],A[A[id].rc].val[0][0]);A[id].val[0][1]=min(A[id].val[0][1],A[A[id].rc].val[0][1]);
A[id].val[1][0]=max(A[id].val[1][0],A[A[id].rc].val[1][0]);A[id].val[1][1]=max(A[id].val[1][1],A[A[id].rc].val[1][1]);
}
}
int rebuild(int dep,int l,int r){
if(l>r) return 0;
int mid=(l+r)>>1;
if(dep&1) nth_element(pos+l,pos+mid,pos+r+1,cmp_1);
else nth_element(pos+l,pos+mid,pos+r+1,cmp_2);
int now=build(pos[mid]);
A[now].lc=rebuild(dep^1,l,mid-1);A[now].rc=rebuild(dep^1,mid+1,r);
Push_up(now);return now;
}
data query(int id,int lx,int ly,int rx,int ry){
if(!id) return data{0};
if(A[id].val[0][0]>rx||A[id].val[0][1]>ry) return data{0};
if(A[id].val[1][0]<lx||A[id].val[1][1]<ly) return data{0};
if(A[id].val[0][0]>=lx&&A[id].val[0][1]>=ly&&A[id].val[1][0]<=rx&&A[id].val[1][1]<=ry) return A[id].sum;
data ans=query(A[id].lc,lx,ly,rx,ry)+query(A[id].rc,lx,ly,rx,ry);
if(Q[A[id].Id].x>=lx&&Q[A[id].Id].y>=ly&&Q[A[id].Id].x<=rx&&Q[A[id].Id].y<=ry) return ans+Q[A[id].Id].val;
return ans;
}
void cycle(int id){
if(!id) return;S[++cntS]=id;
cycle(A[id].lc);pos[++cntp]=A[id].Id;cycle(A[id].rc);
}
void Update(int id){
int now=0;cntp=0;pos[++cntp]=id;
while(now<=30&&root[now]){cycle(root[now]);root[now++]=0;}
root[now]=rebuild(1,1,cntp);
}
data ask(int lx,int ly,int rx,int ry){
data ans=0;
for(int i=0;i<=30;i++) if(root[i]) ans+=query(root[i],lx,ly,rx,ry);
return ans;
}