splay + 垃圾回收 知识点与例题的简要讲解

这篇具有很好参考价值的文章主要介绍了splay + 垃圾回收 知识点与例题的简要讲解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

splay 简要讲解

前置芝士:普通二叉树

splay tree是一个越处理越灵活的数据结构,通过splay(伸展)操作,使整棵树的单次查询时间复杂度接近于O(log n),整棵树的高度也接近于log n

根据上面的这句话,很明显能看出splay与普通二叉树的区别

普通二叉树经过多次处理后,很容易退化成链,单次查询的复杂度直升O(n),对于处理大型数据来说,这是绝对不能允许的

OI和ACM界也经常会有数据能使一个普通二叉树快速退化成链

例:  1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9

 

很明显,对于大型数据的处理来说,普通二叉树已经满足不了了

 

下面,我将会以例图来讲解中序遍历

splay + 垃圾回收 知识点与例题的简要讲解

这张图是我偷的,哈哈splay + 垃圾回收 知识点与例题的简要讲解

 

在这组数据中,数的根节点为6,整棵树的中序遍历为1,2,3,4,5,6,7,10,15,一个树的中序遍历为:左子树 + 根 + 右子树

很明显,这是递增的,当前这个splay树维护的是一个递增的序列

________________________________

操作

_______________

splay 有一个核心操作,就叫splay(伸展)

splay操作是依靠rotate去实现的

rotate(x) 点x向上翻转,分左旋和右旋,使其中序遍历不变,详情见代码

(关键是将这玩意得要图,要不不好讲清,如果代码看不懂的话,点这里,至OI wiki)

splay(x,k) 将点x翻转到点k的下方,每次添加一个数,就将其splay到根节点的下方(每次翻转的复杂度为log n),这样的话就能使整棵树的高度接近于log n

-------------------------------

 

在树中每个点的前继(succ)就是其在数组中的上一个点,后继(pred)就是下一个点,

 

kth 查询第k大的数,在树中每个点的前继就是其在数组中的上一个点,后继就是下一个点,所以在其中序遍历有序的前提下,递归判断每个子树的大小就行了

当然,p2042这道题的kth是第k个数,并不是第k大的数,因为这道题(p2042)维护的是一个区间

---------

build(or insert) 创建子树(或插入一个数)

如果我们要创建一段数字,插入到下标x的后面,想一下,是不是可以先在这组将要插入的数中建树,然后直接将这个树插到下标为x的右子树下,是不是就可以了?

同样,insert(x)也是同理,只不过是其子树的大小只有1

---------

detele操作,垃圾回收

每一次delete(x)后,tree[x]这个点为空,是不是浪费了?这很不符合我们环保的心理 (=_=) ,所以在每次我们delete操作后,将其节点下标保存下来,到build(or insert)的时候再使用,这样是不是就做到回收再利用了?

---------------

当我们想要处理区间 [x,y] 的时候,记住无论我们怎么splay,其中序遍历一定不变,再想想,在splay中一个点的前继和后继是什么

所以我们就可以现将x splay到根节点的下方,将y splay到x的下方,其 [x,y] 是不是就是点x及其右子树 和 点y及其左子树,然后就可以区间处理了

___________________________________________

 

记住,splay所维护的可以不是一个数组的val值,他可以是数组的下标

___________________________________________

一切尽在注释之中,这道题所维护的是每一个点的下标,并不是其点的val

例题:P2042 [NOI2005] 维护数列

 

splay+垃圾回收

#include"bits/stdc++.h"
using namespace std;
const int N = 500010,INF = 1e9;
#define inl inline
#define reg register
//#define ll long long
int n,m;
struct node
{
    int s[2],p,v;
    int rev,same,size,sum,ms,ls,rs;
    //翻转标记,相同标记,子树大小,区间和,最大子段和,最大前缀和,最大后缀和
    inl void init(int _v,int _p) //预处理
    {
        s[0] = s[1] = 0,p = _p,v = _v;
        rev = same = 0;
        size = 1,sum = ms =v;
        ls = rs = max(v,0);
    }
}tr[N];
int root;
int nodes[N],tt;//垃圾回收数组,tt为其大小
int w[N];
inl void pushup(int x) //向上传递
{
    auto &u = tr[x],&l = tr[u.s[0]],&r = tr[u.s[1]];
    u.size = l.size + r.size + 1;
    u.sum = l.sum + r.sum + u.v;
    u.ls = max(l.ls,l.sum + u.v + r.ls);
    u.rs = max(r.rs,r.sum + u.v + l.rs);
    u.ms = max(max(l.ms,r.ms),l.rs + u.v + r.ls);
  //处理各个数据
} inl
void pushdown(int x) //向下传递 { auto &u = tr[x],&l = tr[u.s[0]], &r = tr[u.s[1]]; if(u.same) //若有相同标记,则翻转标记就并不需要 { u.same = u.rev = 0; if(u.s[0]) l.same = 1,l.v = u.v,l.sum = l.v * l.size; if(u.s[1]) r.same = 1,r.v = u.v,r.sum = r.v * r.size;
     
if(u.v > 0) { if(u.s[0]) l.ms = l.ls = l.rs = l.sum; if(u.s[1]) r.ms = r.ls = r.rs = r.sum; }else { if(u.s[0]) l.ms = l.v,l.ls = l.rs = 0; if(u.s[1]) r.ms = r.v,r.ls = r.rs = 0; }
     //左右子树数据处理 }
else if(u.rev) { u.rev = 0,l.rev ^= 1,r.rev ^= 1; swap(l.ls,l.rs),swap(r.ls,r.rs); swap(l.s[0],l.s[1]),swap(r.s[0],r.s[1]);
     //翻转 } } inl
void rotate(int x) { int y = tr[x].p,z = tr[y].p; int k = tr[y].s[1] == x; tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z; tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y; tr[x].s[k ^ 1] = y,tr[y].p = x; pushup(y),pushup(x);
  //向上旋转 } inl
void splay(int x,int k) { while (tr[x].p != k) { int y = tr[x].p, z = tr[y].p; if (z != k) if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x); else rotate(y); rotate(x); } if (!k) root = x; }
//伸展 inl
int get_k(int k) //查询第k个数 { int u = root; while (u) { pushdown(u); if (tr[tr[u].s[0]].size >= k) u = tr[u].s[0]; else if (tr[tr[u].s[0]].size + 1 == k) return u; else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1]; } } inl int build(int l,int r,int p) //建造子树 { int mid = l + r >> 1; int u = nodes[tt -- ]; tr[u].init(w[mid], p); if (l < mid) tr[u].s[0] = build(l, mid - 1, u); if (mid < r) tr[u].s[1] = build(mid + 1, r, u); pushup(u); return u; } inl void dfs(int u) //delete 操作 { if(tr[u].s[0]) dfs(tr[u].s[0]); if(tr[u].s[1]) dfs(tr[u].s[1]); nodes[ ++ tt] = u; //垃圾回收
   }
int main(void) { for(int i = 1;i < N;i ++) nodes[ ++ tt] = i; //nit [1,n] -> 垃圾回收站 scanf("%d%d",&n,&m); tr[0].ms = -INF; w[0] = w[n+1] = -INF; for(int i = 1;i <= n;i ++) scanf("%d",&w[i]); root = build(0,n + 1,0); char op[20]; while (m -- ) { scanf("%s", op); if (!strcmp(op, "INSERT")) { int posi, tot; scanf("%d%d", &posi, &tot); for (int i = 0; i < tot; i ++ ) scanf("%d", &w[i]); int l = get_k(posi + 1), r = get_k(posi + 2); splay(l, 0), splay(r, l); int u = build(0, tot - 1, r); tr[r].s[0] = u; pushup(r), pushup(l); } else if (!strcmp(op, "DELETE")) { int posi, tot; scanf("%d%d", &posi, &tot); int l = get_k(posi), r = get_k(posi + tot + 1); splay(l, 0), splay(r, l); dfs(tr[r].s[0]); tr[r].s[0] = 0; pushup(r), pushup(l); } else if (!strcmp(op, "MAKE-SAME")) { int posi, tot, c; scanf("%d%d%d", &posi, &tot, &c); int l = get_k(posi), r = get_k(posi + tot + 1); splay(l, 0), splay(r, l); auto& son = tr[tr[r].s[0]]; son.same = 1, son.v = c, son.sum = c * son.size; if (c > 0) son.ms = son.ls = son.rs = son.sum; else son.ms = c, son.ls = son.rs = 0; pushup(r), pushup(l); } else if (!strcmp(op, "REVERSE")) { int posi, tot; scanf("%d%d", &posi, &tot); int l = get_k(posi), r = get_k(posi + tot + 1); splay(l, 0), splay(r, l); auto& son = tr[tr[r].s[0]]; son.rev ^= 1; swap(son.ls, son.rs); swap(son.s[0], son.s[1]); pushup(r), pushup(l); } else if (!strcmp(op, "GET-SUM")) { int posi, tot; scanf("%d%d", &posi, &tot); int l = get_k(posi), r = get_k(posi + tot + 1); splay(l, 0), splay(r, l); printf("%d\n", tr[tr[r].s[0]].sum); } else printf("%d\n", tr[root].ms); //MAX-SUM } return 0; } /*
输入样例 1
9 8 2 -6 3 5 1 -5 -3 6 3 GET-SUM 5 4 MAX-SUM INSERT 8 3 -5 7 2 DELETE 12 1 MAKE-SAME 3 3 2 REVERSE 3 6 GET-SUM 5 4 MAX-SUM */

可能对于刚刚学习splay的人来说,这道题明显有点难了

点这里,来做P3224 [HNOI2012] 永无乡

 答案我放在这里了,这道题维护的是数字的val

 这道题用了并查集的启发式合并,说白了就是在合并操作中将较小的集合合并到较大的集合中,以减少所浪费的时间

为什么要用启发式合并?合并操作不是O(1)吗?

不不不,这道题是并查集维护每个splay,splay的合并是O(log n),并不是O(1),需要启发式合并,来过毒瘤数据

#include"bits/stdc++.h"
using namespace std;
const int N = 500010;
#define inl inline
#define reg register
//#define ll long long
int n,m;
struct node
{
    int s[2],p,v,id;
    int size;
    inl void init(int _v,int _id, int _p)
    {
        v = _v,id = _id,p = _p;
        size = 1;
    }
}tr[N];
int root[N],idx;
int p[N];
inl void read()
{
    std::cin.tie(nullptr);
}
inl int Find(int x)
{
    return p[x] != x ? p[x] = Find(p[x]) : p[x];
}

inl void pushup(int x)
{
    tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
    
}

inl void rotate(int x)
{   //y为x的父节点,z为x的爷节点
    int y = tr[x].p,z = tr[y].p;
    int k = tr[y].s[1] == x;//k为(x是否为y的右节点)//即k为(x节点的左右儿子)
    tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
    //z节点的y儿子改为x儿子,x节点的父节点改为z
    
    tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y;
    //处理原x的右儿子,以及原x右节点的parent
    tr[x].s[k ^ 1] = y,tr[y].p = x;
    //更改原x的非y儿子节点(另一个儿子),更改y的父节点为x
    pushup(y),pushup(x);
    //update size
    //x上移1个单位
}
inl void splay(int x,int k,int b)//将集合b的splay中x节点转到k节点的下面while(tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if(z != k)
            if((tr[y].s[1] == x) ^ (tr[z].s[1] == y))    rotate(x);
            else    rotate(y);
            //双旋 
            rotate(x);
    }
    //k==0 
    if(!k)    root[b] = x;//集合b的根节点为x
}
inl void insert(int v,int id,int b)//将编号为id,重要度为v 的节点加入集合b的splay中
{
    reg int u = root[b],p = 0;
    while(u)    p = u,u = tr[u].s[v > tr[u].v];
    u = ++idx;
    if(p) tr[p].s[v > tr[p].v] = u;
    tr[u].init(v,id,p);
    splay(u,0,b);
}
inl void dfs(int u,int b)//将根节点u所在splay中的每一个点插入到集合b的splay中
{
    if(tr[u].s[0])    dfs(tr[u].s[0],b);
    if(tr[u].s[1])    dfs(tr[u].s[1],b);
    insert(tr[u].v,tr[u].id,b);//查询集合b的splay中重要度第k小的节点编号
}
inl int get_k(int k,int b)//²éѯ¼¯ºÏbµÄSplayÖÐÖØÒª¶ÈµÚkСµÄ½Úµã±àºÅ 
{
    int u = root[b];
    while(u)
    {
        if(tr[tr[u].s[0]].size >= k)    u = tr[u].s[0];
        else if(tr[tr[u].s[0]].size + 1 == k)    return tr[u].id;
        else k -= tr[tr[u].s[0]].size + 1,u = tr[u].s[1];
    }
    return -1;
}
int main(void)
{
    read();
    scanf("%d%d",&n,&m);
    //init Find-Union and root
    for(int i = 1;i <= n;i ++)
    {
        p[i] = root[i] = i;
        int v;
        scanf("%d",&v);
        tr[i].init(v,i,0);/init 每个集合的root
    }
    idx = n;//前n个下标个n个splay的根节点用
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        a = Find(a),b = Find(b);
        if(a != b)//如果两个岛不在一个集合中,需要合并
        {
/*
tr[root[a]].size > tr[root[b]].size
保证集合a中元素的个数 <= 集合b中元素的个数
启发式合并
保证较小的集合加入较大的集合
*/ if(tr[root[a]].size > tr[root[b]].size) swap(a,b);//保证集合a中的元素个数 <= 集合b中的元素个数 dfs(root[a],b);//将集合a的splay里的每一个点插入到集合b的splay里面 p[a] = b;//将集合a合并入集合b } } reg int q; scanf("%d",&q); while(q --) { char op[2]; int a,b; scanf("%s%d%d",op,&a,&b); if(*op == 'B')//add edge { a = Find(a),b = Find(b); if(a != b)//Union 如果两个岛不在一个集合里,需要合并 { if(tr[root[a]].size > tr[root[b]].size) swap(a,b); dfs(root[a],b); p[a] = b; } }else { a = Find(a);//集合中不足b个数,输出"-1" if(tr[root[a]].size < b) puts("-1"); else printf("%d\n",get_k(b,a));//否则查询第k小数 } } return 0; }

好了,就到这里了

数据结构不能单纯靠记忆,一定要理解,记住啊,一定要靠理解,记忆只不过是帮助你在考场上调试出来的东西,并不是其主导的因素文章来源地址https://www.toymoban.com/news/detail-711397.html

到了这里,关于splay + 垃圾回收 知识点与例题的简要讲解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • MATLAB知识点:for循环的七道经典例题

     ​讲解视频:可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。​ MATLAB教程新手入门篇(数学建模清风主讲,适合零基础同学观看)_哔哩哔哩_bilibili 节选自​第4章:MATLAB程序流程控制 (1)不使用sum函数,计算行向量x中所有元素的和。   在这个示例中,

    2024年04月13日
    浏览(44)
  • 微机原理 || 8253接口芯片知识点+4道经典例题+手写解题过程

      【例1】 :  设825 3 端口地址为3 00H~303H, 要求计数器2工作在方式5,二进制计数, CLK2=2MHz , OUT2=1KHz。 试按上述要求完成825 3 的 初始化 。   【例2】: 选择计数器 0 工作于方式 3 ,计数初值为 1234 ,十进制计数方式;计数器 2 工作于方式 2 ,计数初值为 61H ,采用二进制

    2024年02月10日
    浏览(54)
  • 【计算机网络】第五章传输层知识点及经典例题汇总

    1、从通信和信息处理的角度看,传输层向它上面的应用层提供通信服务,它属于面向通信部分的最高层,同时也是用户功能中的最低层 2、此层包含TCP和UDP协议。TCP 传送的数据单位协议是 TCP 报文段(segment),UDP 传送的数据单位协议是 UDP 报文或用户数据报。 3、IP数据报要经过

    2024年02月04日
    浏览(54)
  • kafka知识点全方位讲解

    Apache Kafka是一个开源消息系统,由Scala写成。是由Apache软件基金会开发的一个开源消息系统项目。 Kafka最初是由LinkedIn开发,并于2011年初开源。2012年10月从Apache Incubator毕业。该项目的目标是为处理实时数据提供一个统一、高通量、低等待的平台。 Kafka是一个分布式消息队列:

    2023年04月25日
    浏览(44)
  • Java实现连接数据库验证登录和注册(附详细知识点讲解)

    学完Java基础后,一般会做个项目练手(上一篇博客有讲到 Java在线聊天室课程设计 ) 当中肯定会涉及到 登录验证 ,但没学过数据库 😅,不知道如何操作;只能把用户账户密码预存在一个txt文本当中,然后通过IO流读取验证 ⭐ 最后去搜相应的资料和网课进行学习,现在问题

    2024年02月02日
    浏览(49)
  • pyqt5控件自适应窗口知识点汇总(超详细讲解,持续更新中…)

    本文涉及:Windows操作系统,Python,PyQt5,Qt Designer,PyCharm 目录 一、自适应原理  二、基础布局示例 三、高级布局示例:布局嵌套布局 四、其它特殊控件自适应补充 1. tableWidget  2. 未完待续… 五、结语         自适应其实很简单,只要搞懂原理,你就能随心所欲地去布置你

    2024年02月02日
    浏览(47)
  • 【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解

      本篇博客 (上篇) 先带大家学习 递归方式 进行三种遍历, 而在后续的 (下篇) 中将为大家详细讲解非递归的三种遍历方式。 目录 1、二叉树 2、二叉树的递归遍历 2.1、先序遍历 2.2、中序遍历 2.3、后序遍历  二叉树(Binary tree)是树形结构的一个重要类型。许多实际问

    2024年02月08日
    浏览(44)
  • 耗时一个月!期末熬夜复习整理 | 计算机网络(谢希仁第七版)大合集【知识点+大量习题讲解】

    期末计网满绩计划 教材:计算机网络(第七版)谢希仁版 第一章概述 第二章物理层 第三章数据链路层 第四章网络层 第五章运输层 第六章应用层 第七章网络安全 小生凡一,期待你的关注。

    2024年02月11日
    浏览(48)
  • 【python】python的垃圾回收机制(详细讲解)

    👉博__主👈:米码收割机 👉技__能👈:C++/Python语言 👉公众号👈:测试开发自动化【获取源码+商业合作】 👉荣__誉👈:阿里云博客专家博主、51CTO技术博主 👉专__注👈:专注主流机器人、人工智能等相关领域的开发、测试技术。 Python的垃圾回收机制主要基于 引用计数

    2024年02月12日
    浏览(64)
  • 深入理解JVM——垃圾回收与内存分配机制详细讲解

    所谓垃圾回收,也就是要回收已经“死了”的对象。 那我们如何判断哪些对象“存活”,哪些已经“死去”呢? 给对象中添加一个引用计数器,每当有一个地方引用它时,计数器就加一;当引用失效时,计数器就减1;任何时刻计数器为0的对象就是不可能再被使用的。 但是

    2024年02月12日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包