空间 O(n) 的神奇线段树合并

这玩意是真👍，我只能拜谢 gk4000plus！

直接说怎么做吧，不然不会引入了🤡👈🤣

做法：在有垃圾回收的基础上，每个点合并时，先将重儿子合并上来，然后再将轻儿子合并上来，最后将这个点上面的操作加进来。（这里的 size 是按操作数计算的）

证明：皎月半洒花：“信息竞赛懂得都懂。”

下面以单点修改距离，区间修改是本质相同的

因为重儿子的值会直接被父亲的值继承上去，所以其实是只有链顶才会临时存储信息，又因为我们是一个 $dfs​$ 的过程，是每次拎出一条从根节点到叶子的链处理的，所以可以只考虑一条链的所有链顶的大小。

首先根据树剖性质，一条到叶子的链只有 $\log$ 条轻边，因为走一条轻边 $size$ 就会翻倍，所以不难发现这条链上从上往下数的第 $i$ 条轻边的子节点的子树大小一定是小于等于 $\frac{n}{2^{i-1} }$ 的

 的神奇线段树合并1.png)

上面所说的的拎出一条链就是用红线圈出来的，橙点连向父节点的边是轻边，其中 $sz_1\le \frac{n}{2^{1-1} },sz_2\le \frac{n}{2^{2-1} },sz_3\le \frac{n}{2^{3-1} },sz_4\le \frac{n}{2^{4-1} }$。

考虑一颗有 $\frac{n}{2^x}​$ 个操作的线段树有多少节点，首先前 $\log \frac{n}{2^x}​$ 层最坏肯定是可以装满的，前 $\log \frac{n}{2^x}​$ 层一共有 $2 ^{ \log \frac{n}{2^x}+1}​$ 个点，也就是 $2\times size_u​$ 个点，所以空间是

$$\begin{aligned} &\sum\limits_{i=0}^{sum}2\times size_u \\ =&\sum\limits_{i=0}^{sum}2 \times \frac{n}{2^i} \\ =&2\times n \times\sum\limits_{i=0}^{sum} \frac{1}{2^i} \\ =&4\times n \end{aligned}$$

注意到我这样算 $\sum\limits_u size_u$ 的大小是 $2\times n$ 的，所以常数可以直接除以 $2$ ，空间是 $2\times n$。

的。（这里的 $sum​$ 是橙点数量，$u​$ 代表第 $i+1​$ 个橙点，下同）

然后是剩下的 $\log n- \log \frac{n}{2^i}​$ 层，还是一样列一个柿子：

$$\begin{aligned} &\sum\limits_{i=0}^{sum}size_u\times (\log n- \log \frac{n}{2^i}) \\ =&\sum\limits_{i=0}^{sum} \frac{n}{2^i} \times \log 2^i \\ =&\sum\limits_{i=0}^{sum} \frac{n}{2^i} \times i \\ =&\sum\limits_{j=0}^{sum} \sum\limits_{i=j}^{sum} \frac{n}{2^i} \\ \end{aligned}$$

首先发现这个柿子的 $\sum\limits_{i=0}^{sum} \frac{n}{2^i}$ 是小于 $2\times n$ 的，然后 $\sum\limits_{i=1}^{sum} \frac{n}{2^i}$ 是小于 $n$ 的， $\sum\limits_{i=2}^{sum} \frac{n}{2^i}$ 是小于 $\frac{n}{2}$ 的，也就每次减少一半，利用的就是 $\sum\limits_{i=0}^{sum} \frac{n}{2^i} \le 2\times n$ 的证明，即 $n > \sum\limits_{i=1}^{sum} \frac{n}{2^i}$，所以这个柿子的和是小于 $4\times n$ 的，即我们线段树的空间复杂度应该是 $6\times n$ 的，区间修改应该是 $10\times n$ 的，但是实测很难卡满！