左偏樹

左偏樹

左偏樹是一種可并堆，具有堆的性質，且可以快速合并。

dist 定義

對于一棵二叉樹，我們定義外節點為左兒子或右兒子為空的節點，定義一個外節點的 \(dist\) 為 \(1\)，一個不是外節點的 \(dist\) 為其到子樹中最近的外節點的距離加一。空節點的 \(dist\) 為 \(0\)。

一棵有 \(n\) 個節點的二叉樹，根的 \(dist\) 不超過 \(\left\lceil \log(n+1) \right\rceil\)，這是因為一棵根的 \(dist\) 為 \(x\) 的二叉樹至少有 \(x-1\) 層是滿的，那麼就至少有 \(2^x-1\) 個節點。注意這個性質是所有二叉樹都具有的，并不是隻有左偏樹具有。

定義與性質

左偏樹是一棵二叉樹，它不僅具有堆的性質，并且是左偏的，即每個節點左兒子的 \(dist\) 都大于等于右兒子的 \(dist\)。

是以，左偏樹的每個節點的 \(dist\) 都等于其右兒子的 \(dist\) 加一。

需要注意的是，左偏樹的深度沒有保證，一條向左的鍊也是左偏樹。

核心操作：Merge

以下若無特殊說明，都指的是小根堆。

合并兩個堆的時候，由于要滿足堆的性質，先取值較小的節點作為合并之後的根節點，然後将這個根的左兒子左右合并之後根的左兒子，遞歸的合并其右兒子與另一個堆，作為合并後堆的右兒子。注意如果不符合左偏性質，就交換兩個兒子。

代碼：

inline int Merge(int a,int b){
        if(!a||!b) return a+b;
        if(p[b]<p[a]) swap(a,b);
        rs(a)=Merge(rs(a),b);
        if(p[rs(a)].dist>p[ls(a)].dist) swap(rs(a),ls(a));
        p[a].dist=p[rs(a)].dist+1;
        return a;
    }
      

由于左偏性質，每遞歸一層，其中 \(a,b\) 所代表的的節點的其中一個的 \(dist\) 會減 \(1\)，是以合并兩個大小為 \(n,m\) 的堆的複雜度為 \(O(\log n+\log m)\)。

有不用交換左右兒子的寫法，但不建議學，個人感覺還是确定下來比較好。

其他操作

插入節點

把插入的節點視為堆，合并就可以。

删除根

合并左右子樹就可以。

删除任意節點

線将左右兒子合并，然後直接從下向上更新 \(dist\)，不滿足左偏性質的時候交換左右兒子，當 \(dist\) 無需更新的時候結束遞歸。

• 複雜度證明：我們令目前 pushup 的這個節點為 \(x\)，其父親為 \(y\)，一個節點的初始 \(dist\) 為它在 pushup 前的 \(dist\)。我們先 pushup 一下删除的節點，然後從其父親開始讨論複雜度。繼續遞歸下去有兩種情況：

1. \(x\) 是 \(y\) 的右兒子，此時 \(y\) 的初始 \(dist\) 為 \(x\) 的初始 \(dist\) 加一。
2. \(x\) 是 \(y\) 的左兒子，隻有 \(y\) 的左右兒子初始 \(dist\) 相等的時候（此時左兒子 \(dist\) 減一會導緻左右兒子交換）才會繼續遞歸下去，是以 \(y\) 的初始 \(dist\) 仍然是 \(x\) 的初始 \(dist\) 加一。

是以我們得到，除了第一次 pushup（因為被删除節點的父親的初始 \(dist\) 不一定等于被删除節點左右兒子合并後的初始 \(dist\) 加一），每遞歸一層 \(x\) 的初始 \(dist\) 就會加一，是以最多遞歸 \(\log n\) 層。

整個堆加上或減去一個值

直接在根上打标記，或者不改變相對大小的操作都可以。

打标記得時候注意每通路到就往下傳就可以。

例題

​​左偏樹模闆題​​

注意因為我們要保證複雜度，是以我們不能暴力跳父親來找根，我們用并查集來維護根。注意我們删除節點時并查集也要相對應的處理。

#include<bits/stdc++.h>
#include<iostream>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 500010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

struct node{
    int fa,val,dist,l,r,id;
    inline node(){}
    inline node(int fa,int val,int dist,int l,int r,int id) :
        fa(fa),val(val),dist(dist),l(l),r(r),id(id) {}
    inline bool operator < (const node &b) const{
        if(val!=b.val) return val<b.val;
        return id<b.id;
    }
}p[N];

int fa[N];
inline int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}

bool vis[N];

//我們規定，如果一個節點編号在并查集上所在集合的根為 k，那麼該節點在左偏樹上的根就是 k

struct LeftistTree{
    #define ls(a) p[a].l
    #define rs(a) p[a].r
    inline int Merge(int a,int b){
        if(!a||!b) return a+b;
        if(p[b]<p[a]) swap(a,b);
        rs(a)=Merge(rs(a),b);
        if(p[rs(a)].dist>p[ls(a)].dist) swap(rs(a),ls(a));
        p[a].dist=p[rs(a)].dist+1;
        return a;
    }
    inline void EasyMerge(int a,int b){
        if(vis[a]||vis[b]) return;
        int rta=Find(a),rtb=Find(b);
        if(rta==rtb) return;
        int nowrt=Merge(rta,rtb);
        if(nowrt==rtb) swap(rta,rtb);
        fa[rtb]=rta;
    }
    inline int Delete(int k){
        if(vis[k]) return -1;
        int rt=Find(k);vis[rt]=1;int ans=p[rt].val;
        int L=ls(rt),R=rs(rt);
        if(L==0||(p[R]<p[L]&&R!=0)) swap(L,R);
        Find(L);fa[rt]=L;fa[L]=L;
        Merge(ls(rt),rs(rt));return ans;
    }
}LT;

int n,m;

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(m);
    for(int i=1;i<=n;i++){
        int x;read(x);p[i]=node(0,x,1,0,0,i);
    }
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int op,a,b;
        read(op);read(a);
        if(op==1){
            read(b);
            LT.EasyMerge(a,b);
        }
        else printf("%d\n",LT.Delete(a));
    }
    return 0;
}