区间K小问题

Problem 1:无修改、无插入区间第K小问题

关于这题,可以直接用主席树(函数式线段树)来解决

假设现在有无限的内存和时间,可以对每个前缀构造一棵权值线段树,然后每次询问区间 [l, r] 就找出前缀 [0, l - 1] 和 [0, r] 的线段树,相减就可以得到所需要的权值线段树,然后在这上面根据子树大小跑就可以了

由于空间有限,最开始不初始化整棵树,而是动态的添加节点,并且在插入的时候只有经过的那一条链上的东西会被更改,所以对于一些没有修改的子树,直接用指针指向上一次的版本,因为每一次插入最多经过 \mathcal O(\log n) 个节点,这样总共空间不会超过 \mathcal O(n\log n),同样,时间复杂度也是每次 \mathcal O(\log n)

参考问题:BZOJ-2588: Spoj 10628. Count on a tree

Problem 2:带修改、无插入区间第K小问题

现在需要修改权值,如果暴力修改每棵线段树的话,最多会要修改 \mathcal O(n) 级别的东西,复杂度也会退化

这时候想想,我们需要的操作是修改一个区间的线段树和询问一个区间的线段树的信息,也就是区间修改和区间查询,很容易会想到树状数组!它能够把每个区间用 \mathcal O(\log n) 个区间来表示出来

所以只要在每个树状数组的节点建立可以权值线段树,表示这个区间的权值信息就可以完成所需要的操作了,时间和空间复杂度都是 \mathcal O(n\log^2 n)

参考问题:BZOJ-1901: Zju2112 Dynamic Rankings

Problem 3:带修改、带插入区间第K小问题

现在我们需要支持可以在某个位置插入一个值,比如原先的序列是 1 2 3,然后在第二个位置插入 4 的话,序列就会变成 1 4 2 3

因为树状数组不支持插入元素,但是类似 Problem 2 的思想,你或许会想到使用平衡树,它也在 \mathcal O(\log n) 的时间内支持区间修改、查询,而且还支持插入元素

也就是平衡树上的节点就表示整棵子树中信息的权值线段树,但是仔细想就会发现,平衡树基本都是需要旋转来维持平衡的,这样一转,对权值线段树修改的时间复杂度就会迅速增大!

替罪羊树(Scapegoat Tree)是一种很神奇的平衡树,它不需要旋转来保持平衡,而是有一个平衡因子 \alpha \in [0.5, 1] 每次插入如果发现某棵子树太不平衡,就把整棵子树暴力重构成完全二叉树

具体来说也就是如果某棵子树满足 \alpha \cdot size > \max (left\_size, right\_size),就认为是不平衡的,然后就重构它

\alpha = 0.5 的时候,这棵树就是完全二叉树,当 \alpha = 1 的时候就永远不会重构,很显然,\alpha 越小,询问的效率越高,\alpha 越大,插入的效率越高

可以证明,替罪羊树的查询效率是 \mathcal O(\log n),而插入均摊 \mathcal O(\log n)

这样,这个问题只需要用替罪羊树再套上权值线段树就可以解决了

但是有一个问题就是你需要动态分配内存,并且在重构的时候要及时释放无用内存。并且在写权值线段树的时候不要写成函数式线段树那样,否则内存会爆(我就不小心写成这样被坑了好久)

参考问题:BZOJ-3065: 带插入区间K小值

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/04/kth-problem

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.