平衡树 - 分治与随机化思想的融合

· · 闲话

I.综述&解释

平衡树，是非常平衡的树吗？

啊对对对。

平衡，就是指对于每一个节点：它的左右子树大小差不超过1。

当然，我们后来发现除了某些平衡树（e.g. 替罪羊树）之外，其他的都只是做到大致平衡。

II.真·综述

这是一种用来处理元素的前驱、后继，以及处理一些可以自底向上传递数据的结构（FHQ-Treap可以完成，普通Treap因为ZigZag改变了结构所以不能分出区间）

其实，本文中探讨的都不是最严格的平衡树，只能说是比较平衡的（利用随机化平均特性的Treap和FHQ-Treap）。

让我们从平衡树的基本性质——“BST性质”谈起。

这个性质是指，如果一棵二叉树满足：

那么我们就称这棵二叉树满足“BST性质”。

所以这个有啥用？其实这就是二叉查找树的基本工作原理。

因为我们只要知道我们要找什么，我们就一定可以排除半边子树。所以就可以提升速度。

但是，如果一棵二叉树只满足以上性质，那么我们完全可以通过特殊的节点插入顺序（例如有序的插入序列）来将这棵树变成链。

这个时候我们就想起并查集的处理方式——我们不关心树的结构，只要满足BST性质即可。那么我们就可以按照某种方式对结构进行维护。

所以Treap的解决方案就是，为每个点添加随机权值，并在满足BST性质的前提下再像二叉堆一样满足“堆性质”，即每个点都比其左右子树的权值大/小。

那么，要怎么维护呢。旋转。可以发现，旋转并不会损伤BST性质。所以，维护“堆性质”不会损伤BST性质。

那么为什么要随机地维护“堆性质”呢？会发现，实际上随机如果作用在二叉堆上，那么它的高度就趋近\operatorname O(\log N)，不要问我怎么证明，大概就是因为随机数分布随机吧。这个多半玄学。

好，那么FHQ-Treap就是不同的维护方式。

它取消了旋转这个步骤，直接变成分裂和合并，按这样的方式分裂出仍然满足BST性质的树。

合并时，由于BST性质只是在意左右顺序，这个时候再来维护堆性质也是可以。

不过这么做，常数确实会大，但是好处就是，可以分出操作区间，就能像线段树一样维护区间信息了，Yeah！

本质上，这就是分治和随机化思想。所以我更改了标题

III.基操

就是不断插入元素。

不过还可以用笛卡尔树的建树方法将时间复杂度优化到O(N)

递归地，像字典树一样，找到val应该在的位置，插入一个新节点。

将这个节点旋转到最底下，直接删除

Link

不好说，大概就是，转化一下子节点和父节点的关系。

例如右旋，就是直接把父节点变成右儿子，然后把自己原来的右儿子传给父亲的左儿子。（这一子树都比原来父亲的key要小，这么转化显然合法）

更难描述，大概就是递归下去，将节点分为两类，直接连接到上面传下来的“接口”上。（这里应用用的妙）

建立两个指针，指示两棵树上正在决定的节点，这个节点由于传参就是按顺序传的，所以只要关系随机权值的大小，左树大就把它变成父亲，右树变成右儿子，然后再往下决定。

放个板子。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct FHQ_Treap{
    int l,r;
    int dat,val,siz;
    bool resv;
}t[N];
#define l(p) t[p].l
#define r(p) t[p].r
#define dat(p) t[p].dat
#define val(p) t[p].val
#define siz(p) t[p].siz
#define resv(p) t[p].resv
int tot;
int n,m;
int New(int val){
    int np=++tot;
    val(np)=val;
    dat(np)=rand();
    siz(np)=1;
    return np;
}
void Pushup(int p){
    siz(p)=siz(l(p))+siz(r(p))+1;
}
int root;const int INF=INT_MAX;
void SplitByVal(int p,int &x,int &y,int val)
{
    if(!p){
        x=y=0; 
        return;
    }
    if(val(p)<=val){
        x=p,SplitByVal(r(p),r(p),y,val);
        //左子树整个都要被分到x,而右子树里有一些要被分到x,有一些要被分到y 
    }else{
        y=p,SplitByVal(l(p),x,l(p),val);
        //右子树整个都要被分到y,而左子树里有一些要被分到x,有一些要被分到y 
    }
    Pushup(p);//分裂后,p的左或右子树已经改变 
}
void Spread(int p){
    if(resv(p)){
        resv(p)=false;
        swap(l(p),r(p));
        resv(l(p))^=1,resv(r(p))^=1;
    }
}
void SplitBySize(int p,int &x,int &y,int val){
    if(!p){
        x=y=0;
        return;
    }
    Spread(p);
    if(siz(l(p))+1<=val){
        x=p,SplitBySize(r(p),r(p),y,val-siz(l(p))-1);
        //              |这里传下x树的最右边方便链接 
        //分界点在右边,并把左边完全包括进x,并继续寻找右边分界点 
    }else{
        y=p,SplitBySize(l(p),x,l(p),val);
        //                |这里传下y树的最左边方便链接 
        //分界点在左边,把右边完全包括进y,并继续寻找左边分界点 
    }
    Pushup(p);
}
//以上Split函数中,引用的意义是,修改从上面传下来的l,r,以链接一块块树(或者是最上面的答案)
//Split过程示意图: http://www.yhzq-blog.cc/wp-content/uploads/2021/10/merge.gif(是SplitByVal)
int Merge(int x,int y){//返回合并后的root 
    if(!x||!y) return x+y;//有一子树不存在,直接合并
    //为啥不检查val呢?因为x是原来左子树来的,y是右边子树来的,val问题不用考虑 
    if(dat(x)<dat(y)){//按照大根堆性质合并 (确定上下关系)
        Spread(y);
        l(y)=Merge(x,l(y));//注意我们不能把参数传反了 
        //注意val大小关系 
        Pushup(y);
        return y; 
    }else{
        Spread(x);
        r(x)=Merge(r(x),y);
        Pushup(x);
        return x;
        //同上 
    }
    // x是原来左树,y是右树,合并时左右关系不能乱 
}
void Insert(int val){
    int lt=0,rt=0;
    SplitByVal(root,lt,rt,val);
    root=Merge(Merge(lt,New(val)),rt);
}
void Resv(int l,int r){
    int lt=0,mt=0,rt=0;
    SplitBySize(root,lt,mt,l-1);
    SplitBySize(mt,mt,rt,r-l+1);
    resv(mt)^=1;
    root=Merge(Merge(lt,mt),rt);
}
void Output(int p){
    if(!p) return;
    Spread(p);
    Output(l(p));
    cout<<val(p)<<" ";
    Output(r(p));
    return;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        Insert(i);
    }
    for(int i=1;i<=m;i++){
        int l,r;cin>>l>>r;
        Resv(l,r);
    }
    Output(root);
    return 0;
}