线段树的空间复杂度是多少？节点数计算存疑

首先纠正一个小误区：拥有n个叶子节点的完美二叉树，总节点数是2n-1（比如n=4时，总节点7=2*4-1），不是2n+1，不过这不影响核心疑问的解答。

两种说法的本质是场景不同：

• 2n相关的计算：只适用于n是2的整数次幂的情况。此时线段树是完美二叉树，总节点数刚好是2n-1，和2n的量级一致。如果把非2的幂的n补到最近的2的幂，此时所需节点数也不会超过2*(2^ceil(log2n))，但这个值需要手动计算，不够省心。

• 4n的空间推荐：这是实践中通用的安全上限。当用数组存储线段树时，为了方便用索引计算左右孩子（左孩子=2i，右孩子=2i+1），我们需要保证数组能容纳所有节点。数学上可以证明，不管n是多少，线段树的总节点数一定小于4n。比如n=5时，实际节点数11<20=45；n=7时，实际节点数13<28=47。直接开4n的数组，不用纠结n是不是2的幂，不会出现空间不足的问题，属于“懒省事但绝对安全”的做法。

你觉得非完美二叉树节点数比完美的少，这个逻辑是对的，但空间复杂度描述的是最坏情况下的上限，4n是一个能覆盖所有n的上限，而且和O(n)的复杂度等价，所以很多资料会直接说空间复杂度是O(4n)。

内容的提问来源于stack exchange，提问作者Sandeep Mishra