RainAir
My OI Blog
RainAir
Splay 如何维护区间信息

如何维护区间

我们都知道平衡树是一种很神奇的东西,可以用于维护动态的序列总信息,但是如果想维护其中的某一个区间的信息,我们该怎么做好呢?
我们考虑换一种维护方式:平衡树的结构不是按照节点的值的大小来进行建树,而是以这个节点在序列中的位置为关键字来维护。也就是说对于平衡树中任意一个节点 $x$ ,左子树中的元素永远在它前面,右子树的元素永远在它后面。显然一个区间可以对应一个子树,所以我们要使用能提取子树的数据结构,比如 Splay 和 非旋 Treap。
比如我们考虑提取 $[l,r]$ 的区间信息:我们首先将 $l-1$ 节点旋转到根,Splay 变成了这样:
https://blog.aor.sd.cn/wp-content/uploads/2019/02/1.png
然后我们接着把 $r+1$ 旋转到 $l-1$ 的下方,也就变成了这样:
https://blog.aor.sd.cn/wp-content/uploads/2019/02/2.png
我们发现 $R+1$ 节点的左子树就是我们要的区间!所以我们直接对这个子树进行想要的操作即可,复杂度是旋转的复杂度即均摊$O(logn)$。
接下来我们来看一道例题。

「BZOJ1500」「NOI2005」维修数列

题目链接
题目大意:要求你维护一个数列,支持以下操作:
https://blog.aor.sd.cn/wp-content/uploads/2019/02/1112.png
任何时刻数列中最多含有 $5\times 10^5$ 个数,数列中任何一个数字均在 $[-10^3, 10^3]$ 内。
插入的数字总数不超过 $4 \times 10^6$个,输入文件大小不超过 $\text{20M}$。
显然这就是用 Splay 维护区间信息的裸题,接下来我们对于每个操作都分析一遍。

Insert 操作

看起来暴力插入所有的数非常不可取。。。随便就能卡掉的样。
我们不妨考虑一下如果我们有了一个序列里的所有的树,想得到这个序列对应的 Splay 可以有什么方便的方法。显然我们可以直接暴力递归建树,这样不仅快 ($O(nlogn)$) 得到的树也十分平衡。具体建树过程就是每次选择中点作为当前的根,然后递归处理中点左边和右边。
我们不妨把输入的序列先搞个 Splay 出来,然后我们发现在 $x$ 后插入,如果我们按照上面的方法提取出区间 $[x,x+1]$,那么 $x+1$ 的左子树不久应该是我们新建出来的 Splay 吗。。。直接接上去就可以了。

Delete 操作

和 Insert 操作相同的思路:我们直接把这段区间提取出来,不过我们发现现在我们是要删除,所以直接断开这个区间代表的子树与父节点的连接就可以了。但是在这题中为了节省运行空间建议写一个内存回收池来回收这些被删除的节点,这个操作甚至比插入还简单。

MAKE-SAME 操作

考虑把这一段区间修改成同一个数。在线段树上区间操作我们有 lazy-tag 可用,在平衡树上也可以。我们提取出这个区间,然后在根节点打个区间覆盖的标记就行了。注意每次访问这个区间前标记必须要下放。

翻转

学过 LCT 的都会,没学过的参考一下文艺平衡树的做法就可以了。
我们发现建出的 Splay 同时保留了原来序列的性质:如果我们中序遍历这棵 Splay,那么得到的序列就是原序列!我们考虑区间翻转意味着什么:是不是就是对于这个区间里的每一个节点左右儿子都互换啊(因为互换后现在先遍历的是原来后遍历的,并且子树也都交换了)。所以我们同时维护一下翻转标记就可以了。
注意到下放标记的时候如果又有区间覆盖的标记又有翻转的标记,这时候我们可以忽略翻转标记(因为你都是一个数了翻转没有意义),这样能优化不少常数。

求和

我们对于 Splay 的每一个节点,维护它及其它子树中所有节点代表的原序列中的元素的和。查询的时候提取区间直接输出就可以了。

求最大子列

我们考虑一种基于分治的求最大子列方法:对于每个区间都维护从左边开始的最大子列,从右边开始的最大子列和该区间的最大子列,分别记为 $ls,rs,ans$。
对于 ls 的维护:我们考虑从左边开始的最大子列是否覆盖了整个左儿子代表的区间,rs 同理。
对于 ans 就有多种可能了:全都在左儿子区间的,全都在右儿子区间的,跨过中间点的。
pushup 的时候分别维护即可,可以 $O(1)$ 维护。
于是这题的代码也就可以轻松写出来啦:

写在最后

至于我为什么不写听起来更简单的 fhq treap,因为我们机房里的人天天吹它,于是我就不想学了。。。可能以后接触到可持久化的时候才会学QAQ

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/457
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望省选不要翻车,希望我还有脑子
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

  • https://secure.gravatar.com/avatar/fd1b3f3ab2176acd5ce9e8da8aec64df?s=80&d=mm&r=g
    企鹅保护协会会长

    知乎观光团

    1月前回复

RainAir

Splay 如何维护区间信息
如何维护区间 我们都知道平衡树是一种很神奇的东西,可以用于维护动态的序列总信息,但是如果想维护其中的某一个区间的信息,我们该怎么做好呢? 我们考虑换一种维护方式:平衡树的结构…
扫描二维码继续阅读
2019-02-02
文章归档