线段树：开多大？

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

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

普通线段树

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

结论：$T=4n$，用 N << 2 | 1。

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

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

动态开点线段树

假设线段树需要维护区间 $[1,n]$，总共要处理 $m$ 次更新和查询（千万注意是两者之和！！！）。

结论：$T\lt40m$，用 (M << 5) + (M << 3)。

最坏情况下深度为 $\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$。

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