JZTXT

平衡树

发布时间 2023-06-04 22:43:24作者: TKXZ133

FHQTreap

FHQTreap是一种平衡树，它通过分裂和合并两种操作来维持树的平衡，而不需要旋转。

其每个节点除了有权值，还有一个随机的优先级，用来决定合并的方案。单次操作的复杂度是\(O(\log n)\)。

可以方便的实现很多区间功能，比如进行区间翻转、区间加法，维护区间最值、区间和等。

也可以很方便地实现可持久化，因为不需要修改父子关系。

其他应用：

  • 动态凸包，可以支持点的插入和删除，以及查询凸包上的点。
  • 动态中位数，可以支持元素的插入和删除，以及查询中位数或任意顺序统计量。

FHQTreap通过随机权值保证单次操作期望复杂度为\(O(\log n)\)。这是因为在随机数均匀分布的情况下，其期望树高为$ 2\ln n\ \approx 1.39\log_2n\(，而单次合并分类操作是沿着树的高度进行递归的，所以每次分裂或合并的时间复杂度是\)O(\log n) \(的。而FHQTreap的其他操作均可以通过常数次合并分裂操作实现，故FHQTreap的总时间复杂度是\) O(\log n)$。但常数较大，通常有\(4\sim 5\)倍常数。

普通平衡树

普通平衡树

普通平衡树

即用平衡树对一个集合进行维护，支持插入，删除，求前驱，后继，查询某数的排名，查询排名对应的数等。

mt19937 rng(random_device{}());

struct FHQn{
    int ch[2];
    int val,key,siz;
};

struct FHQ{
    FHQn a[N];
    int tot,rt,x,y,z,ans;
    void push_up(int p){
        a[p].siz=a[a[p].ch[0]].siz+a[a[p].ch[1]].siz+1;
    }
    int built(int k){
        int p=++tot;
        a[p]={{0,0},k,rng(),1};
        return p;
    }
    int merge(int p,int q){
        if(!p||!q) return p+q;
        if(a[p].key<a[q].key){
            a[p].ch[1]=merge(a[p].ch[1],q);
            push_up(p);return p;
        }
        else{
            a[q].ch[0]=merge(p,a[q].ch[0]);
            push_up(q);return q;
        }
    }
    void split(int p,int k,int &l,int &r){
        if(!p){l=r=0;return ;}
        if(a[p].val<=k){
            l=p;split(a[p].ch[1],k,a[p].ch[1],r);
        }
        else{
            r=p;split(a[p].ch[0],k,l,a[p].ch[0]);
        }
        push_up(p);
    }
    int kth(int p,int k){
        while(true){
            if(a[a[p].ch[0]].siz>=k) p=a[p].ch[0];
            else if(a[a[p].ch[0]].siz+1==k) return p;
            else k-=a[a[p].ch[0]].siz+1,p=a[p].ch[1];
        }
    }
    void insert(int k){
        split(rt,k,x,y);
        rt=merge(merge(x,built(k)),y);
    }
    void del(int k){
        split(rt,k,x,z);split(x,k-1,x,y);
        y=merge(a[y].ch[0],a[y].ch[1]);
        rt=merge(merge(x,y),z);
    }
    int find_kth(int k){
        split(rt,k-1,x,y);
        ans=a[x].siz+1;
        rt=merge(x,y);
        return ans;
    }
    int find_num(int k){
        return a[kth(rt,k)].val;
    }
    int pre(int k){
        split(rt,k-1,x,y);
        ans=a[kth(x,a[x].siz)].val;
        rt=merge(x,y);
        return ans;
    }
    int nxt(int k){
        split(rt,k,x,y);
        ans=a[kth(y,1)].val;
        rt=merge(x,y);
        return ans;
    }
}tree;

序列平衡树

即用平衡树对序列进行维护，支持区间最值，区间翻转，区间加，区间求和等区间操作。

使用FHQTreap 可以方便的对序列进行操作，只需要将分裂方式从按值分裂改为按大小分裂即可。

当然，为了保证时间复杂度，需要配合懒标记和下放懒标记的函数使用。

void split(int p,int k,int &l,int &r){
    if(p) push_down(p);
    else{l=r=0;return ;}
    if(a[a[p].ch[0]].siz<k){
        l=p;split(a[p].ch[1],k-a[a[p].ch[0]].siz-1,a[p].ch[1],r);
    }
    else{
        r=p;split(a[p].ch[0],k,l,a[p].ch[0]);
    }
    push_up(p);
}

要进行对\([l,r]\)的区间操作时只需要将树分裂成三颗，对中间的树进行操作，最后合并三颗树即可。

void operate(int l,int r,int k){
    int x,y,z;
    split(rt,r,x,z);
    split(x,l-1,x,y);
    operate_t(y,k);
    rt=merge(merge(x,y),z);
}

懒标记的使用基于题目决定。值得注意的是，在执行任何递归子树的操作前都要下放懒标记。

int merge(int p,int q){
    if(!p||!q) return p+q;
    if(a[p].key<a[q].key){
        push_down(p);a[p].ch[1]=merge(a[p].ch[1],q);
        push_up(p);return p;
    }
    else{
        push_down(q);a[q].ch[0]=merge(p,a[q].ch[0]);
        push_up(q);return q;
    }
}

而下放懒标记的方法也很简单，跟线段树差不多。

void push_down(int p){
    if(a[p].t){
        if(a[p].ch[0]) operate_t(a[p].ch[0]);
        if(a[p].ch[1]) operate_t(a[p].ch[1]);
        a[p].t=0;
    }
}

而operatr_t()函数以及push_up()函数等根据题目来实现。

  • 例：

维护区间的最大子列和（必须至少选一个数），区间和，区间翻转，区间修改：

struct FHQn{
    int ch[2];
    int val,siz,key;
    int t1,t2,t3;
    int sum,maxl,maxr,maxs;
};

void push_up(int p){
    a[p].sum=a[a[p].ch[0]].sum+a[a[p].ch[1]].sum+a[p].val;
    a[p].siz=a[a[p].ch[0]].siz+a[a[p].ch[1]].siz+1;
    a[p].maxl=max({a[a[p].ch[0]].maxl,a[a[p].ch[0]].sum+a[a[p].ch[1]].maxl,0});
    a[p].maxr=max({a[a[p].ch[1]].maxr,a[a[p].ch[1]].sum+a[a[p].ch[0]].maxr,0});
    a[p].maxs=max(a[p].val,a[a[p].ch[0]].maxr+a[p].val+a[a[p].ch[1]].maxl);
    if(a[p].ch[0]) a[p].maxs=max(a[p].maxs,a[a[p].ch[0]].maxs);
    if(a[p].ch[1]) a[p].maxs=max(a[p].maxs,a[a[p].ch[1]].maxs);
}

void reverse_t(int p){
    if(!p) return ;
    a[p].t1^=1;
    swap(a[p].ch[0],a[p].ch[1]);
    swap(a[p].maxl,a[p].maxr);
}

void change_t(int p,int k){
    if(!p) return ;
    a[p].val=a[p].t3=k;a[p].t2=1;
    a[p].sum=a[p].siz*k;
    a[p].maxs=max(a[p].sum,k);
    a[p].maxl=a[p].maxr=max(a[p].sum,0);
}

void push_down(int p){
    if(!p) return ;
    if(a[p].t1){
        reverse_t(a[p].ch[0]);
        reverse_t(a[p].ch[1]);
        a[p].t1=0;
    }
    if(a[p].t2){
        change_t(a[p].ch[0],a[p].t3);
        change_t(a[p].ch[1],a[p].t3);
        a[p].t2=a[p].t3=0;
    }
}

平衡树的应用

  • 如果我们将上文的维护集合的平衡树和维护序列的平衡树合并，会怎么样？

树套树！

树套树可以求区间前驱，区间后继，区间排名，区间查询某数的排名，区间查询排名对应的数等，当然，也支持单点修改，区间最值等操作。

树套树有很多种，如线段树套线段树，平衡树套线段树，线段树套平衡树，树状数组套权值线段树，分块套树状数组等。

树套树中存在外层树和内层树的概念，外层树包括线段树，平衡树，树状数组，分块等，内层树包括权值线段树，平衡树，树状数组，STL的set等。所以组合起来至少有16种树套树。

当然，不同的树套树对于不同的操作有着不同的复杂度：

线段树套权值线段树线段树：均为\(O(\log^2n)\)。

线段树套平衡树：除了查询区间内排名对应的数为\(O(\log^3n)\)，其他均为\(O(\log^2n)\)。

树状数组套权值线段树：均为\(O(\log^2n)\)。

大部分复杂度为\(O(\log^2 n)\)的原因是进行操作时，操作在外层树被划分成了\(O(\log n)\)个区间，而对于每个区间，内层树都进行了\(O(\log n)\)次操作，所以合起来时\(O(\log^2n)\)的。

当然，树套树的码量相对较大，正常写法在\(4.5kb\)左右。

  • 维护奇怪的东西

序列平衡树可以维护序列，而DP 正是基于序列实现的，所以用平衡树可以动态的维护DP数组。

但往往DP 与平衡树结合的题目是用平衡树动态维护斜率优化的凸包。

于是这又让平衡树和计算几何扯上了关系。

类似维护DP，平衡树也可以动态维护哈希数组。