线段树（区间树）

一棵二叉树的每个节点是存储的一个区间或者说是一个线段相应的信息，这里说的相应的信息不是指把这个区间内的元素都存进去，我们以求和为例，每一个节点相应存储的是这个节点所对应区间的数字的和。

线段树一定是满二叉树吗？不一定，这里是因为8恰好是2的三次方，刚好可以构成一颗满二叉树。

根节点代表整个线段，左孩子代表根节点线段的前半段，右孩子就是根节点线段的后半段。直到到了叶子节点，叶子节点只表示一个元素。 如果现在数组中有十个元素，相应的线段树就不是二叉树了，如下：

注意：线段树不是完全二叉树，但线段树是平衡二叉树，当然堆也是平衡二叉树。

关于平衡二叉树和完全二叉树的概念，由于堆是完全二叉树，所以我在堆和优先队列中就详细介绍了，有兴趣的小伙伴可以看一下。

什么是完全二叉树呢？完全二叉树就是把元素按照树的形状一层一层的放，直到放完为止，即把元素顺序排成树的形状。堆也是一棵平衡二叉树，因为完全二叉树一定是平衡二叉树，什么是平衡二叉树？即对于整棵树来说，最大深度和最小深度的差值不能大于1，因此平衡二叉树一定不会退化成链表。满二叉树是特殊的完全二叉树。

线段树虽然是平衡二叉树，不是完全二叉树，但是线段树任然可以使用数组来表示，如果区间有n个元素，用数组表示需要有多少个节点呢？对于满二叉树来说，0层有一个节点，1层有两个节点，2层有四个节点，3层有8个节点，则在h层一共有2 ^h -1个节点(大约是2 ^h 个)，最后一层(h-1层)，有2 ^(h-1) 个节点， 即满二叉树最后一层的节点数大致等于前面所有层节点之和。

为什么最坏情况是如果n=2 ^k +1，需要4n的空间呢？因为如果n=2 ^k ，就是刚好可以构成一课满二叉树，这时只需要2n的区间就好了，这是最好的情况，数组中每个空间都被使用，最坏的情况就是在满二叉树的情况下多出一个节点，由于我们数组是存储的相当于满二叉树的节点个数，所以需要数组2n+2n=4n的空间，但实际上这2n的空间中只有一个节点是有效数据，其他2n-1的空间都是浪费掉的。

所以为了考虑到最坏的情况，如果区间有n个元素，数组表示需要4n的空间，由于我们的线段树不考虑添加元素，即区间固定，使用4n的静态空间就可以了。