欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

平衡树学习笔记

程序员文章站 2022-06-03 13:24:29
...

学习平衡树首先要学习一下二叉查找树

二叉查找树顾名思义，就是维护一棵支持查找的二叉树，在序列问题上，我们一般构造一棵二叉树，使其中序遍历等于原序列，这样我们的序列操作就转换成一系列在树上的操作，从而得到序列的答案，二叉查找树单次操作复杂度期望O(log⁡n)O(\log n)，最坏O(n)O(n)

但由于题目中数据可构造，一棵二叉查找树的深度达到最坏，单次操作复杂度就会达到O(n)O(n)，这是不能接受的，而平衡树是一种优化二叉查找树的复杂度的算法

平衡树基本都可以用这个模板检验你的基本操作是否掌握

平衡树算法种类多种多样，常见的有红黑树、AVL、替罪羊树、Treap、Splay、Leafy、fhqtreap

qwaszx：来学Leafy吧

伸展树 Splay

伸展树，多用于序列操作中，基本操作是将一个节点转到根，支持的操作众多且复杂度稳定，缺点是不可以可持久化

以下内容部分摘自OIwiki

rotate

旋转一个节点x到深度更小的位置

平衡树学习笔记

这张图表示了对于一个节点，我们怎么旋转它，使这棵树的中序遍历不变，并使这个节点去深度更小的位置

我们设要旋转的节点为xx，该节点的父亲为yy，son[y][0]表示yy的左儿子，son[y][1]表示yy的右儿子，kindkind表示xx是yy的哪一个儿子，具体旋转过程看代码吧

bool l_r(int x){
    return x==son[fa[x][1]];
}
void rotate(int x,int &goal){
    int y=fa[x],z=fa[y],kind=l_r(x);
    if (y==goal)goal=x;else son[z][l_r(y)]=x;
    son[y][kind]=son[x][kind^1];fa[son[x][kind^1]]=y;
    son[x][kind^1]=y;fa[y]=x;fa[x]=z;
    pushup(y);pushup(x);
}

Splay

将一个节点x转到根

当我们想要将一个节点转到根的时候，我们每次把一个节点转到父节点的位置，然后让父节点下来做自己的子节点就可以了，具体见下面的旋转操作

有个问题，一条链按这个做法进行下去的话，岂不是还是一条链

所以我们不能单纯这么瞎转，如果从该节点的父节点的父节点到这个点是一条链的话，我们先转父节点再转这个节点，如果不是，那旋转两次这个节点，这样我们转完以后深度就可以大大减小了

void splay(int x,int &goal){
    for (int y=fa[x];x!=goal;y=fa[x]){
        if (y!=goal)rotate(l_r(x)==l_r(y)?y:x,goal);
        rotate(x,goal);
    }
}

find

查询树上中序遍历的第x个节点的编号

对于序列操作来说这个操作非常重要，思路就是我们把这个排名x不断和当前节点的左子树大小进行比较，决定去左子树还是右子树里寻找

void find(int x){
    int now=rt;
    while (1){
        if (x<=siz[ls])now=ls;
        else{
            x-=siz[ls]+cnt[now];
            if (x<=0)return val[now];
            now=rs;
        }
    }
}

get_rank

对于值x，求在树的中序遍历的位置

和find相对，就是我们比较的时候和左儿子的值比较就好了

int get_rank(int x){
    int res=1,now=rt;
    while (1){
        if (x<val[now])now=ls;
        else{
            res+=siz[ls];
            if (x==val[now]){
                splay(now,rt);return res;
            }
            res+=cnt[now];now=rs;
        }
    }
}

pre & suf

找值x的前驱后继

这个操作在splay上可以说非常简短，先insert我们查询的值，这个值所在的节点被转到根，那么前驱就是左子树里最大的那个数，后继就是右子树里最小的那个数，然后delete掉就好了，根据二叉查找树的性质这非常好实现

代码提供的严格小于或大于的做法

//主函数里insert一个值x
int pre(){
    int now=son[rt][0];while (rs)now=rs;return now;
}
int suf(){
    int now=son[rt][1];while (ls)now=ls;return now;
}
//主函数里delete一个值x

insert

在某个位置插入一个值x

一般题目都是插在序列末尾，直接按着关键字检查走下去就好了，其实插在哪里都有办法实现，具体可以自行考虑一下，甚至你插入一个序列都可以做到

那么插入的思路就是你根据你的需要，从根节点开始，每走一步之前判断一下应该去左儿子还是右儿子，直到找到一个空位置或者一个含有x信息的节点计算贡献为止

void ins(int x){
    if (!rt){
        rt=++tot;cnt[rt]=siz[rt]=1;val[rt]=x;return;
    }
    int now=rt,fat=0;
    while (1){
        if (val[now]==x){
            cnt[now]++;siz[now]++;pushup(fat);splay(now,rt);return;
        }
        fat=now;now=son[now][x>val[now]];
        if (!now){
            now=++tot;cnt[now]=siz[now]=1;val[now]=x;
            son[fat][x>val[fat]]=now;fa[now]=fat;
            pushup(fat);splay(now,rt);return;
        }
    }
}

delete

删除一个节点/值

删除一个节点和值的变化其实不大，自己想一下就好

思路是先把要删的节点(或者存储你这个值的节点)，转到根，然后分类讨论一下：

没有儿子，那树里就只有这个点了，直接删除，并且标记树为空(root=0)

只有一个儿子，那这个儿子就是删掉这个节点以后的root

有两个儿子，那么让这个节点的前驱或者后继代替它就行

void del(int x){
    get_rank(x);
    if (cnt[rt]>1){
        cnt[rt]--;siz[rt]--;return;
    }
    int now=rt;
    if (!ls&&!rs){
        clear(now);rt=0;return;
    }
    if (ls&&rs){
        int y=pre();splay(y,rt);
        son[y][1]=rs;fa[rs]=y;
        clear(now);return;
    }
    if (ls){
        rt=ls;fa[rt]=0;clear(now);return;
    }
    if (rs){
        rt=rs;fa[rt]=0;clear(now);return;
    }
}

例题1：文艺平衡树

对序列支持区间求和和区间反转，题解我有另一篇文章了

例题2：【NOI2005】维护数列

比上一个题多了个区间删除和区间插入，这样一来split就是基本操作了，split是将一段连续的区间拎出来，具体就是把l−1l-1放到根，r+1r+1放到根的右儿子上，于是根的左儿子的右子树就是这个区间了，和上一个题完全一致，我们在把这个思路放到区间删除和区间插入上即可

此外，本题卡空间，但有一个同时序列最多5×1055\times 10^5的限制，我们可以回收节点，把删除过的节点重复利用，这一点可以用一个队列存储，然后把每次插入点的编号集合求出来建树就好了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define ls son[now][0]
#define rs son[now][1]
using namespace std;
void file(){
    freopen("read.in","r",stdin);
    freopen("write.out","w",stdout);
}
const int N=500010,inf=1e9;
inline int read(){
    int sym=0,res=0;char ch=getchar();
    while (!isdigit(ch))sym|=(ch=='-'),ch=getchar();
    while (isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return sym?-res:res;
}
int n,m,rt,a[N],id[N],tot;
int sum[N],ans[N],pre[N],suf[N],val[N];
int son[N][2],fa[N],tag[N],rev[N],siz[N];
char ch[N];
queue<int>q;
bool l_r(int x){
    return x==son[fa[x]][1];
}
void clear(int x){
    son[x][0]=son[x][1]=fa[x]=tag[x]=rev[x]=sum[x]=ans[x]=siz[x]=0;
}
int max_3(int a,int b,int c){
    return max(a,max(b,c));
}
void pushup(int now){
    if (!now)return;
    sum[now]=sum[ls]+sum[rs]+val[now];
    siz[now]=siz[ls]+siz[rs]+1;
    pre[now]=max(sum[ls]+val[now]+pre[rs],pre[ls]);
    suf[now]=max(sum[rs]+val[now]+suf[ls],suf[rs]);
    ans[now]=max_3(ans[ls],ans[rs],suf[ls]+val[now]+pre[rs]);
}
void lazy_change(int now,int t){
    tag[now]=1;val[now]=t;
    sum[now]=val[now]*siz[now];
    ans[now]=max(sum[now],val[now]);
    suf[now]=pre[now]=max(sum[now],0);
}
void lazy_rev(int now){
    rev[now]^=1;swap(ls,rs);swap(pre[now],suf[now]);
}
void pushdown(int now){
    if (tag[now]){
        if (ls)lazy_change(ls,val[now]);
        if (rs)lazy_change(rs,val[now]);
        rev[now]=tag[now]=0;
    }
    if (rev[now]){
        if (ls)lazy_rev(ls);
        if (rs)lazy_rev(rs);
        rev[now]=0;
    }
}
void build(int last,int l,int r){
    if (l>r)return;
    int mid=l+r>>1,now=id[mid];fa[now]=id[last];
    if (l==r){
        sum[now]=ans[now]=a[l];siz[now]=1;
        pre[now]=suf[now]=max(a[l],0);
    }
    build(mid,l,mid-1);build(mid,mid+1,r);
    val[now]=a[mid];son[fa[now]][mid>last]=now;
    pushup(now);
}
void rotate(int x,int &goal){
    int y=fa[x],z=fa[y],kind=l_r(x);
    if (y==goal)goal=x;else son[z][l_r(y)]=x;
    son[y][kind]=son[x][kind^1];fa[son[x][kind^1]]=y;
    son[x][kind^1]=y;fa[y]=x;fa[x]=z;
    pushup(y);pushup(x);
}
void splay(int x,int &goal){
    for (int y=fa[x];x!=goal;y=fa[x]){
        if (y!=goal)rotate(l_r(x)==l_r(y)?y:x,goal);
        rotate(x,goal);
    }
}
void cut(int now){
    if (ls)cut(ls);if (rs)cut(rs);q.push(now);clear(now);
}
int find(int x){//返回序列第x个数在树上的节点编号
    int now=rt;
    while (1){
        pushdown(now);
        if (x<=siz[ls])now=ls;
        else{
            x-=siz[ls]+1;if (x<=0)return now;now=rs;
        }
    }
}
void ins(int l,int r){
    int len=r-l+1;
    for (int i=1;i<=len;i++)a[i]=read();
    for (int i=1;i<=len;i++){
        if (!q.empty())id[i]=q.front(),q.pop();
        else id[i]=++tot;
    }
    build(0,1,len);int root=id[len+1>>1];
    int x=find(l),y=find(l+1);
    splay(x,rt);splay(y,son[x][1]);
    son[y][0]=root;fa[root]=y;
    pushup(y);pushup(x);
}
int split(int l,int r){
    int x=find(l-1),y=find(r+1);
    splay(x,rt);splay(y,son[x][1]);
    return son[y][0];
}
void del(int l,int r){
    int x=split(l,r),y=fa[x];
    cut(x);son[y][0]=0;
    pushup(y);pushup(fa[y]);
}
void rever(int l,int r){
    int now=split(l,r),y=fa[now];
    lazy_rev(now);pushup(y);pushup(fa[y]);
}
void change(int l,int r,int t){
    int now=split(l,r),y=fa[now];
    lazy_change(now,t);pushup(y);pushup(fa[y]);
}
int query(int l,int r){
    int x=split(l,r);return sum[x];
}
int main(){//file();
    n=read();m=read();rt=n+3>>1;
    ans[0]=a[1]=a[n+2]=-inf;//保证至少选一个数
    for (int i=2;i<=n+1;i++)a[i]=read();
    for (int i=1;i<=n+2;i++)id[i]=i;
    tot=n+2;build(0,1,tot);
    for (int i=1;i<=m;i++){
        scanf("%s",ch);
        if (ch[0]=='M'&&ch[2]=='X'){//max_sum
            printf("%d\n",ans[rt]);continue;
        }
        int l=read()+1,r=l+read()-1;
        if (ch[0]=='I'){//insert
            ins(l,r);
        }
        if (ch[0]=='D'){//delete
            del(l,r);
        }
        if (ch[0]=='R'){//reverse
            rever(l,r);
        }
        if (ch[0]=='G'){//get_sum
            printf("%d\n",query(l,r));
        }
        if (ch[0]=='M'&&ch[2]=='K'){//make_same
            int t=read();change(l,r,t);
        }
    }
    return 0;
}
相关标签： OI学习笔记 算法 数据结构

上一篇： PHP nl2br函数 将换行字符转成 <br>

下一篇： Springboot文件上传

推荐阅读