主题

主题

 
   

Splay在区间问题中的简单的运用

  • 闲谈

Splay的复杂度分析是均摊O(logn),常数为3+。这个复杂度是Splay作为容器的势能分析中得来的。显然作为容器而言,Splay没有Treap以及红黑树等诸多平衡树速度快。

但是Splay仍然这么受青睐的原因大概是处理区间问题的作用。

但是Splay处理区间问题就不是单纯的容器了。本蒟显然不会证明时间复杂度。

  • 原理

第一个条件是伸展树可以任意旋转。通过旋转把需要处理的区间放到一棵子树中。这是其处理区间问题的方式。

第二个条件是与线段树一致的。它所基于的思想也是区间加法。

  • 实现方法

以本蒟的Splay代码为例——

(写这篇文章的时候,我的Splay相当于大众的rotate,我旋转到root写的是在外面while……Splay(x)。本来Splay这个程序应该是直接旋到root的。后来也改成大众化的了)

节点:

一个节点,既需要储存本节点的信息(为了区间加法),也需要储存子树的信息(为了便于查询)

一个节点的tag(为了便于修改)表示这个节点的子树(包括自己)都没有被更新。

旋转:

我一般写Spaly(翻转树),即只有单旋。

在旋转之前,先会Pushdown(f)与Pushdown(p)。(我不用PushUp)这一个操作使得 个标记 对于 所有在这个标记上方(不包括自己)的节点 信息都是正确的

在旋转之后,f与p的信息变化了,因此会重新更新f与p的信息。更新f与更新p都是用区间加法——即通过左右子树的信息与当前结点的信息结合来更新。

由于我们只保证了 个标记 对于 所有在这个标记上方(不包括自己)的节点 信息都是正确的。所以我们需要Pushdown其他的节点——f的儿子与p的儿子。由于交换后用来更新的这几个节点,在交换前也是一样的,所以可以在旋转前Pushdown。

常数较大,因此没有tag的时候,就不要Pushdown了,否则常数就很大了。

修改与查询:

我们把一个区间的前驱旋转到根,后继旋转到前驱的右儿子。之后后继的左子树就是我们要处理的区间。由于我们节点记录了子树的信息,所以可以通过查询节点来实现对子树(区间)的查询。

对于修改而言,由于我们要保证 个标记 对于 所有在这个标记上方(不包括自己)的节点 信息都是正确的。所以我们需要直接修改前驱+后继,不更新当前子树的信息,只打一个tag。

对于查询而言,由于前驱与后继的标记可能没有更新到当前子树,所以我们先Pushdown(pre),再Pushdown(Suf),最后Pushdown(p)(即当前子树的根节点)。这样p的信息就是完全正确的了。之后由于我们一个节点维护了子树的信息,因此可以直接查询。

这样就把区间问题统一起来了。

  • 时间复杂度

我并不会证明这样的Splay的时间复杂度。UOJ发了一个势能分析的课件。打算去学习一下。我觉得这个复杂度不一定是O(nlogn)的样子。

  • 例题

一般线段树可以做的题目,Splay都可以做。记不得是谁这么说来着了?还有人说“Splay是序列之王”。虽然我写的常数比较大。

从codevs的线段树习题开始。

给出一个长度为n的序列。给出m个操作:

  1. 给一个区间[li..ri]加上一个数字。

  2. 查询一个区间[li..ri]的区间和。

这个是线段树的朴素题了。我们用Splay也很好维护。每一个节点维护子树的权值和,以及自己的权值。tag维护这个子树加了多少即可。

代码

给出一个长度为n的全1序列。给出m个操作:

  1. 将一段区间[li..ri]覆盖为0。

每一次操作之后输出序列中剩余的1的个数。

这个也是很朴素的线段树。我们用Splay仍然很好维护。每一个节点维护子树的权值和,以及自己的权值。tag维护这个子树是否被0覆盖。

(另外有一个一样的题目:codevs_1299,数据范围5e5,(我写的)Splay常数较大的确过不了。不过这本来是并查集的题目,线段树被过了可能数据倒偏水了)

代码

给出一棵大小为n的全1树。给出m个操作:

  1. 将一个节点取反。

  2. 查询一棵子树的1的个数。

把DFS序处理出来,问题转换为单点取反与区间查询1的个数。可以用zkw线段树来维护。据说可以用树状数组。懒得管他——只要不是单点修改的区间求和/区间前缀最值,我就懒得写树状数组(好奇怪的傻子——宁可写10行的线段树不写2行的树状数组)。

我们用Splay仍然很好维护。维护子树和。单点修改可以直接旋转到根,然后修改。常数比较小。甚至不用维护tag。

代码

给出一个长度为n的全0序列。给出m个操作:

  1. 将一段区间取反。

每一次操作之后输出整个序列的1的个数。

这个也是很朴素的线段树。我们用Splay维护比较方便。同样类似于codevs_1082,维护节点的权值,以及一棵子树的权值和。tag维护这个子树是覆盖了奇数次还是偶数次。

写的过程中,觉得线段树的tag标准——每一个节点的tag记录的是儿子的信息而不是自己这棵子树的信息。似乎这样方便一些。旋转+修改+查询的代码都要调整一下。常数相差不是很大的样子。

最后还是用原来的方法——tag记录自己这棵子树的信息。

代码

给出一个长度为n的序列,每个数字不超过1e12。给出m个操作:

  1. 给一段区间开方。

  2. 查询一段区间的和。

这个线段树的做法是比较直接的。不要花脑子的暴力修改,遇到全1的子串就返回。

需要花脑子的是总时间复杂度的分析:每一个数字最多会被开方log2(12)=4次。于是每一条线段树的树链最多会被遍历4次。由于线段树有O(n)条树链,遍历一次是O(logn),于是总得复杂度是O(nlogn)。

Splay也可以实现类似的维护。同样在全1子树就返回。那么每一个节点最多会被遍历4次。Splay这么做的复杂度不能通过树链来分析,但是我们知道每个节点会被执行4次操作,就可以视为每个操作执行了4次。那么复杂度相当于是 每一个操作执行1次 的4倍。

而每一个操作执行1次的复杂度是之前大量事实证明(+本蒟不会的势能分析)得到的O(nlogn),所以总得复杂度是与线段树一致的。

(本蒟的Splay比某些人的线段树跑的还快,比某些人(比方说本蒟)的树状数组跑得还快……大概是因为数据水了。换一种说法,出题人想不到某些无聊的人会拿Splay来做这些题目)

代码

  • 为什么选择Splay

Splay常数大约为4,一般是指在Pushdown的时候所附带的常数。而线段树常数一般是2,指的是把区间一般拆分为2logn个区间。

一个微弱的优势是Splay空间开销的常数为1,线段树为2(动态开节点)。但是时间开销的常数即为线段树的2倍。在一些情况,比方说树套树中,首选平衡树(当然不一定是Splay)。

那么,为什么要选择Splay呢?

动态序列问题!

  • 另一个原理

线段树是基于区间加法的原理,通过对区间的拆分,来实现维护。显然这是一个静态的问题。然而Splay没有静态的树形结构。Splay则是基于区间加法的原理,通过旋转的方法,使得一棵子树成为一个区间,来实现维护。

在静态区间加法的问题中,Splay显然没有线段树优。但是在处理动态序列问题的时候,线段树难以下手,但Splay可以方便维护。

  • 经典问题

  1. 区间翻转。

    这个问题是Splay的入门练习了。现在搬出来静静思考一下。其实这个问题只涉及到区间的tag维护。然而这一个tag会使得线段树的形态发生很大的改变。然而Splay本身就是在改变中处理动态问题。

  2. 动态序列问题。

    如果带插入,Splay可以把左边子树与右边子树旋到根。把要插入的节点重置为根,然后把子树接上。

    也许以后会有一些“调整数据结构形态”的概念(自己瞎逼逼的名词)。比方说Splay是对二叉排序树的调整,再者如可并堆中的左偏树是对普通堆的调整。可能以后会有一种神奇的东西对线段树进行调整。比方说如果需要对线段树实现插入操作,那么动态开节点就会一直开的很深。如果可以实现对线段树的形态的调整,会不会实现均摊O(logn)?

  • 小结……?

能用线段树的就用线段树。

不能用线段树的也不一定要用Splay(一个浅显的例子:能用二维树状数组的一般都用树套树)。

但是可以考虑Splay……

 
 
评论
 
 
热度(1)