qndmx
by 咕咕咕派 @ 2020-08-03 10:39:08
保险？
by 血色黄昏 @ 2020-08-03 10:39:26
@[血色黄昏](/user/220426) 啊这，，但是二倍完全够了啊
by zjrdmd @ 2020-08-03 10:39:54
叶子节点乘2就炸了？
by 血色黄昏 @ 2020-08-03 10:40:08
@[血色黄昏](/user/220426) 叶子节点不是可以不用往下递归了吗/yiw
by zjrdmd @ 2020-08-03 10:40:48
`叶节点*2=>Runtime Error`
by 咕咕咕派 @ 2020-08-03 10:41:04
@[zjrqwq](/user/174897) 判断这个是不是叶节点呢………………判断就要`*2 *2+1`了吧……
by 咕咕咕派 @ 2020-08-03 10:41:38
如果用指针的话开2倍就行了
by Guoyh @ 2020-08-03 10:42:09
@[咕咕咕派](/user/344811) 判断$l==r$不就行了吗（逃
by zjrdmd @ 2020-08-03 10:42:17
一般线段树开 $4\times n$ 的空间其原因在于：线段树是一颗完全二叉树。以下是拙劣的证明：
由于线段树深度为 $\ulcorner \log_{2} n\urcorner$ 所以一共就有 $2^{\ulcorner \log_2 n \urcorner+1}-1$ 个节点， $\frac{2^{\ulcorner \log_2 n \urcorner+1}-1}{n}$ 的最大值在 $n=2^k-1$ 是取到，所以
$$
\frac{2^{\ulcorner \log_2 n \urcorner+1}-1}{n}=\frac{2^{\log k+2}-1}{2^k-1} = \frac{2^k \times 4-1}{2^k-1} = 4+ \frac{3}{2^k-1}
$$
所以一般线段树开四倍空间是为了安全。而熟练以后就可以尝试使用动态开点线段树。
by JK_LOVER @ 2020-08-03 10:42:18