树套树笔记

没错这是个大坑

这两天看到一鬼畜题,带插入区间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)

Advertisements