左偏树学习笔记
一、前言
左偏树是一种可以在 \(O(\log n)\) 内快速合并的堆式数据结构。
具体来说，
插入一个元素：\(O(\log n)\)。
查询最值：\(O(1)\)。
删除最值：\(O(\log n)\)。
合并：\(O(\log n)\)。
减少一个元素的值：\(O(\log n)\)。
同时它可以持久化。
二、定义
- 外节点：左儿子或者右儿子为空的节点。
- 一个节点 \(x\) 的距离 \(dis_x\) 代表节点 \(x\) 到其所在的子树内的最近的外节点的距离。特别地，如果 \(x\) 是外节点，\(dis_x=0\)；如果 \(x\) 是空节点，\(dis_x=-1\)。
三、性质
- 左偏树满足小/大根堆的性质，即对于所有节点 \(x\)，满足 \(v_x\le v_{lx}\) 且 \(v_x\le v_{rx}\)，或者对于所有节点 \(x\)，满足 \(v_x\ge v_{lx}\) 且 \(v_x\ge v_{rx}\)。
- 左偏树具有左偏性质，即对于任何一个节点 \(x\)，有 \(dis_{lx}\ge dis_{rx}\)。
四、结论
- \(dis_x=dis_{rx}+1\)。这是因为根据定义，\(dis_x=min(dis_{lx},dis_{rx})+1\) 并且 \(dis_{lx}\ge dis_{rx}\)。
- 距离为 \(n\) 的左偏树一共至少 \(2^{n+1}-1\) 个节点，取等时它是满二叉树。这是因为根据定义，对于左偏树中的每一个节点 \(x\) 都满足 \(dis_{lx}\ge dis_{rx}=n-1\)，否则 \(dis_{lx}\le dis_{rx}\)，与性质矛盾。所以左子树的第 \(dis_{rx}+1=n\) 层的所有节点全部存在。递归地考虑，知道它至少是一棵满二叉树。所以至少 \(2^{n+1}-1\) 个节点。
- 一棵有 \(n\) 个节点的左偏树距离至多为 \(\lfloor log_2(n+1)\rfloor-1\)。可以由结论 2 推得。
五、实现
我们以根节点的编号指代一棵左偏树。这里我们假定维护的是小根堆，即全部求的是节点权值的最小值。
merge(x,y)：合并两个以节点 \(x\)、\(y\) 为根的左偏树，返回合并后的左偏树的根节点编号。这是左偏树最基础的操作。- 首先，如果两棵树中有一棵为空，那么返回另外一棵树。
- 如果两棵树都非空，不妨假设 \(v_x\) 小于 \(v_y\)，否则交换 \(x\)，\(y\) 以避免讨论。
- 将 \(y\) 与 \(x\) 的右子树 \(r_x\) 合并。
- 返回时，如果回溯到节点 \(p\) 时， \(p\) 的右子节点 \(r_p\) 的距离 \(dis_{rp}\) 大于 \(p\) 的左子节点 \(l_p\) 的距离。 \(dis_{lp}\)，那么这不满足左偏树的左偏性质。所以我们交换 \(p\) 的左右子树即可。
- 最后，由于节点 \(p\) 的距离可能发生改变，我们要更新 \(p\) 的距离，即令 \(dis_p\leftarrow dis_{rp}+1\)。
总结：这样就可以合并两棵左偏树了。由于所有遍历过的节点都被更新了，所以这种修改后的依然是一棵左偏树。时间复杂度是原先的 \(dis_x\)，是 \(O(\log n)\) 级别的。
- 求最小值：根节点的值，时间复杂度 \(O(1)\)。
- 删除最小值：删除根节点，合并根节点的左右子树，时间复杂度与合并两棵左偏树相同，为 \(O(\log n)\)。
- 插入新节点：容易知道一个点也是一棵左偏树，所以可以看做两棵左偏树的合并。时间复杂度也是 \(O(\log n)\)。
- 左偏树的建树：将所有节点作为左偏树放进先进先出的队列里，每次拿出队首的两棵左偏树，将它们合并后放到队尾。那么前 \(\frac{n}{2}\) 次合并的是距离为 \(0\) 的左偏树，然后 \(\frac{n}{4}\) 次合并的是距离为 \(1\) 的左偏树，……，然后 \(\frac{n}{2^i}\) 次合并的是距离为 \(i-1\) 的左偏树。总复杂度为 \(\frac{n}{2}\times O(1)+\frac{n}{4}\times O(2)+\frac{n}{8}\times O(3)+……=O(n)\)。
- 在左偏树上删除一个指定节点（并非删除值为 \(x\) 的节点，而是删除编号为 \(x\) 的节点）。
- 首先，我们将 \(x\) 的左子树、右子树合并，得到 \(x\) 的子树新的根节点 \(p\)。
- 如果 \(p\) 是全局的根节点，结束操作。
- 否则继续分类讨论，令 \(q\) 为 \(p\) 的父亲节点。
- 新树的距离为 \(dis_p\)，如果满足 \(dis_q=dis_p+1\) ，那么结束操作。
- 如果满足 \(dis_q>dis_p+1\)，那么 \(q\) 的距离应该更新为 \(dis_p+1\)，而且如果 \(p\) 是 \(q\) 的左子节点，要交换 \(q\) 的左右子树。然后继续向上更新 \(q\) 的父亲节点。
- 如果满足 \(dis_q<dis_p+1\)，那么 \(q\) 的距离应该更新为 \(dis_p-1\)，而且如果 \(p\) 是 \(q\) 的右子节点，要交换 \(q\) 的左右子树。然后继续向上更新 \(q\) 的父亲节点。
总结：这样就可以删除任何一个指定节点了。合并是 \(O(\log n)\) 的，向上更新是 \(O(\log n)\) 的，总复杂度 \(O(\log n)\)。
- 获得节点 \(x\) 所在的左偏树的根节点。直接向上跳，使用路径压缩即可。需要维护 \(rt_x\) 的值，在合并和删除时要更新。这个操作最坏 \(O(\log n)\)。
合并：
点击查看代码
int merge(int x,int y){
if(!x||!y)return x+y;
if(val[x]<val[y])swap(x,y);
r[x]=merge(r[x],y);
if(dis[l[x]]<dis[r[x]])swap(l[x],r[x]);
dis[x]=dis[r[x]]+1;
return x;
}
删除非根节点：
点击查看代码
void pushup(ll x){
if(!x)return;
if(dis[x]!=dis[r[x]]+1){
dis[x]=dis[r[x]]+1;
pushup(fa[x]);
}
}
ll merge(ll x,ll y){
if(!x||!y)return x+y;
if(val[x]<val[y])swap(x,y);
fa[r[x]=merge(r[x],y)]=x;
if(dis[l[x]]<dis[r[x]])swap(l[x],r[x]);
pushup(x);
return x;
}
六、例题
例 1.P3377 【模板】左偏树（可并堆）
点击查看代码
int n,m,v[100010],l[100010],r[100010],d[100010],dl[100010],rt[100010];
int merge(int x,int y){
if(!x||!y)return x+y;
if(v[x]>v[y]||x>y&&v[x]==v[y])swap(x,y);
r[x]=merge(r[x],y);
if(d[r[x]]>d[l[x]])swap(l[x],r[x]);
d[x]=d[r[x]]+1;
return x;
}
int find(int x){
return x==rt[x]?x:rt[x]=find(rt[x]);
}
int main(){
n=read();m=read();d[0]=-1;
for(int i=1;i<=n;i++)v[i]=read(),rt[i]=i;
for(int op,x,y;m;m--){
op=read();x=read();
if(op==1){
y=read();
if(dl[x]||dl[y])continue;
x=find(x);y=find(y);
if(x!=y)rt[x]=rt[y]=merge(x,y);
}else{
if(dl[x]){puts("-1");continue;}
x=find(x);
write(v[x]);putchar(10);
rt[x]=rt[l[x]]=rt[r[x]]=merge(l[x],r[x]);
dl[x]=1;d[x]=l[x]=r[x]=0;
}
}
return 0;
}
例 2.P1456 Monkey King
点击查看代码
int merge(int x,int y){
if(!x||!y)return x+y;
if(val[x]<val[y])swap(x,y);
r[x]=merge(r[x],y);
if(dis[l[x]]<dis[r[x]])swap(l[x],r[x]);
dis[x]=dis[r[x]]+1;
return x;
}
int find(int x){
return x==rt[x]?x:rt[x]=find(rt[x]);
}
int work(int x){
val[x]/=2;
int p=rt[l[x]]=rt[r[x]]=merge(l[x],r[x]);
l[x]=r[x]=dis[x]=0;
return rt[p]=rt[x]=merge(p,x);
}
int main(){
while(cin>>n){
for(int i=1;i<=n;i++){
val[i]=read();
rt[i]=i;
l[i]=dis[i]=r[i]=0;
}
m=read();
for(int x,y,p;m;m--){
x=find(read());y=find(read());
if(x==y)puts("-1");
else{
x=work(x);y=work(y);
rt[x]=rt[y]=merge(rt[x],rt[y]);
write(val[rt[x]]);
putchar(10);
}
}
}
return 0;
}
例 3.P2713 罗马游戏
点击查看代码
int merge(int x,int y){
if(!x||!y)return x+y;
if(val[x]>val[y])swap(x,y);
r[x]=merge(r[x],y);
if(dis[l[x]]<dis[r[x]])swap(l[x],r[x]);
dis[x]=dis[r[x]]+1;
return x;
}
int find(int x){
return x==rt[x]?x:rt[x]=find(rt[x]);
}
int main(){
n=read();
for(int i=1;i<=n;i++)val[rt[i]=i]=read();
m=read();
for(int i=1,x,y;i<=m;i++){
char op;
cin>>op;
if(op=='M'){
x=read();y=read();
if(del[x]||del[y])continue;
x=find(x);y=find(y);
if(x!=y)rt[x]=rt[y]=merge(x,y);
}else{
x=read();
if(del[x])putchar(48);
else{
x=find(x);
write(val[x]);
rt[x]=rt[l[x]]=rt[r[x]]=merge(l[x],r[x]);
l[x]=r[x]=dis[x]=val[x]=0;
del[x]=1;
}
putchar(10);
}
}
return 0;
}
例 4.P1552 [APIO2012] 派遣
点击查看代码
int n,m,v[100010],b[100010],l[100010],r[100010],d[100010];
int sz[100010],rt[100010],c[100010],tag=0;
ll ans=0,sum[100010];
int merge(int x,int y){
if(!x||!y)return x+y;
if(c[x]<c[y])swap(x,y);
r[x]=merge(r[x],y);
if(d[r[x]]>d[l[x]])swap(l[x],r[x]);
d[x]=d[r[x]]+1;
return x;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++){
b[i]=read();c[i]=read();v[i]=read();
rt[i]=i;sz[i]=1;sum[i]=c[i];
}
for(int i=n;i>=1;i--){
while(sum[i]>m){
sum[i]-=c[rt[i]];sz[i]--;
rt[i]=merge(l[rt[i]],r[rt[i]]);
}
ans=max(ans,1ll*v[i]*sz[i]);
sum[b[i]]+=sum[i];
sz[b[i]]+=sz[i];
rt[b[i]]=merge(rt[b[i]],rt[i]);
}
cout<<ans<<'\n';
return 0;
}
题解 P3377 【【模板】左偏树（可并堆）】——雷哲涵
左偏树的特点及其应用——黄源河
左偏树——OI-WIKI