线段树：开多大？

本文研究线段树的空间问题。

注意： 虽然下面给出了 “空间复杂度”，但是不要按空间复杂度开！要按照 “总结点不超过” 开。下面把需要开的大小记作 $T$。

普通线段树

假设线段树需要维护区间 $[1,n]$。

结论：$T=4n$。

也就是一共有 $n$ 个叶子结点，最好情况下深度为 $\log_2n+1$，最坏情况下深度为 $\log_2n+2$。

所以总结点不超过 $2^{\log_2n+2}=4n$，空间复杂度是 $O(n)$。

动态开点线段树

假设线段树需要维护区间 $[1,n]$，一共要处理 $m$ 次更新。 结论：$T\lt40m$。

最坏情况下深度为 $\log_2n+2$，也就是每次更新最多创建 $\log_2n+2$ 个节点，总结点不超过 $m\log_2n+2m$，空间复杂度是 $O(m\log_2n)$。

然而计算 $\log$ 太麻烦了，我们尝试线性近似：

• 假设 $m\log_2n+2m\le km$，待定 $k$。

• 两边约去 $m$，得 $\log_2n+2\le k$，左边肯定是单调递增的，代入 $n=10^{11}$，$\log_210^{11}+2\approx38.54$，稍微取整一下，取 $k=40$。

  （一般也不太可能遇到 $\gt10^{11}$ 数量级的数据了吧......）

类似地，我们得到下表。$32m$ 和 $40m$ 是常见的取值，别的看个乐就好。

$n\le$	$10^5$	$10^{9}$（__int32 上界）	$10^{11}$	$10^{12}$	$10^{19}$（__int64 上界）
空间估算（节点）	$\lt20m$	$\lt32m$， m<<5	$\lt40m$，(m<<5)+(m<<3)	$\lt42m$	$\lt66m$

可持久化线段树

假设线段树需要维护区间 $[1,n]$，一共要处理 $m$ 次更新。

结论：$T<40m$。

其实和动态开点线段树是差不多一样的。