前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Splay详解(三)

Splay详解(三)

作者头像
attack
发布2018-04-11 14:55:54
8100
发布2018-04-11 14:55:54
举报
文章被收录于专栏:数据结构与算法

前言

上一节我们学习了splay所能解决的基本问题,这节我来讲一下splay怎么搞区间问题

实现

splay搞区间问题非常简单,比如我们要在区间l,r上搞事情,那么我们首先把l的前驱旋转到根节点

再把r的后继旋转到根节点的右儿子

那么此时根节点的右儿子的左儿子所代表的就是区间l,r

这个应该比较好理解

然后就可以像线段树的lazy标记一样,给区间l,r打上标记,延迟更新,比如区间反转的时候更新的时候直接交换左右儿子

这里有一个技巧:如果一个区间被打了两次,那么就相当于不打

所以我们用一个bool变量来储存该节点是否需要被旋转

下传函数可以这么写

代码语言:javascript
复制
inline void pushdown(int x)
{
    if(tree[x].rev)
    {
        swap(tree[x].ch[0],tree[x].ch[1]);
        tree[tree[x].ch[0]].rev^=1;
        tree[tree[x].ch[1]].rev^=1;	
        tree[x].rev=0;
    }
}

注意每次rotate的时候先下传标记

例题

洛谷P3391 【模板】文艺平衡树(Splay)

洛谷P3165 [CQOI2014]排序机械臂

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-11-26 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 实现
  • 例题
    • 洛谷P3391 【模板】文艺平衡树(Splay)
      • 洛谷P3165 [CQOI2014]排序机械臂
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档