树套树笔记

没错这是个大坑

这两天看到一鬼畜题,带插入区间k小值,BZOJ3065,网上搜的hzwer写法貌似是替罪羊树套线段树(?!!)省队里面一神犇也大致给我讲了讲,说实话,并没有怎么听懂Orz

总之先从最基础的树套树开始,也就是带修改区间k小值

静态的区间k小值大家都会做,内存换时间就划分树,时间换内存就主席树

带修改区间k小值呢,其实思路和主席树差不多(主席树:要是我能查询[a,b)区间里进入左子树的数的个数就好了!),要是我能查询[a,b)区间里进入左子树的数的个数就好了。但是带修改怎么查呢?

假设对于一个区间,有数组flag_inleft,其中flag_inleft[i]==1表示元素i进入左子树,==0表示进入右子树,那么对于区间[a,b),我们只要求sum {i | a<=i<b }的值就能达到目的了。

好了,那么我们在每个区间里面放一颗树状数组或者线段树…就能logn的时间查询上诉sansum值了,每次查询时间(应该是不紧却的)上界是O(log^2(n)),(因为树高logn,每个节点查询又需要logn(感觉这里不紧却))。还是很好写的。

(我会回来填坑的)

(我回来填坑了)

其实这题用Splay也可以写的嘛,主席树套Splay。

众所周知Splay是可以维护区间的,鉴于查询区间k大的时候我们只需要主席树的每一个节点支持查询“到i的时候有多少个数进入了左边”,而Splay又支持快速的插入和查询前缀和…后面就不用详细展开了。

更加抽象一点,对于序列上的一个区间k小类型的操作f,执行这个操作的复杂度为O(f*logn)。因为在主席树上一共要经过logn那么多个点,而每个点都要花O(f)维护。

例如主席树,查询(二分)是logn的,所以主席树整体查询复杂度是O(logn*logn)。

例如划分树,查询(二分)是1的,所以划分树整体查询复杂度是O(1*logn)。

例如带修改的主席树(主席树套树状数组),修改操作(在树状数组上)是logn的,所以整体修改复杂度是O(logn*logn)

主席树和划分树关系的一点感想(以及一颗主席树)

主席树(fotileOrz树/函数式线段树)和划分树的主要区别个人觉得是划分树把每一步的信息都单独记录下来,这样查找的时候可以直接寻址,然而主席树是不必要就不更新。

而且主席树可以用主席树套树状数组/线段树(看了某篇记不得名字的论文以后对这两者有了新的认识:其实就是一回事)支持修改, 当然这样的话复杂度就要乘上一个logn了.

莫名其妙的,在Vijos上主席树用的空间居然大于划分树,

主席树vs划分树

下面是划分树,上面是主席树。

根据TLK同学的意见开始用真实存在的null节点来代替#define NULL 0,(似乎)确实方便不少(虽然调试的时候带来一点小麻烦)
刚开始的时候是用std::pair和vector来做“时间-数量”的映射,后来想到数量肯定是递增的,就直接看与begin的距离就好了 话说我的划分树写的真的是丑Orz

(标题在骗人,此处无颗主席树)