[知识点]平衡树之Splay

时间:2022-09-04 16:14:22

// 此博文为迁移而来,写于2015年7月18日,不代表本人现在的观点与看法。原始地址:http://blog.sina.com.cn/s/blog_6022c4720102w6rg.html

1、前言
       这玩意儿真的搞了我好久,当然前一阵子一直都没有去管它,最近直接参照了YML(@YMDragon)的程序,感觉还是不错的,大概看得懂了,就是逻辑关系有点扯。好,废话不多说……
 
2、概念
       平衡树的全称为:平衡二叉搜索树,功能很强大,带来的后果就是代码非常复杂。首先大家应该都知道二叉搜索树是什么了,那么前面加一个平衡的含义在于什么?根据读入顺序 { 80,30,90,20,40,35,38 },我们先构造出一棵二叉搜索树,如图:
[知识点]平衡树之Splay
      显然,这棵树长得有点畸形,其根节点左儿子部分节点明显过多。然而这不仅仅是看起来不舒服的问题,但我们要在树上进行某项询问或是某项操作的时候,如果深度过大,将会明显影响到时间效率,可以举一个极端的例子——如果我们构造出的是一条链,那么时间复杂度可想而知。而平衡的含义就出现了,让这棵树长得更像一棵树!在操作的时候能够提高效率。写平衡树的方式有很多种,如:Splay,Treap,红黑树和AVL树等等。Splay相比之下功能强大,代码量较大,今天的重点就在Splay。
 
3、Let's Splay
       Splay的中文是伸展,并不清楚这有什么关系。Splay主要存在三种操作,下面一一介绍:
       1.Zig操作
      目标节点X是根节点的左(右)儿子,则将目标节点右(左)旋转至根节点。
[知识点]平衡树之Splay
       2.Zig-zig操作
      目标节点X不是根节点的子节点,且为其父节点的左(右)儿子,其父节点为其爷爷节点的左(右)儿子,则将目标节点X和其父节点先后进行右(左)旋。
[知识点]平衡树之Splay

3.Zig-zag操作

       目标节点X不是根节点的子节点,且为其父节点的左(右)儿子,其父节点为其爷爷节点的右(左)儿子,则将目标节点X进行右(左)旋,其父节点进行左(右)旋。[知识点]平衡树之Splay
       具体操作的话,旋转多为自下而上的递归旋转,直到把目标节点旋转至根节点。
4、应用
       平衡树存在一个共同作用也就是前文所提——平衡(废话呢)。但是今天的主题是Splay,之前也说过了它功能强大,那么强大在哪里?第一眼看题目你也许根本想不到要用Splay。现在我们来看一道神题:
[知识点]平衡树之Splay
      首先这是一道NOI2005的原题,BZOJ上没有给树数据范围,但是我想模拟的时间复杂度和空间复杂度一定是不能承受的。我也曾想到了链,但是感觉实现起来有点麻烦,那么这道题要用到的就是Splay。注意到,六大操作中,全部区间修改或区间询问,故我们先设当前操作对应区间为[x,y](INSERT是个例外,可以认为y=x+1),首先我们将x旋转至根,然后在将y旋转至根,仔细思考一下,[x,y]目前在树中是如何分布的?必然是在同一棵子树之中。那么这样就好处理了,插入时即可类似于在这棵子树中构造(同等于最开始的输入环节),删除时直接将一棵子树清空(清空的具体操作:权值记为0,作标记;可能会遇到一个问题,如果删除操作过多,可能会造成过多的空间资源的浪费,这里我们可以考虑开一个队列,以便以后新插入节点时可以直接使用已经被删除的空间),修改权值和翻转的操作有点类似于线段树;询问的话,提前对于每一棵子树进行维护即可。
 
代码:
----------------------------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
 
#define MAXN 500005
#define INF 1<<30
using namespace std;
 
struct Node
{
        int son[2],l,r,m,k,t1,t2,s,sum,fa;
};
 
Node tree[MAXN];
int m,n,root,a[MAXN];
char now[10];
queue Q;
 
void plus1(int now,int val)
{
        if (!now) return;
        tree[now].k=val,tree[now].t1=1,tree[now].sum=tree[now].k*tree[now].s;
        if (tree[now].k>0) tree[now].l=tree[now].r=tree[now].m=tree[now].sum; 
        else tree[now].l=tree[now].r=tree[now].m=tree[now].k;
}
 
void plus2(int now)
{
        if (!now) return;
        swap(tree[now].son[0],tree[now].son[1]),tree[now].t2^=1;
        swap(tree[now].l,tree[now].r);
}
 
void push(int now)
{
        if (!now) return;
        if (tree[now].t1) plus1(tree[now].son[0],tree[now].k),plus1(tree[now].son[1],tree[now].k),tree[now].t1=0;
        if (tree[now].t2) plus2(tree[now].son[0]),plus2(tree[now].son[1]),tree[now].t2=0;
}
 
void update(int now)
{
        if (!now) return;
        push(now);
        int lson=tree[now].son[0],rson=tree[now].son[1];
        tree[now].s=tree[lson].s+tree[rson].s+1;
        tree[now].sum=tree[lson].sum+tree[rson].sum+tree[now].k;
        tree[now].l=max(tree[lson].l,tree[lson].sum+tree[now].k+max(tree[rson].l,0));
        tree[now].r=max(tree[rson].r,tree[rson].sum+tree[now].k+max(tree[lson].r,0)); 
        tree[now].m=max(max(tree[lson].m,tree[rson].m),tree[now].k+max(tree[lson].r,0)+max(tree[rson].l,0));
}
 
void rotate(int now)
{
        int fa=tree[now].fa,gfa=tree[fa].fa,q=(tree[fa].son[1]==now),son=tree[now].son[q^1];
        if (gfa) tree[now].fa=gfa,tree[gfa].son[tree[gfa].son[1]==fa]=now;
        else tree[now].fa=0,root=now;
        tree[fa].son[q]=son; if (son) tree[son].fa=fa;
        tree[fa].fa=now,tree[now].son[q^1]=fa;
        update(fa),update(now);
//  让我来翻译一下这段话:
// 新建变量:我的爸爸,我爸爸的爸爸,“我是我爸的右儿子”判断,我的左(右)儿子;
// 如果我有爷爷,那么我的爸爸是我的爷爷,我的爷爷的儿子是我,左还是右取决于我爸爸是我爷爷的左还是右儿子;
// 如果我没爷爷,那么我爸爸也没有了,我就是你们的祖宗
// 我爸爸的儿子是我的儿子;如果我有儿子,那么我儿子的爸爸是我的爸爸
//  我爸爸的爸爸是我,我的左(右)儿子是我爸爸。
}
 
void splay(int now)
{
        int k=0;
        for (int x=now;x;x=tree[x].fa) { k++; a[k]=x; }
        for (int i=k;i>=1;i--) push(a[i]);
        while (tree[now].fa) rotate(now);
}
 
void build(int now,int l,int r)
{
        int mid=(l+r)>>1;
        if (l<mid) tree[now].son[0]=Q.front(),Q.pop(),build(tree[now].son[0],l,mid-1),tree[tree[now].son[0]].fa=now;
        scanf("%d",&tree[now].k);
        if (mid<r) tree[now].son[1]=Q.front(),Q.pop(),build(tree[now].son[1],mid+1,r),tree[tree[now].son[1]].fa=now;
        update(now);
}
        
int rank(int q)
{
        int now=root;
        while (now)
        {
                push(now);
                if (tree[tree[now].son[0]].s+1==q) return now;
                if (tree[tree[now].son[0]].s>=q) now=tree[now].son[0];
                else q-=tree[tree[now].son[0]].s+1,now=tree[now].son[1];
        }
        return 0;
}
 
void ins()
{
        int pos,tot,l,r,root; scanf("%d %d",&pos,&tot);
        l=rank(pos),r=rank(pos+1); splay(l),splay(r);
        root=Q.front(),Q.pop(),build(root,1,tot);
        if (l) tree[l].son[1]=root,tree[root].fa=l;
        else   tree[r].son[0]=root,tree[root].fa=r;
        update(l),update(r);
}
 
void DFS(int now)
{
        if (tree[now].son[0]) DFS(tree[now].son[0]);
        if (tree[now].son[1]) DFS(tree[now].son[1]);
        Q.push(now),memset(tree+now,0,sizeof(tree[now]));
}
 
void del()
{
        int pos,tot,l,r; scanf("%d %d",&pos,&tot);
        l=rank(pos-1),r=rank(pos+tot); splay(l),splay(r);
        if (l) DFS(tree[l].son[1]),tree[l].son[1]=0;
        else   DFS(tree[r].son[0]),tree[r].son[0]=0;
        update(l),update(r);
}
 
void makeSame()
{
        int pos,tot,c,l,r; scanf("%d %d %d",&pos,&tot,&c);
        l=rank(pos-1),r=rank(pos+tot); splay(l),splay(r);
        if (l) plus1(tree[l].son[1],c); else plus1(tree[r].son[0],c);
        update(l),update(r);
}
 
void reverse()
{
        int pos,tot,l,r; scanf("%d %d",&pos,&tot);
        l=rank(pos-1),r=rank(pos+tot); splay(l),splay(r);
        if (l) plus2(tree[l].son[1]); else if (r) plus2(tree[r].son[0]); else plus2(root);
        update(l),update(r);
}
 
int getSum()
{
        int pos,tot,l,r; scanf("%d %d",&pos,&tot);
        l=rank(pos-1),r=rank(pos+tot); splay(l),splay(r);
        if (l) return tree[tree[l].son[1]].sum;
        else return tree[tree[r].son[0]].sum;
}
        
int maxSum() { return tree[root].m; }
 
void init()
{
        freopen("1500.in","r",stdin);
        freopen("1500.out","w",stdout);
        scanf("%d %d",&n,&m);
        for (int i=1;i<=MAXN;i++) Q.push(i);
        tree[0].l=tree[0].r=tree[0].m=-INF;
        root=Q.front(),Q.pop(),build(root,1,n);
}
 
int main()
{
        init();
        for (int i=1;i<=m;i++)
        {
                scanf("%s",&now);
                if (now[0]=='I') ins();
                else if (now[0]=='D') del();
                else if (now[2]=='K') makeSame(); 
                else if (now[0]=='R') reverse();
                else if (now[0]=='G') printf("%d\n",getSum());
                else printf("%d\n",maxSum());
        }
        return 0;
}
---------------------------------------------------------------------------------------------------

[知识点]平衡树之Splay的更多相关文章

  1. P3391 【模板】文艺平衡树(Splay)新板子

    P3391 [模板]文艺平衡树(Splay) 题目背景 这是一道经典的Splay模板题——文艺平衡树. 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转 ...

  2. fhq&lowbar;treap &vert;&vert; BZOJ 3223&colon; Tyvj 1729 文艺平衡树 &vert;&vert; Luogu P3391 【模板】文艺平衡树(Splay)

    题面: [模板]文艺平衡树(Splay) 题解:无 代码: #include<cstdio> #include<cstring> #include<iostream&gt ...

  3. 【BZOJ】3223&colon; Tyvj 1729 文艺平衡树(splay)

    http://www.lydsy.com/JudgeOnline/problem.php?id=3223 默默的.. #include <cstdio> #include <cstr ...

  4. 平衡树(Splay):Splaytree POJ 3580 SuperMemo

    SuperMemo         Description Your friend, Jackson is invited to a TV show called SuperMemo in which ...

  5. bzoj3223 Tyvj 1729 文艺平衡树(Splay Tree&plus;区间翻转)

    3223: Tyvj 1729 文艺平衡树 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 2202  Solved: 1226[Submit][Sta ...

  6. BZOJ3224普通平衡树【Splay】

    3224: Tyvj 1728 普通平衡树 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 11751  Solved: 5013 Descriptio ...

  7. 【BZOJ3223】文艺平衡树(Splay)

    题面 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1 ...

  8. BZOJ 3224 - 普通平衡树 - &lbrack;Treap&rsqb;&lbrack;Splay&rsqb;

    题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=3224 Description 您需要写一种数据结构(可参考题目标题),来维护一些数,其中 ...

  9. P3369 【模板】普通平衡树(splay)

    P3369 [模板]普通平衡树 就是不用treap splay板子,好好背吧TAT #include<iostream> #include<cstdio> #include&l ...

随机推荐

  1. H264解码学习-2015&period;04&period;16

    今天看了不少,却感觉收获寥寥. 1.H264相关知识 因为RTP协议发过来的数据已经经过了H264编码,所以这边需要解码.补充一下H264的相关知识. 与以往的视频压缩标准相比,H.264 视频压缩标 ...

  2. 10-20日 &amp&semi;&amp&semi; 抽签问题

    Ants # include <cstdio> #include <algorithm> ; int L, n, x[MAX_N]; void solve() { ; ; i ...

  3. sleep&lpar;&rpar;

    经常看到线程中用sleep(),到底是什么用处,下面讲的比较通俗: 我们可能经常会用到 Thread.Sleep 函数来使线程挂起一段时间.那么你有没有正确的理解这个函数的用法呢?思考下面这两个问题: ...

  4. 关于SQL优化的一个小试例子

    原SQL: select ta.serialno,       ta.accepttime,       ta.subsnumber,       ta.subsname,       ta.cont ...

  5. 函数nvl&comma;nvl2&comma;nullif&comma;coalesce

    NVL: Converts a null value to an actual valueNVL2:If expr1 is not null, NVL2 returns expr2. If expr1 ...

  6. 理解Python闭包概念

    闭包并不只是一个python中的概念,在函数式编程语言中应用较为广泛.理解python中的闭包一方面是能够正确的使用闭包,另一方面可以好好体会和思考闭包的设计思想. 1.概念介绍 首先看一下维基上对闭 ...

  7. Android中的Context(一)

    Android中的Context(一) 在Android开发中,Context可以说是我们接触地非常多的一个概念了,也译作"上下文",但是这个上下文到底是什么却并不好理解. 通俗的 ...

  8. phpcms 路由配置

    这是一个由apache多站点配置引发的"血案",本以为是本地多站点配置的问题,结果找了半天没找到相关配置,最后还是问的大腿,同时也了解一些关于c盘hosts文件的映射作用以及使用 ...

  9. SQL Server 属性不匹配。存在属性&lpar;Directory&comma; Archive&rpar;,包括属性&lpar;0&rpar;,不包括属性&lpar;Archive&comma; Compressed&comma; Encrypted&rpar;

    问题:安装SQL SERVER 2008报错 “存在属性(Directory, Archive),包括属性(0),不包括属性(Archive, Compressed, Encrypted)” 解决办法 ...

  10. Android-PullToRefresh&lpar;一&rpar;

    先讲下这篇写啥东西,也就是这家伙(chrisbanes)写的一个上拉下拉刷新的Demo,连接https://github.com/fengcunhan/Android-PullToRefresh 东西 ...