Chtholly 树，以及一点札记
作为一个实打实的老年退役 OI 水人，每每看到新型骗分数据结构的时候，我都是非常兴奋的。
今天见到了一个神奇的数据结构，名叫 Chtholly Tree。
寒假咸在家，虽说毕设任务当头，但还是忍不住摸鱼。于是就随便写一写。
名字的来源
来自世界上最幸福的女孩珂朵莉·诺塔·瑟尼欧里斯。
 |
 |
 |
首次出现在 2017 年，得名于 CF896C 这道题的题解，能有效处理随机数据、支持区间推平的区间查改类问题。
萌百的评论区竟然也有人提到了这玩意，可怕。
原题简述
有一长度为 N 的序列。M 次操作，有以下四种：
- 把区间 $[l, r]$ 中的数都加上 x
- 把区间 $[l, r]$ 中的数都设为 x（即区间推平，极为重要）
- 询问区间第 x 小
- 询问区间中各元素的 x 次幂之和，结果对 y 取模
全部数据独立均匀随机，并且伪随机函数和数据的生成方法直接在题干中给出；输入只有 N 和 M 和随机种子，其他的自己算。
Chtholly 树简述
虽然题目看起来好像不太可做，但由于数据完全是随机的，我们可以想各种姿势骗分。珂朵莉树就是在这种情景下诞生的一种优秀的骗分数据结构，它的主要思想如下：
- 用一棵区间树（
std::set即可），或者干脆就用链表，来维护序列中所有包含相同值的连续区间 - 对于操作 2，摧毁 $[l, r]$ 中所有的区间，然后加入一个新的表示 $[l, r]$ 的区间
- 对于其他操作，暴力扫描所有 $[l, r]$ 中的区间，在每个区间上 $O(1)$ 地做相应的操作
该算法十分暴力，其正确性显然。
Chtholly 树的复杂度
由于数据都是随机的，操作 2 期望占了所有操作的 $\frac{1}{4}$；直觉上，珂朵莉树维护的区间数应该不会太多，从而效率也就能比较高。
以下为了讨论方便，假定 $m = \Theta(n)$。
可以证明，在使用 std::set 的情况下，珂朵莉树的复杂度的期望为 $O(n \log \log n)$。
下面，我提供两种证明方式。第一种是比较容易想到的，但是缺少严谨性，算出的复杂度也不紧；第二种摘抄参考了 Editorial 的评论区以及这篇文章。
一个不甚严谨的证明
考虑第 $i$ 次操作：先固定前 $i-1$ 次操作以及这次操作的区间 $[l_i, r_i]$；记此次操作净删除区间数为 $d_i$，此次操作涉及的区间数为 $f_i$。
对于第 1 种操作有 $d_i = -O(1)$，对于第 2 种操作有 $d_i = \Theta(f_i)$，对于第 3、4 种操作有 $d_i = 0$。于是显然有
$$ \mathbb{E}[d_i] = \Theta(\mathbb{E}[f_i]) $$
同时，我们注意到序列一开始有 $O(n)$ 个区间，而一次操作最多增加 $O(1)$ 个区间，每个区间最多被删掉一次。因此，我们有
$$ \sum_{i=1}^m d_i = O(n + m) $$
据此推论：
$$ \mathbb{E}\left[\sum_{i=1}^m f_i\right] = O(n + m) $$
区间用 std::set 维护并且始终至多有 $O(n)$ 个，于是操作每个区间的代价就是 $O(\log n)$。由于 $m = \Theta(n)$，珂朵莉树最终的复杂度上界就是 $O(n \log n)$。
这个证明在估计区间数的时候使用的是 $O(n)$，但这个界并不一直是紧的。下面的证明会处理这个缺憾。
一个严谨一点的证明
区间的右端点和区间一一对应，我们转而考虑所有区间的右端点。
只有操作 2 能够摧毁某个现有的右端点，为了方便，我们把它称作合并操作（Merge）。考察 $k$ 次 merge 之后，右端点 $i$ 仍然存活的概率。这里的「仍然存活」指的是，$i$ 在这些 merge 执行之前就是某个区间的右端点，并且这 $k$ 次 merge 都没有摧毁它。先摧毁后重建的情形不在讨论范围之内。
一次 merge 不摧毁右端点 $i$ 的充要条件是它操作的区间不包含 $i$，或者以 $i$ 为其右端点。在所有的 $\binom{n}{2}$ 个区间中有 $i + \binom{i-1}{2} + \binom{n-i}{2}$ 个满足这一条件，因此当 $k = 1$ 时上述概率就等于
$$ \frac{n^2 + 2i^2 - 2ni + 2}{n(n-1)} \approx \left(\frac{i}{n}\right)^2 + \left(1-\frac{i}{n}\right)^2 $$
假设各次操作独立随机，则 $k$ 次 merge 后 $i$ 仍存活的概率就是上述结果的 $k$ 次幂。最开始我们期望有 $O(n)$ 个区间，由期望的线性性，$k$ 次 merge 后区间数量的期望等于每个点继续作为右端点存在的概率之和：
$$ \sum_{i=1}^n \left(\left(\frac{i}{n}\right)^2 + \left(1-\frac{i}{n}\right)^2\right)^k \approx n\int_0^1 \left(x^2 + (1-x)^2\right)^k dx$$
可以证明右边积分的上界为 $O(n / k)$：
$$
\begin{aligned}
I &= n\int_0^1 \left(x^2 + (1-x)^2\right)^k dx \\
&= n\int_{-0.5}^{0.5} \left(0.5 + 2x^2\right)^k dx \\
&= n2^{-k}\int_{-0.5}^{0.5} \left(1 + 4x^2\right)^k dx \\
&= n2^{-k}\sum_{i=0}^k \binom{k}{i} 4^i \int_{-0.5}^{0.5}x^{2i} dx \\
&= n2^{-k}\sum_{i=0}^k \binom{k}{i} 4^i \int_{-0.5}^{0.5}x^{2i} dx \\
&= n2^{-k}\sum_{i=0}^k \binom{k}{i} \frac{1}{2i+1} dx \\
&\leq n2^{-k}\sum_{i=0}^k \binom{k}{i} \frac{1}{i+1} dx \\
&= n2^{-k}\frac{2^{k+1}-1}{k+1} \\
&= O\left(\frac{n}{k}\right)
\end{aligned}
$$
平均下来，每个右端点经过 $k$ 次操作存活的概率是 $O(1 / k)$。
令 $t$ 表示区间的总数。初始时有 $O(n)$ 个右端点，存活到最后的概率都是 $O(1 / m)$；倒数第 $i$ 个操作创建 $O(1)$ 个新端点，存活到最后的概率是 $O(1 / i)$。因此：
$$ \mathbb{E}[t] = O\left(n\cdot\frac{1}{m} + \sum_{i=1}^{m}\frac{1}{i}\right) = O\left(\frac{n}{m} + \log m \right) $$
以 $t_i$ 表示第 $i$ 次操作后 $t$ 的值；利用 $m = \Theta(n)$，我们有：
$$ \mathbb{E}\left[\overline{t_i}\right] = \frac{1}{n} \sum_{i=1}^{n} O\left(\frac{n}{i} + \log i\right) = O(\log n) $$
区间用 std::set 维护，操作每个区间的代价是 $O(\log t)$。利用琴生不等式可得总的时间复杂度为 $O(n \log \log n)$。
证毕。
总结
我们可以看到珂朵莉树的高效完全是由数据的随机性，以及随机的区间推平操作这二者来保证的。
因此它最终也只能算是一个骗分算法（悲
一点札记
《末日时在做什么？有没有空？可以来拯救吗？》播出于 2017 年 4 月，当时我还是一集一集追的整部番。
回首当初，宛如昨日；然而掐指一算已经过了 2 年多，等 1 月新番完结就是恰好 3 年了。
受日漫的荼毒我一直觉得「人不中二枉少年」，然而现在回想起来当年追番时的激情四射也许就是我少年时代的标志；时过境迁，如今的我虽然还记得威廉和珂朵莉之间那段令人掉泪的故事，却再也拿不出当年的劲头追番和补番了。
最近还找到了《千桃》FD 的资源，兴致勃勃地下载下来，然后发现本编的故事忘得差不多了。
——的确是老了。
——但是就算老了，我也永远喜欢珂朵莉。