浅谈珂树及其扩展运用

· · 算法·理论

什么是珂树

珂朵莉树，颜色段均摊，由 lxl 老师的 CF896C 而得名。
其核心思想是利用推平操作，将一个区间变为左端点，右端点，值三个量，用 set 或链表将其按左端点排序，从而将每段区间串联起来。
这种数据结构极为暴力，它其实并不是一棵树，只是一个序列，但传统珂树在随机数据下可以达到均摊 O(n \log_2 n) 的优秀复杂度，链表版本可以更快。具体证明见题解。
以下介绍的珂树，均为使用 set 实现的珂树。

珂树的原理

这篇文章主要想讲下关于珂树的 trick，原理这里就简单介绍了。
珂树有两个基本操作，分裂和推平，即 \operatorname{spilt} 和 \operatorname{assign}。
对于分裂操作，在 set 内二分目标点所在块，删除该块，插入从目标点分裂开的两个块，复杂度为 \log_2 n。
对于推平操作，先将目标区间的两端分割下来，删除目标区间内所有块，插入一个由左端点，右端点，目标值组成的新块，复杂度与分裂相同。
推平操作主要保证低复杂度，分裂操作用于获取区间。
基于这两个操作，我们可以完成区间加，区间最值等许多操作。
具体代码见下文。

珂树可解决的问题

一般来讲，珂朵莉树可解的问题要求必须有推平操作，且数据尽可能随机，否则可以被卡成平方阶。
从 CF896C 这道例题来讲，要求维护一个序列，支持区间加，区间推平，区间第 k 小，区间次幂和。
传统意义上讲，这类题目应该用线段树解决，但线段树不便维护区间次幂和，且码量较大，我看到这题的唯一线段树做法暴力求了区间次幂和。
但是如果使用珂朵莉树，只需要维护上述三个基本值，再配合上简单的暴力，就可以解决本题，代码。

珂树的相关运用

我读到关于珂树的文章很少讲运用，所以这里就讲讲了。

珂树与其他数据结构

例题 P8512。
和其他多数据结构结合的题目类似，这里主要是利用了珂树便于推平的特性，前缀和思想，同时结合树状数组的区间加，实现多个区间推平结果求和。
这样说可能不太清晰，换句话讲，我们逐个进行推平操作，在推平后统计答案，存入树状数组中。
对于一个区间 [l,r]，我们用 1 到 r 的结果减去 1 到 l-1 的结果，就得到了最终答案。
这样的题目有一个共性，就是每次操作的答案间必须有联系，而这种联系必须可以被其他数据结构或算法所维护，这类题目的关键就是找到并维护这种联系。

珂树与树链剖分

众所周知，一道数据结构题只要上树就变成了一道新题。
这里我选的例题是 P2146。
这题只需要维护区间推平与全局求和。
注意到卸载和安装的方向，一个需要推平整个子树，另一个则是推平从当前点到根的路径。
含有推平操作，则使用珂树更为简便，重链剖分后直接推平即可，代码。
这里用了一点卡常技巧，下文会详细说明。
更深一步，也更能体现珂树优势的树剖题是 P2486，这里不再赘述，可以自行探索。

珂树与卡常

这是我想讲的一点，也是珂树和其他数据结构不同的一点。
在处理某个全局值时，我们可以通过在操作时直接改变值进行维护。
如果是其他数据结构，比如线段树，因为带有懒标记，所以无法直接获知某个值的变化，但珂树不一样，它并不带有任何延迟的内容，而是直接处理，所以可以直接改变全局值，不影响复杂度，代码较为简单。
例子是 Play with tree 这道题，来自 BZOJ，这个题能较为明显的体现出珂树的优势。
首先先将边权下传至点，这是经典 trick 了。
不考虑树剖部分，则需要维护带推平和区间加的区间最值和全局 0 的个数。
区间加和推平都是基本操作，可以直接解决。
接着考虑查询，最值好办，但是维护 0 的个数就复杂了。
这时候，如果利用珂树，基于其非常暴力的基础，我们可以直接通过暴力求出 0 的个数。
代码见下，在校 OJ 上最慢 996ms，校评测姬性能差一些，在其他平台应该会更优秀。

珂树与区间翻转

感谢 @aaron0919，找到了珂树区间翻转的例题。
例题 P5350，需要求和推平区间加，还有区间的翻转交换和复制。
因为珂树使用 set，对区间进行了动态排序，所以很适合处理区间翻转的问题。
在处理翻转操作时，只需要算出该区间左右边界在翻转后的位置，直接修改即可，记得交换左右边界。
然后再说一下如何实现区间复制和交换，复制比较简单，把原区间所有段拿出，删除目标区间内段，改变左右边界后将原区间内块插入即可。
区间交换稍微复杂一点，需要将两个区间取出，在珂树中删除，再改变两区间内块的左右边界，最后插入即可。我的代码稍微复杂了一点，我将两区间内的块先放到了珂树末尾，操作完成后再删除，使用一些容器存储可能会好写一些。 具体代码在这里。

珂树思想的推广

珂树思想，即靠左右边界及一个或多个数值表示一个区间的思想。
一般情况下，我们保存这个区间内数的值，但有时，这个数值还可以表示其他内容。
例题是 P11833，联合省选 D2T1，推箱子。
按时间排序的贪心是容易想到的，这里讲后面的操作部分。
我们注意到，把一排箱子一起推动后，其位置形成一个公差为 1 的等差数列。
则我们保存区间的首项，就可以表示出这个区间内的所有数。
然后需要写比较复杂的模拟，求出每个箱子推完后的时间，判断是否满足限制即可。
很可惜，我在考场上并没有写出来。

总结

珂树代码简单，思维暴力，适于维护易被表示的区间，但要求直接或间接有区间推平操作。
同时，它可以简单的维护几乎所有线段树可维护的内容，在适当情况下可以代替其他数据结构使用。
永远喜欢珂朵莉。