一种支持修改的数据结构

左偏树(可并堆)

定义

在这之前，我们先来阐述一些定义：

1. 外节点：\(ls\) 或 \(rs\) 为空的节点
2. 距离：节点的距离 \(dist_x\) 定义为节点 \(x\) 到距 \(x\) 最近的外节点的距离，空节点的距离为 \(-1\)

其次是左偏树的性质：

1. 左偏性：即满足 \(dist_{ls}>=dist_{rs}\)
2. 堆性质：若满足小根堆，则满足 \(v_x<=v_{ls}\) , \(v_x<=v_{rs}\)

这引出了左偏树的一些结论：

1. 节点 \(x\) 的距离为 \(dist_{rs}+1\) (由于左偏性)
2. 距离为 \(n\) 的左偏树至少有 \(2^n-1\) 个节点，最少时，形态接近满二叉树
3. 有 \(n\) 的节点的左偏树的根节点距离是 \(O(log_2n)\)

接下来是左偏树支持的一些操作：

1. 合并
2. 插入给定值
3. 求最小值
4. 删除最小值
5. 求指定节点在左偏树的根节点

详解

一.合并

\(merge(x,y)\) 为合并以 \(x\) , \(y\) 为根节点的两棵子树，返回值为合并后的根节点。

先考虑堆的合并：

1. 若 \(v_x<=v_y\) ,则以 \(x\) 做为合并后的根节点。(若有 \(v_x>v_y\) 则 \(swap(x,y)\) )
2. 将 \(y\) 与 \(x\) 的一个儿子合并，合并后的根节点代替与 \(y\) 合并的儿子的位置，返回 \(x\)
3. 重复以上操作，直到 \(x\) 与 \(y\) 有一方是空节点。

然鹅，这样合并的操作复杂度为 \(O(h)\) \(h\) 为树高，当堆退化为链时，复杂度为 \(O(n)\) ,想要进一步优化，则要优化左偏树。由于在左偏树中，左儿子的距离大于右儿子的距离，所以每次选择右儿子进行合并，则单次复杂度可以来到 \(O(long_2n)\) ;

但两棵树合并后可能破坏左偏树的左偏性，故在每次合并后，判断节点 \(x\) 是否符合 \(dist_{ls}>=dist_{rs}\) ，若不满足则 \(swap(ls,rs)\) ,并维护 \(dist_x=dist_{rs}+1\) ,即可维护左偏树的左偏性。

二.插入给定值

新建一个值等于插入值的点，将该节点与左偏树合并即可。

三.求最小值

由于左偏树的堆性质，所以左偏树的最小值即为左偏树的根节点的值。

四.删除最小值

等价于删除左偏树的根节点，合并左右子树即可。

五.求指定节点在左偏树的根节点

可以记录每个节点的父亲节点，然后暴力跳父亲节点。

<code>int find(int x){

if(rt[x]) return find(rt[x]);

return x;

}

是不是非常熟悉，当然，可以使用路径压缩优化。

int find(int x){

if(rt[x]) return rt[x]=find(fa[x]);

return x;

}

如此，我们便需维护 \(rt\) 数组。在合并两个节点时，令：

rt[x]=rt[y]=merge(x,y);

在删除左偏树的最小值时

rt[ls[x]]=rt[rs[x]]=rt[x]=merge(ls[x],rs[x]);

因为 \(x\) 之前靠近根节点,在路径压缩时，\(rt\) 数组有可能等于 \(x\) ，所以 \(rt[x]\) 也指向删除后的根节点。

由于使用了路径压缩优化，导致 \(x\) 的树形结构被破坏，若之后还需使用 \(x\) 则需重建一个同值节点。使用路径压缩优化后，可以在 \(O(log_2n)\) 的时间复杂度内找到一个点在左偏树的根节点。

完整代码

#include <bits/stdc++.h>

#define seq(q, w, e) for (int q = w; q <= e; q++)

#define ll long long

using namespace std;

const int maxn = 1e5+10;

int m,n,x,y,op;

int ls[maxn],rs[maxn],dist[maxn],rt[maxn];

bool tf[maxn];

struct node{ //点节点结构体

int id,v; //编号，价值

bool operator<(node x)const{return v==x.v?id<x.id:v<x.v;}

}v[maxn];

int find(int x){ //寻找祖宗

if(rt[x]==x)

return x;

return rt[x]=find(rt[x]); //路径压缩

}

int merge(int x,int y){ //合并x，y

if(!x||!y) //若这两个节点中存在空节点

return x+y;

if(v[y]<v[x]) //保证v[x]<v[y]

swap(x,y);

rs[x]=merge(rs[x],y); //由于左偏性质，最优合右树

if(dist[ls[x]]<dist[rs[x]]) //维护左偏性质

swap(ls[x],rs[x]);

dist[x]=dist[rs[x]]+1; //维护根节点距离

return x;

}

signed main()

{

ios::sync_with_stdio(0);

cin.tie(0);cout.tie(0);

dist[0]=-1;

cin>>n>>m;

seq(i,1,n){ //初始化

cin>>v[i].v; //输入价值

rt[i]=i;

v[i].id=i;

}

while(m--){

cin>>op>>x;

if(op==1){

cin>>y;

if(tf[x]||tf[y]) continue;

x=find(x);y=find(y);

if(x!=y) rt[x]=rt[y]=merge(x,y); //若不在一棵树上

}

else{

if(tf[x]){

cout<<"-1"<<"\n";

continue;

}

x=find(x);

cout<<v[x].v<<"\n";

tf[x]=true;

rt[ls[x]]=rt[rs[x]]=rt[x]=merge(ls[x],rs[x]);

ls[x]=rs[x]=dist[x]=0;

}

}

return 0;

}