通常使用一维数组来存储线段树,因为线段树是一个完全二叉树,假设该线段树存储的区间为 $\left[ 1,n \right]$,则我们可以计算得到一个线段树存储空间的上界
该线段树倒数第二层的节点数目小于 $n$,由于这个树是一个完全二叉树,其叶子节点的数目小于 $2n$,又完全二叉树有性质 $2n_{0} = N + 1$,所以 $2n_{0} - 1 = N < 4n$,所以我们可以得知,线段树的节点总数 $N$ 小于 4 倍的区间长度 $n$,所以我们在开空间的时候倾向于开 $4n$ 大小的空间存储线段树的节点