对于线段树套线段树的结点数上界的研究与创新（一）

· · 算法·理论

引言

同学们写线段树套线段树的时候常常会有开大了 MLE，开小了又会 RE 的疑惑。

那么我就在这里分析一下其结点数上界，同时举例证明可以在一定条件下取到。

线段树套线段树，这里指区间线段树套动态开点权值线段树。

对于树状数组套动态开点权值线段树可以用同样的方法分析。

分析

注：以下所有的 \log x 均指 \log_2 x。

设序列长度为 n，修改次数为 m，值域为 v。

显然总结点数在 m 次修改对于 n 个数均匀时最大。

设 f(i) 表示一棵存储了 i 个数的信息的线段树所占用的结点数上界，则有：

f(i)=2i-1+(\log v-\log i)i

而树套树的总结点数上界应为：

f(n+m)+2f\left(\dfrac{n+m}{2}\right)+4f\left(\dfrac{n+m}{4}\right)+\cdots+nf\left(\dfrac{n+m}{n}\right)

整理得：

-(2n-1)+(n+m)(\log n+1)\left(2+\log v+\dfrac{\log n}{2}-\log (n+m)\right)

即：

-(2n-1)+\dfrac{(n+m)(\log n+1)\left(4+2\log v+\log n-2\log (n+m)\right)}{2}

若使用离散化，则 v\le n+m，总结点数上界为：

-(2n-1)+(n+m)(\log n+1)\left(2+\dfrac{\log n}{2}\right)

即：

-(2n-1)+\dfrac{(n+m)(\log^2 n +5 \log n+4)}{2}

结论

设序列长度为 n，修改次数为 m，值域为 v。

则线段树套线段树的结点数上界为：

-(2n-1)+\dfrac{(n+m)(\log n+1)\left(4+2\log v+\log n-2\log (n+m)\right)}{2}

若使用离散化，则 v\le n+m，结点数上界为：

-(2n-1)+\dfrac{(n+m)(\log^2 n +5 \log n+4)}{2}

且上界取到的条件极为苛刻。

同时上界也是可以取到的，例如 (n,m,v)=(2^p,2^q-2^p,2^q)，其中 p,q\in N \land p\le q。

后记

作者本人使用超过 60 min 学习树套树，使用近 60 min 推式子和举例子，又使用近 60 min 写文章，点个赞再走呗！

注意

如果仅是想知道写树套树时要开多少倍空间，那么阅读至 后记 足矣。

如果想思考和探索更多，可以继续阅读。

以下内容可能引发您的不适，请务必谨慎阅读。

思考

可以发现对于多数 (n,m,v)，上文的结点数上界是取不到的。

问题的根源在于，结点数是基于整数意义的，而 \log 则是基于实数意义的，二者并不匹配。

所以，要想推出 (n,m,v) 在整数意义下的上界，需要更复杂的分析和更深刻的理解。

这也是这篇文章的标题中包含“一”的原因所在。

创新

上文中提到，基于整数意义的结点数和基于实数意义的 \log 并不匹配。

既然我们希望推出 (n,m,v) 在整数意义下的上界，从另一角度考虑，我们又为什么不能希望将结点数这一概念抽象成实数意义？

倘若真的能将结点数抽象成实数意义，那么同理深度也将被抽象成实数意义。就这样，我们将结点数、深度、\log 统一起来。对于任何非负实数 r，都存在结点数为 r、深度为 \log_2 (r+1) 的满二叉树（定义结点数为 1 的满二叉树深度为 1）。

同时，这一项统一，也意味着上文中在整数意义下取不到的结点数上界在实数意义下都能取到了。