关于空间

P3372 【模板】线段树 1

TankYu @ 2024-08-10 09:17:54

RT，之前好像看到了一个贴可以两倍空间建树（并不是动态开点），大致是一个点的左右儿子是 mid * 2,mid * 2 + 1，其中 mid 是这个点的区间的中点。

求证明 or 证伪

by dyyzy @ 2024-08-10 09:36:00

@TankYu 感觉不太行，最后一行可能会有空余，节点数最多为 2N，故总结点数最多为 4N

by TankYu @ 2024-08-10 09:45:36

@dyyzy 细说？

by sdyzpf @ 2024-08-10 09:49:19

@TankYu 正确的

by dyyzy @ 2024-08-10 09:57:33

@TankYu 最后一行节点长度均为 1，把最后一行开满需要 2N 个节点。极限情况最后一行可能只有一个节点，此时倒数第二行一个节点长度为 2，其余长度均为 1，近似有 N 个节点，根据二叉树的性质得总结点数近似为 4N

by TankYu @ 2024-08-10 09:58:14

@dyyzy 最后一行为啥有 2n 个节点

by sdyzpf @ 2024-08-10 10:03:02

@TankYu 首先 2mid 显然是 2N 级别的，所以只要证明线段树节点标号不重复就行了。

另一种情况是是 $L+R+1=l+r+1$ 且 $L+R$ 为偶数。在线段树上，仅有 $L=R=l=r-1$ 时满足条件。而 $L=R$ 为叶子节点没有儿子，所以编号也不冲突。

by dyyzy @ 2024-08-10 10:03:19

@TankYu 倒数第二行结点长度为 1，有n个节点，最后一行节点数为倒数第二行的两倍，故有2n个节点

by TankYu @ 2024-08-10 10:03:42

@sdyzpf orz，感谢

by TankYu @ 2024-08-10 10:05:01

@dyyzy ? 你在说啥？

最后一行不是叶子吗

by sdyzpf @ 2024-08-10 10:08:10

@sdyzpf 救命，打错了。

| 下一页