左偏树学习总结
内容
在学OI的前期，我们接触了一种数据结构，叫做堆。它资瓷插入一个元素，查询最小/大元素和删除最小/大元素。然后就发现STL的$priority \ queue$可以直接用，非常的方便。
但是有时候题目让我们资瓷两个堆的合并，这样$priority \ queue$就不行了(但是pb_ds还是可以的)。这样我们就要手写左偏树。
什么是左偏树呢？首先，从名字上看，它是一棵树。其实它还是一棵二叉树。它的节点上存4个值：左、右子树的地址，权值，距离。
权值就是堆里面的值。距离表示这个节点到它子树里面最近的叶子节点的距离。叶子节点距离为0。
既然是一种特殊的数据结构，那肯定有它自己的性质。左偏树有几个性质(小根为例)。
性质一：节点的权值小于等于它左右儿子的权值。
堆的性质，很好理解。
性质二：节点的左儿子的距离不小于右儿子的距离。
在写平衡树的时候，我们是确保它的深度尽量的小，这样访问每个节点都很快。但是左偏树不需要这样，它的目的是快速提取最小节点和快速合并。所以它并不平衡，而且向左偏。但是距离和深度不一样，左偏树并不意味着左子树的节点数或是深度一定大于右子树。
性质三：节点的距离等于右儿子的距离+1。
没什么好说的= =
性质四：一个n个节点的左偏树距离最大为$log(n+1)-1$
这个怎么证明呢？我们可以一点一点来。
若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。
节点最少的话，就是左右儿子距离一样，这就是完全二叉树了。
若一棵左偏树的距离为k，则这棵左偏树至少有$2^{k+1}-1$个节点。
距离为k的完全二叉树高度也是k，节点数就是$2^{k+1}-1$。
这样就可以证明性质四了。因为$n>=2^{k+1}-1$，所以$k<=log(n+1)-1$
有了性质，我们来讲讲它的操作。
1.合并
我们假设A的根节点小于等于B的根节点（否则交换A,B），把A的根节点作为新树C的根节点，剩下的事就是合并A的右子树和B了。
合并了A的右子树和B之后，A的右子树的距离可能会变大，当A的右子树 的距离大于A的左子树的距离时，性质二会被破坏。在这种情况下，我们只须要交换A的右子树和左子树。
而且因为A的右子树的距离可能会变，所以要更新A的距离=右儿子距离+1。这样就合并完了。
代码
int merge(int x,int y)
{
if (x==0 || y==0)
return x+y;
if (val[x]>val[y] || (val[x]==val[y] && x>y))
swap(x,y);
ch[x][1]=merge(ch[x][1],y);
f[ch[x][1]]=x;
if (dis[ch[x][0]]<dis[ch[x][1]])
swap(ch[x][0],ch[x][1]);
dis[x]=dis[ch[x][1]]+1;
return x;
}
我们来分析一下复杂度。我们可以看出每次我们都把它的右子树放下去合并。因为一棵树的距离取决于它右子树的距离(性质三)，所以拆开的过程不会超过它的距离。根据性质四，不会超过$log(n_x+1)+log(n_y+1)-2$，复杂度就是$O(\log n_x+\log n_y)$
2.插入
插入一个节点，就是把一个点和一棵树合并起来。
因为其中一棵树只有一个节点，所以插入的效率是$O(\log n)$
3.删除最小/大点
因为根是最小/大点，所以可以直接把根的两个儿子合并起来。
因为只合并了一次，所以效率也是$O(\log n)$。
4.构造
把n个点构造成一棵左偏树的话，也非常常用。
第一种暴力的思想就是一个一个插入，效率$O(n\log n)$
第二种可以模仿一下二叉堆的构造
将n个节点放入队列。
不断地从队首取出两棵左偏树，将它们合并之后加入队尾。
当队列中只剩下一棵左偏树时，结束。
我们分析一下它的复杂度。设$n=2^k$，则复杂度为：
$${n \over 2} \times O(1)+{n \over 4} \times O(2)+{n \over 8} \times O(3)+ \cdots =O(n \times \sum_{i=1}^k{i \over 2^i})=O(n \times (2-{k+2\over 2^k}))=O(n)$$
5.删除任意节点
因为左偏树没有平衡树的性质，所以我们没法删除权值为特定值的点，也没法查找特定值的点的位置。
但是要删除某特定位置的点还是能做到的。我们先和删除最值一样，把它的孩子合并起来。
因为我们合并后的新树的距离可能会改变，所以要更新一下q的距离。
假如q的距离是p的距离+1，那么无论p是左右子树都不需要调整。
假如p的距离+1小于q的距离，就改下q的距离，而且假如p是左子树的话需要交换子树。由于q的距离小了，还需要更新它的父亲。
假如p距离变大了的话，看看p是不是左子树，是左子树的话就结束了。但是p是右子树的话，就有两种可能，假如p的距离仍然小于q的左子树，那就直接改q的距离就好了；大于的话还要换下子树，向上走。(在这里还有一种情况就是原来的左右子树距离一样，那就不用更新q的距离，直接结束就好了)
void del_pos(int x)
{
int q=f[x],p=merge(ch[x][0],ch[x][1]);
f[p]=q;val[x]=-1;
if (q)
ch[q][ch[q][1]==x]=p;
while(q)
{
if (dis[ch[q][0]]<dis[ch[q][1]])
swap(ch[q][0],ch[q][1]);
if (dis[ch[q][1]]+1==dis[q])
return;
dis[q]=dis[ch[q][1]]+1;
q=f[q];
}
}
下面分两种情况讨论删除操作的时间复杂度。
情况1：p的距离减小了。在这种情况下，由于q的距离只能缩小，当循环结束时，要么根节点处理完了，q为空；要么p是q的右子树并且$dis[p]+1=dis[q]$；如果$dis[p]+1>dis[q]$，那么p一定是q的左子树，否则会出现q的右子树距离缩小了，但是加1以后却大于q的距离的情况，不符合左偏树的性质三。不论哪种情况，删除操作都可以结束了。注意到，每一次循环，p的距离都会加1，而在循环体内，$dis[p]+1$最终将成为某个节点的距离。根据性质四，任何的距离都不会超过$\log n$，所以循环体的执行次数不会超过$\log n$。
情况2：p的距离增大了。在这种情况下，我们将必然一直从右子树向上调整，直至q为空或p是q的左子树时停止。一直从右子树升上来这个事实说明了循环的次数不会超过$\log n$（性质四）。
最后我们看到这样一个事实，就是这两种情况只会发生其中一个。如果某种情况的调整结束后，我们已经知道要么q为空，要么$dis[p]+1=dis[q]$，要么p是q的左子树。这三种情况都不会导致另一情况发生。直观上来讲，如果合并后的新子树导致了父节点的一系列距离调整的话，要么就一直是往小调整，要么是一直往大调整，不会出现交替的情况。这样效率就是$O(\log n)$
但是说了这么多，有一个操作是还是$O(n)$的：找到某个节点所在左偏树的根。因为需要一直走father走到根。我试了好几种方法优化都实现不了。也许这就是让人理性愉悦的数据结构吧2333333
一个板子：luogu3377
#include <cstdio>
#define N 100010
using namespace std;
int inline read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void swap(int &x,int &y){int t=x;x=y,y=t;}
int ch[N][2],val[N],dis[N],f[N],n,m;
int merge(int x,int y)
{
if (x==0 || y==0)
return x+y;
if (val[x]>val[y] || (val[x]==val[y] && x>y))
swap(x,y);
ch[x][1]=merge(ch[x][1],y);
f[ch[x][1]]=x;
if (dis[ch[x][0]]<dis[ch[x][1]])
swap(ch[x][0],ch[x][1]);
dis[x]=dis[ch[x][1]]+1;
return x;
}
int getf(int x)
{
while(f[x]) x=f[x];
return x;
}
void pop(int x)
{
val[x]=-1;
f[ch[x][0]]=f[ch[x][1]]=0;
merge(ch[x][0],ch[x][1]);
}
main()
{
n=read(),m=read();
dis[0]=-1;
for (int i=1;i<=n;i++)
val[i]=read();
for (int i=1;i<=m;i++)
{
int com=read();
if (com==1)
{
int x=read(),y=read();
if (val[x]==-1 || val[y]==-1)
continue;
if (x==y)
continue;
int fx=getf(x),fy=getf(y);
merge(fx,fy);
}
else
{
int x=read();
if (val[x]==-1)
puts("-1");
else
{
int y=getf(x);
printf("%d\n",val[y]);
pop(y);
}
}
}
}
目前效率第一，欢迎超越。
第二：luogu3273
这题多了几个操作。
1.合并两个堆：直接merge
2.把某个点加：把这个点删了，再加一个更新了权值之后的点。
3.整个堆加：在根上打mark
4.全局加：记个全局mark
5.查询单点：一路加上所有父亲的mark再输出
6.查询堆最大值：直接输出
7.查询全局最大值。。
第七个操作需要把所有堆的根提取出来再建个堆。每次merge都要把并进去的堆的最大值删掉，单点加和整堆加都需要更新最大值。
有很多细节要注意
#include <cstdio>
#include <queue>
#define N 300010
using namespace std;
int inline read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void swap(int &x,int &y){int t=x;x=y,y=t;}
int n,m,add,root;
char com[10];
struct zps
{
int ch[N][2],val[N],dis[N],f[N],mark[N];
void clear(int x){f[x]=ch[x][0]=ch[x][1]=0;}
int sum(int x)
{
int ans=0;
while(x=f[x]) ans+=mark[x];
return ans;
}
void pushdown(int x)
{
if (ch[x][0])
val[ch[x][0]]+=mark[x],
mark[ch[x][0]]+=mark[x];
if (ch[x][1])
val[ch[x][1]]+=mark[x],
mark[ch[x][1]]+=mark[x];
mark[x]=0;
}
int merge(int x,int y)
{
if (x*y==0)
return x+y;
if (val[x]<val[y])
swap(x,y);
pushdown(x);
ch[x][1]=merge(ch[x][1],y);
f[ch[x][1]]=x;
if (dis[ch[x][0]]<dis[ch[x][1]])
swap(ch[x][0],ch[x][1]);
dis[x]=dis[ch[x][1]]+1;
return x;
}
int getf(int x)
{
while(f[x]) x=f[x];
return x;
}
int del_pos(int x)
{
pushdown(x);
int q=f[x],p=merge(ch[x][0],ch[x][1]);
f[p]=q;
if (q)
ch[q][ch[q][1]==x]=p;
while(q)
{
if (dis[ch[q][0]]<dis[ch[q][1]])
swap(ch[q][0],ch[q][1]);
if (dis[ch[q][1]]+1==dis[q])
return root;
dis[q]=dis[ch[q][1]]+1;
p=q;
q=f[q];
}
return p;
}
void add_tree(int x,int v)
{
int fx=getf(x);
val[fx]+=v;
mark[fx]+=v;
}
int add_point(int x,int v)
{
int fx=getf(x);
if (fx==x)
if (ch[x][0]+ch[x][1]==0)
{
val[x]+=v;
return x;
}
else
if (ch[x][0])
fx=ch[x][0];
else
fx=ch[x][1];
del_pos(x);
val[x]+=v+sum(x);
clear(x);
return merge(getf(fx),x);
}
int build()
{
queue<int>que;
for (int i=1;i<=n;i++)
que.push(i);
while(que.size()>1)
{
int x=que.front();que.pop();
int y=que.front();que.pop();
int z=merge(x,y);
que.push(z);
}
return que.front();
}
}h1,h2;
main()
{
n=read();
h1.dis[0]=h2.dis[0]=-1;
for (int i=1;i<=n;i++)
h1.val[i]=read(),h2.val[i]=h1.val[i];
root=h2.build();
m=read();
for (int i=1;i<=m;i++)
{
scanf("%s",com);
if (com[0]=='U')
{
int x=read(),y=read();
int temp,fx=h1.getf(x),fy=h1.getf(y);
if (fx!=fy)
{
temp=h1.merge(fx,fy);
if (temp==fx)
root=h2.del_pos(fy);
else
root=h2.del_pos(fx);
}
}
else
if (com[0]=='A')
if (com[1]=='1')
{
int x=read(),v=read();
root=h2.del_pos(h1.getf(x));
int y=h1.add_point(x,v);
h2.val[y]=h1.val[y];
h2.clear(y);
root=h2.merge(root,y);
}
else if (com[1]=='2')
{
int x=read(),v=read(),fx=h1.getf(x);
root=h2.del_pos(fx);
h1.val[fx]+=v;
h1.mark[fx]+=v;
h2.val[fx]=h1.val[fx];
h2.clear(fx);
root=h2.merge(root,fx);
}
else if (com[1]=='3')
{
int v=read();
add+=v;
}
else;
else if (com[0]=='F')
if (com[1]=='1')
{
int x=read();
printf("%d\n",h1.val[x]+add+h1.sum(x));
}
else if (com[1]=='2')
{
int x=read();
printf("%d\n",h1.val[h1.getf(x)]+add);
}
else if (com[1]=='3')
printf("%d\n",h2.val[root]+add);
}
}
效率也是第一。。
下一道luogu3261
这题就是每个点建个左偏树，记录这个点上的人。dfs的时候先把儿子上的人merge到这个点上，然后判断堆顶上的是否大于生命值，小于就弹出去。统计一下就好了。
#include <cstdio>
#define N 300010
using namespace std;
long long inline read()
{
long long x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct node{int to,next;}e[N];
int tot,st[N];
int n,m,f;
int ch[N][2],dis[N],rt[N],s[N],ed[N],dep[N],die[N];
long long h[N],val[N],am[N],mm[N],a[N],v[N];
void add(int x,int y){e[++tot].to=y,e[tot].next=st[x],st[x]=tot;}
void swap(int &x,int &y){int t=x;x=y,y=t;}
void upd(int x,long long add,long long mul)
{
if (!x) return;
val[x]*=mul,val[x]+=add;
mm[x]*=mul,am[x]*=mul,am[x]+=add;
}
void pushdown(int x)
{
upd(ch[x][0],am[x],mm[x]);
upd(ch[x][1],am[x],mm[x]);
am[x]=0,mm[x]=1;
}
int merge(int x,int y)
{
if (x*y==0)
return x+y;
if (val[x]>val[y])
swap(x,y);
pushdown(x);
ch[x][1]=merge(ch[x][1],y);
if (dis[ch[x][1]]>dis[ch[x][0]])
swap(ch[x][0],ch[x][1]);
dis[x]=dis[ch[x][1]]+1;
return x;
}
void dfs(int x,int deep)
{
dep[x]=deep;
for (int i=st[x];i;i=e[i].next)
{
dfs(e[i].to,deep+1);
rt[x]=merge(rt[x],rt[e[i].to]);
}
while (rt[x] && h[x]>val[rt[x]])
{
pushdown(rt[x]);
die[x]++;
ed[rt[x]]=x;
rt[x]=merge(ch[rt[x]][0],ch[rt[x]][1]);
}
if (a[x])
upd(rt[x],0,v[x]);
else
upd(rt[x],v[x],1);
}
main()
{
n=read(),m=read();
dis[0]=-1;
for (int i=1;i<=n;i++)
h[i]=read();
for (int i=2;i<=n;i++)
{
f=read(),a[i]=read(),v[i]=read();
add(f,i);
}
for (int i=1;i<=m;i++)
{
val[i]=read(),s[i]=read();mm[i]=1;
rt[s[i]]=merge(rt[s[i]],i);
}
dfs(1,1);
for (int i=1;i<=n;i++)
printf("%d\n",die[i]);
for (int i=1;i<=m;i++)
printf("%d\n",dep[s[i]]-dep[ed[i]]);
}
效率还是第一。。
cogs526
裸题
#include <cstdio>
#define N 100010
using namespace std;
int inline read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void swap(int &x,int &y){int t=x;x=y,y=t;}
int n,m;
int ch[N][2],val[N],dis[N],f[N];
int merge(int x,int y)
{
if (x*y==0)
return x+y;
if (val[x]<val[y])
swap(x,y);
ch[x][1]=merge(ch[x][1],y);
f[ch[x][1]]=x;
if (dis[ch[x][0]]<dis[ch[x][1]])
swap(ch[x][0],ch[x][1]);
dis[x]=dis[ch[x][1]]+1;
return x;
}
int getf(int x)
{
while(f[x]) x=f[x];
return x;
}
int pop(int x)
{
f[ch[x][0]]=f[ch[x][1]]=0;
int p=merge(ch[x][0],ch[x][1]);
ch[x][0]=ch[x][1]=0;
return p;
}
main()
{
freopen("monkeyk.in","r",stdin);
freopen("monkeyk.out","w",stdout);
n=read();
dis[0]=-1;
for (int i=1;i<=n;i++)
val[i]=read();
m=read();
for (int i=1;i<=m;i++)
{
int x=read(),y=read();
int fx=getf(x),fy=getf(y);
if (fx==fy)
puts("-1");
else
{
int x1=pop(fx),y1=pop(fy);
val[fx]/=2,val[fy]/=2;
int p=merge(fx,fy);
int q=merge(x1,y1);
printf("%d\n",val[merge(p,q)]);
}
}
}