指针线段树是只占 2n 的空间吗

ppip @ 2022-04-07 22:21:31

by Terrible @ 2022-04-07 22:30:13

从空间复杂度的角度来看，确实可以这么说，但是其实际上空间仍可能大于非指针线段树。

by ppip @ 2022-04-07 22:33:49

但是其实际上空间仍可能大于非指针线段树

为什么啊 @

by ppip @ 2022-04-07 22:33:58

@Terrible

by 小粉兔 @ 2022-04-07 22:34:46

因为还得存指针的空间啊

by huangzitai @ 2022-04-07 22:43:51

非指针线段树可以做到 2n 的空间吧，只不过比较麻烦

by Terrible @ 2022-04-07 22:47:50

首先，非指针线段树的结点数量是小于4n的，而且是可以等于 2n的，这就意味着非指针线段树是有2n空间的潜力的，具体的非指针线段树空间开点量可以看P7122 Chino 与线段树这个题的题解。（我曾经给出来过一个比较贴近的公式 4\times 2^{\lfloor\log_2n\rfloor}）

其次，指针本身也是需要占用空间的，如果是用整数数组做指针的话，需要有两个量leftson和rightson，每一个结点如果都要有一个对应的leftson和rightson的话，每个结点平分 8 字节内存。

如果是动态开点的话，每一个指针量*在 32 位机上是 4 字节，两个是 8 字节，64 位程序是 8 字节，两个就是 16 字节。

如果结点元素占用的空间字节数比较小的话，显然指针线段树的指针空间加起来会比非指针线段树的空间要大。

by ppip @ 2022-04-07 22:49:20

好的谢谢各位巨佬

by Seauy @ 2022-04-07 23:22:27

@Terrible 准确来说好像是 2^{\lceil \log_2 n \rceil+1}-1？

by DarksideCoderω @ 2022-04-08 06:59:21

@Terrible 用动态开点类似的方法建树,非指针也能做到 2n

我写了几年了

by Yansuan_HCl @ 2022-04-08 10:44:32

静态 2n 空间线段树黑科技