一个关于Treap优化的点子

我今天做了一道可持久化Treap的题目。因为我不会写非旋转版Treap,更不会写可持久化非旋转版Treap,所以就想着法子绕开这个禁区。当然,我这么做是不对的,认真学习的我应该正面对抗来自Treap的代码量攻击;但是我在这偷懒的过程中却想出了一种不基于随机性、代码量小的做法。这种做法我感觉应该可以拓展,但是暂时还没想到怎么应用于更多的问题。

题目大意

交互题。

在题目给的头文件里,定义了一种结构体Data、满足交换律和结合律的函数Data F(Data x,Data y)、还有一个一开始为空的序列。我们需要实现对该序列的三种操作:

  • 往第idid个序列后面加入一个DataData,作为一个新序列;
  • 从第idid个序列最后面删去一个元素,作为一个新序列;
  • 问第idid个序列[l,r][l,r]FF值为多少。

要求在每次询问的时候最多调用一次F

做题经历

我在考试的时候,把“每次询问”理解成了“每次操作”。这样的话,我们需要在加入的时候调用一次FF,在每次询问区间的时候只调用一次F就能求出所有可能的[l,r][l,r]。我尝试对序列长度比较小的情况进行手工构造,发现在n=6n=6的时候我就做不到了,询问/加入的时候必须至少调用两次。我一想,连我手工构造都构造不出来,那我还能有什么最有策略或者DP能够搞定这个问题?弃了!

最后20分钟的时候开始码主席树解决调用次数大于1的情况,码完之后样例竟然过不了,0分。后来再调了一会,发现可持久化的新结点编号忘记return了。因为编译忘了开-Wall,编译器也没提示我,就这样没了那30分暴力。

正常算法讨论

在插入的时候,是可以多次调用F的!所以一种O(n2)O(n^2)的做法就是在插入的时候把所有的[l,r][l,r]求一遍,询问直接给出答案。

先不考虑可持久化,那么可以建一棵线段树,每个节点类似max sub-array问题维护[l,mid][l,mid]后缀和与[mid+1,r][mid+1,r]前缀和,询问的时候找到第一个跨中间的节点,查询,相加,返回,只调用一次F

加入可持久化是不能用这种方法的,因为每次更新时为了更改前缀和后缀总共要用O(n)O(n)的时间和空间,不能高效利用求出的数据,没有体现主席树的思想。有小伙伴开主席树套主席树,多开的那些主席树就用来维护这个前缀和后缀,两个log\log。祝他们好运。

考虑用Treap来解决这个问题。每个节点维护左子树的后缀和与右子树的前缀和,对于旋转,就暴力重构。这里的时间复杂度我还不是很确定,题解说这个子树有O(logn)O(\log n)个节点,有待考证。

有一个比较好的优化思路。因为我们已经可持久化,而每次插入只插入一个节点,所以查询的右区间我们可以通过追溯历史版本来转化为求后缀和。每个节点可以剪掉一半的信息。

删除就是询问历史版本,接下来用可持久化Treap来维护就好了。期望时空复杂度O(nlogn)O(n\log n)

多想一点

为什么Treap的复杂度优秀?在这题里,我们每次只插入一个在最右边的节点,再根据权值大小往上旋转几次。那是不是有一种旋转方式最优?

所以我让一个节点如果有左儿子,那么它的左子树必须是满二叉树。在实现的时候,只需要从上沿着最右边的链一直往下走,找到第一个左边size=右边size的节点,模拟Treap的旋转之后发现在此处应该进行的操作为用新结点代替这棵子树,并把原来的子树作为新节点的左子树。这样能实现比较平衡的二叉树,高度logn\left\lceil\log n\right\rceil

这也是我这几天实现过的最简短的代码,详见Github/EZOJ/Contests/1315/C.cpp

再多想一点

这题要求可持久化。那么我的做法类似主席树,更新最右边那条链。在每个节点上我们需要储存左子树的信息,看一看满二叉树,容易算出空间复杂度O(nlogn)O(n\log n),因为时间上要干的事情就是算一遍这些数组,所以时间复杂度也是O(nlogn)O(n\log n)

等等!

好像有点问题?

我们在加入一个结点的时候具体要开多大的数组来存左子树是依赖于当前树的形态的。如果题目连续插入,那么均摊每次操作复杂度O(logn)O(\log n)没有问题。在我们把一整个树归为左子树的时候,我们是不是要O(n)O(n)算一遍左子树后缀和?因为要求可持久化,题目可以很恐怖地不断选取这个复杂度刚好最坏的时间操作!

这就像我的基于边的DP在碰到菊花图的时候无能为力了,却还傻傻不知道为什么TLE。

这就是为什么Treap优秀,因为它旋转次数总是随机的,和形态没有关系,也就卡不掉了。

很启发

虽然做了无用功,但是我觉得这个思考过程还是十分启发的。这种方法能提供一个均摊O(logn)O(\log n)的复杂度,常数十分小。所以这样的做法是否能继续推广到其它问题上,优化算法,还有待研究。

如果已经有人搞出类似的东西,请务必联系我,给学识浅薄的我的思想来个大解放,实现友好交流,促进共同发展。

一道类似的题

今天看杂题的时候发现的CodeChefXRQRS,思路十分像,做法也很像,只是需要把Treap改成可持久化Trie,这不更好写了嘛!

avatar
Kerry Su