经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C++ » 查看文章
splay + 垃圾回收 知识点与例题的简要讲解
来源：cnblogs　　作者：Vect0r_lemon　　时间：2023/10/25 10:12:52　　对本文有异议

splay 简要讲解

前置芝士:普通二叉树

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

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

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

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

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

 

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

 

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

这张图是我偷的,哈哈

 

在这组数据中,数的根节点为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] 维护数列

 

  1. splay+垃圾回收
  3. #include"bits/stdc++.h"
  4. using namespace std;
  5. const int N = 500010,INF = 1e9;
  6. #define inl inline
  7. #define reg register
  8. //#define ll long long
  9. int n,m;
  10. struct node
  11. {
  12.     int s[2],p,v;
  13.     int rev,same,size,sum,ms,ls,rs;
  14.     //翻转标记,相同标记,子树大小,区间和,最大子段和,最大前缀和,最大后缀和
  15.     inl void init(int _v,int _p) //预处理
  16.     {
  17.         s[0] = s[1] = 0,p = _p,v = _v;
  18.         rev = same = 0;
  19.         size = 1,sum = ms =v;
  20.         ls = rs = max(v,0);
  21.     }
  22. }tr[N];
  23. int root;
  24. int nodes[N],tt;//垃圾回收数组,tt为其大小
  25. int w[N];
  26. inl void pushup(int x) //向上传递
  27. {
  28.     auto &u = tr[x],&l = tr[u.s[0]],&r = tr[u.s[1]];
  29.     u.size = l.size + r.size + 1;
  30.     u.sum = l.sum + r.sum + u.v;
  31.     u.ls = max(l.ls,l.sum + u.v + r.ls);
  32.     u.rs = max(r.rs,r.sum + u.v + l.rs);
  33.     u.ms = max(max(l.ms,r.ms),l.rs + u.v + r.ls);
  34. 　　//处理各个数据
    }
  35. inl void pushdown(int x) //向下传递
  36. {
  37.     auto &u = tr[x],&l = tr[u.s[0]], &r = tr[u.s[1]];
  38.     if(u.same) //若有相同标记,则翻转标记就并不需要
  39.     {
  40.         u.same = u.rev = 0;
  41.         if(u.s[0])  l.same = 1,l.v = u.v,l.sum = l.v * l.size; 
  42.         if(u.s[1])  r.same = 1,r.v = u.v,r.sum = r.v * r.size;
    　　　　　
  43.         if(u.v > 0)
  44.         {
  45.             if(u.s[0])  l.ms = l.ls = l.rs = l.sum;
  46.             if(u.s[1])  r.ms = r.ls = r.rs = r.sum;
  47.         }else
  48.         {
  49.             if(u.s[0])  l.ms = l.v,l.ls = l.rs = 0;
  50.             if(u.s[1])  r.ms = r.v,r.ls = r.rs = 0;
  51.         }
    　　　　　//左右子树数据处理
  52.     }else
  53.     if(u.rev)
  54.     {
  55.         u.rev = 0,l.rev ^= 1,r.rev ^= 1;
  56.         swap(l.ls,l.rs),swap(r.ls,r.rs);
  57.         swap(l.s[0],l.s[1]),swap(r.s[0],r.s[1]);
    　　　　　//翻转
  58.     }
  59. }
  60. inl void rotate(int x)
  61. {
  62.     int y = tr[x].p,z = tr[y].p;
  63.     int k = tr[y].s[1] == x;
  64.     tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
  65.     tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y;
  66.     tr[x].s[k ^ 1] = y,tr[y].p = x;
  67.     pushup(y),pushup(x);
    　　//向上旋转
  68. }
  69. inl void splay(int x,int k)
  70. {
  71.     while (tr[x].p != k)
  72.     {
  73.         int y = tr[x].p, z = tr[y].p;
  74.         if (z != k)
  75.             if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
  76.             else rotate(y);
  77.         rotate(x);
  78.     }
  79.     if (!k) root = x;
  80. }
    //伸展
  81. inl int get_k(int k) //查询第k个数
  82. {
  83.     int u = root;
  84.     while (u)
  85.     {
  86.         pushdown(u);
  87.         if (tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
  88.         else if (tr[tr[u].s[0]].size + 1 == k) return u;
  89.         else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
  90.     }
  91. }
  92. inl int build(int l,int r,int p) //建造子树
  93. {
  94.     int mid = l + r >> 1;
  95.     int u = nodes[tt -- ];
  96.     tr[u].init(w[mid], p);
  97.     if (l < mid) tr[u].s[0] = build(l, mid - 1, u);
  98.     if (mid < r) tr[u].s[1] = build(mid + 1, r, u);
  99.     pushup(u);
  100.     return u;
  101. }
  102. inl void dfs(int u) //delete 操作
  103. {
  104.     if(tr[u].s[0])  dfs(tr[u].s[0]);
  105.     if(tr[u].s[1])  dfs(tr[u].s[1]);
  106.     nodes[ ++ tt] = u; //垃圾回收
    　　
  107. }
  108. int main(void)
  109. {
  110.     for(int i = 1;i < N;i ++) nodes[ ++ tt] = i;
  111.     //nit [1,n] -> 垃圾回收站
  112.     scanf("%d%d",&n,&m);
  113.     tr[0].ms = -INF;
  114.     w[0] = w[n+1] = -INF;
  115.     for(int i = 1;i <= n;i ++)  scanf("%d",&w[i]);
  116.     root = build(0,n + 1,0);
  117.     char op[20];
  119.     while (m -- )
  120.     {
  122.         scanf("%s", op);
  123.         if (!strcmp(op, "INSERT"))
  124.         {
  125.             int posi, tot;
  126.             scanf("%d%d", &posi, &tot);
  127.             for (int i = 0; i < tot; i ++ ) scanf("%d", &w[i]);
  128.             int l = get_k(posi + 1), r = get_k(posi + 2);
  129.             splay(l, 0), splay(r, l);
  130.             int u = build(0, tot - 1, r);
  131.             tr[r].s[0] = u;
  132.             pushup(r), pushup(l);
  133.         }
  134.         else if (!strcmp(op, "DELETE"))
  135.         {
  136.             int posi, tot;
  137.             scanf("%d%d", &posi, &tot);
  138.             int l = get_k(posi), r = get_k(posi + tot + 1);
  139.             splay(l, 0), splay(r, l);
  140.             dfs(tr[r].s[0]);
  141.             tr[r].s[0] = 0;
  142.             pushup(r), pushup(l);
  143.         }
  144.         else if (!strcmp(op, "MAKE-SAME"))
  145.         {
  146.             int posi, tot, c;
  147.             scanf("%d%d%d", &posi, &tot, &c);
  148.             int l = get_k(posi), r = get_k(posi + tot + 1);
  149.             splay(l, 0), splay(r, l);
  150.             auto& son = tr[tr[r].s[0]];
  151.             son.same = 1, son.v = c, son.sum = c * son.size;
  152.             if (c > 0) son.ms = son.ls = son.rs = son.sum;
  153.             else son.ms = c, son.ls = son.rs = 0;
  154.             pushup(r), pushup(l);
  155.         }
  156.         else if (!strcmp(op, "REVERSE"))
  157.         {
  158.             int posi, tot;
  159.             scanf("%d%d", &posi, &tot);
  160.             int l = get_k(posi), r = get_k(posi + tot + 1);
  161.             splay(l, 0), splay(r, l);
  162.             auto& son = tr[tr[r].s[0]];
  163.             son.rev ^= 1;
  164.             swap(son.ls, son.rs);
  165.             swap(son.s[0], son.s[1]);
  166.             pushup(r), pushup(l);
  167.         }
  168.         else if (!strcmp(op, "GET-SUM"))
  169.         {
  170.             int posi, tot;
  171.             scanf("%d%d", &posi, &tot);
  172.             int l = get_k(posi), r = get_k(posi + tot + 1);
  173.             splay(l, 0), splay(r, l);
  174.             printf("%d\n", tr[tr[r].s[0]].sum);
  175.         }
  176.         else printf("%d\n", tr[root].ms); //MAX-SUM
  177.     }
  179.     return 0;
  180. }
  181. /*
    输入样例 1
  182. 9 8 
  183. 2 -6 3 5 1 -5 -3 6 3 
  184. GET-SUM 5 4
  185. MAX-SUM
  186. INSERT 8 3 -5 7 2
  187. DELETE 12 1
  188. MAKE-SAME 3 3 2
  189. REVERSE 3 6
  190. GET-SUM 5 4
  191. MAX-SUM
  192. */

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

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

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

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

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

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

  1. #include"bits/stdc++.h"
  2. using namespace std;
  3. const int N = 500010;
  4. #define inl inline
  5. #define reg register
  6. //#define ll long long
  7. int n,m;
  8. struct node
  9. {
  10.     int s[2],p,v,id;
  11.     int size;
  12.     inl void init(int _v,int _id, int _p)
  13.     {
  14.         v = _v,id = _id,p = _p;
  15.         size = 1;
  16.     }
  17. }tr[N];
  18. int root[N],idx;
  19. int p[N];
  20. inl void read()
  21. {
  22.     std::cin.tie(nullptr);
  23. }
  24. inl int Find(int x)
  25. {
  26.     return p[x] != x ? p[x] = Find(p[x]) : p[x];
  27. }
  29. inl void pushup(int x)
  30. {
  31.     tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
  32.     
  33. }
  35. inl void rotate(int x)
  36. {   //y为x的父节点，z为x的爷节点
  37.     int y = tr[x].p,z = tr[y].p;
  38.     int k = tr[y].s[1] == x;//k为（x是否为y的右节点）//即k为（x节点的左右儿子）
  39.     tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
  40.     //z节点的y儿子改为x儿子，x节点的父节点改为z
  41.     
  42.     tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y;
  43.     //处理原x的右儿子，以及原x右节点的parent
  44.     tr[x].s[k ^ 1] = y,tr[y].p = x;
  45.     //更改原x的非y儿子节点（另一个儿子），更改y的父节点为x
  46.     pushup(y),pushup(x);
  47.     //update size
  48.     //x上移1个单位
  49. }
  50. inl void splay(int x,int k,int b)//将集合b的splay中x节点转到k节点的下面while(tr[x].p != k)
  51.     {
  52.         int y = tr[x].p, z = tr[y].p;
  53.         if(z != k)
  54.             if((tr[y].s[1] == x) ^ (tr[z].s[1] == y))    rotate(x);
  55.             else    rotate(y);
  56.             //双旋 
  57.             rotate(x);
  58.     }
  59.     //k==0 
  60.     if(!k)    root[b] = x;//集合b的根节点为x
  61. }
  62. inl void insert(int v,int id,int b)//将编号为id，重要度为v 的节点加入集合b的splay中
  63. {
  64.     reg int u = root[b],p = 0;
  65.     while(u)    p = u,u = tr[u].s[v > tr[u].v];
  66.     u = ++idx;
  67.     if(p) tr[p].s[v > tr[p].v] = u;
  68.     tr[u].init(v,id,p);
  69.     splay(u,0,b);
  70. }
  71. inl void dfs(int u,int b)//将根节点u所在splay中的每一个点插入到集合b的splay中
  72. {
  73.     if(tr[u].s[0])    dfs(tr[u].s[0],b);
  74.     if(tr[u].s[1])    dfs(tr[u].s[1],b);
  75.     insert(tr[u].v,tr[u].id,b);//查询集合b的splay中重要度第k小的节点编号
  76. }
  77. inl int get_k(int k,int b)//2é?ˉ?ˉo?bμ?Splay?D??òa?èμúkD?μ??úμ?±ào? 
  78. {
  79.     int u = root[b];
  80.     while(u)
  81.     {
  82.         if(tr[tr[u].s[0]].size >= k)    u = tr[u].s[0];
  83.         else if(tr[tr[u].s[0]].size + 1 == k)    return tr[u].id;
  84.         else k -= tr[tr[u].s[0]].size + 1,u = tr[u].s[1];
  85.     }
  86.     return -1;
  87. }
  88. int main(void)
  89. {
  90.     read();
  91.     scanf("%d%d",&n,&m);
  92.     //init Find-Union and root
  93.     for(int i = 1;i <= n;i ++)
  94.     {
  95.         p[i] = root[i] = i;
  96.         int v;
  97.         scanf("%d",&v);
  98.         tr[i].init(v,i,0);/init 每个集合的root
  99.     }
  100.     idx = n;//前n个下标个n个splay的根节点用
  101.     while(m--)
  102.     {
  103.         int a,b;
  104.         scanf("%d%d",&a,&b);
  105.         a = Find(a),b = Find(b);
  106.         if(a != b)//如果两个岛不在一个集合中，需要合并
  107.         {
  108. /*
  109. tr[root[a]].size > tr[root[b]].size
    保证集合a中元素的个数 <= 集合b中元素的个数
    启发式合并
    保证较小的集合加入较大的集合
  110. */
  111.             if(tr[root[a]].size > tr[root[b]].size)
  112.                 swap(a,b);//保证集合a中的元素个数 <= 集合b中的元素个数
  113.             dfs(root[a],b);//将集合a的splay里的每一个点插入到集合b的splay里面
  114.             p[a] = b;//将集合a合并入集合b
  115.         }
  116.     }
  117.     reg int q;
  118.     scanf("%d",&q);
  119.     while(q --)
  120.     {
  121.         char op[2];
  122.         int a,b;
  123.         scanf("%s%d%d",op,&a,&b);
  124.         if(*op == 'B')//add edge
  125.         {
  126.             a = Find(a),b = Find(b);
  127.             if(a != b)//Union 如果两个岛不在一个集合里，需要合并
  128.             {
  129.                 if(tr[root[a]].size > tr[root[b]].size)
  130.                     swap(a,b);
  131.                 dfs(root[a],b);
  132.                 p[a] = b;
  133.             }
  134.             
  135.         }else
  136.         {
  137.             a = Find(a);//集合中不足b个数，输出"-1"
  138.             if(tr[root[a]].size < b)    puts("-1");
  139.             else    printf("%d\n",get_k(b,a));//否则查询第k小数 
  140.         }
  141.     }
  142.     
  143.     return 0;
  144. }

好了，就到这里了

数据结构不能单纯靠记忆，一定要理解，记住啊，一定要靠理解，记忆只不过是帮助你在考场上调试出来的东西，并不是其主导的因素

原文链接：https://www.cnblogs.com/better-coding/p/17774921.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C++热门文章

  • C/C++编程笔记：编写不会在C ++中编译的C程序，我教你呀！
  • 洛谷 P2085 最小函数值
  • 使用C++界面框架ImGUI开发一个简单程序
  • C++ Json解析CJsonObject的详细使用
  • C++编译错误杂记
  • 二分法（二）：采用二分法解决“最小化最大值问题”
  • C++实现json字符串与map的转换
  • C++借助curses库实现俄罗斯方块
  • 长乐培训Day5
  • 【OpenFOAM】——OpenFOAM入门算例学习

    • C++推荐文章

  • #8. 「模板」树链剖分
  • 预设型 DP
  • Standard Template Libary or C++ Standard Library
  • 一种优秀的虚拟机内存架构 - AQ
  • 如何让 MGR 不从 Primary 节点克隆数据？
  • TLScanary：Pwn中的利器
  • c++临时对象导致的生命周期问题
  • C++(Qt)-GIS开发-简易瓦片地图下载器
  • 逆向通达信 x 逆向微信 x 逆向Qt
  • C++面向对象

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号