Splay详解(三)

前言

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

实现

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

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

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

这个应该比较好理解

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

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

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

下传函数可以这么写

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]排序机械臂

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏linux、Python学习

数据可视化:Matplotlib的坐标轴管理

有兴趣的可以跟踪pyplot模块的figure函数,可以完整看见Figure的创建过程,由FigureManager创建与管理的。

4830
来自专栏计算机视觉与深度学习基础

Leetcode 130 Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions su...

2025
来自专栏程序你好

二叉树搜索树(程序员都知道)

4511
来自专栏owent

POJ PKU 1986 Distance Queries 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1986

822
来自专栏chenssy

【死磕Java并发】-----J.U.C之ConcurrentHashMap红黑树转换分析

原文出处http://cmsblogs.com/ 『chenssy』 在【死磕Java并发】-----J.U.C之Java并发容器:ConcurrentHash...

3328
来自专栏C语言及其他语言

【每日一题】蛇行矩阵

题号:1097 题目描述 蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。 输入 本题有多组数据,每组数据由一个正整数N组成。(N不大于100) 输出...

3488
来自专栏计算机视觉与深度学习基础

Leetcode 275. H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending orde...

2954
来自专栏mathor

matlab—基础绘图

plot函数是matlab中用于作图的函数,常用格式为:plot(x,y),x代表着横坐标,y代表纵坐标,一般情况下如果是画一组连续的图,x和y一般都是矩阵

1453
来自专栏尾尾部落

[剑指offer] 和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100...

691
来自专栏数据结构与算法

BZOJ5249: [2018多省省队联测]IIIDX(线段树 贪心)

不难发现题目给出的是一个树,其中\(\frac{i}{K}\)是\(i\)的父亲节点

871

扫码关注云+社区

领取腾讯云代金券