博客

我们首先设区间长度为 n ，线段树高度为 h；先看下面两种情况：

1. n=8
   
   
   
   这种情况比较好，正好是一个满二叉树。
   
   当区间长度为 8 时，该线段树是一个满二叉树，高度 h = 4
   
   也就是
   
   
   
   2

   3

   2^3
   
   
   
   
   
   
   
   2
   
   
   
   
   
   
   
   
   
   
   3
   
   
   
   
   
   
   
   
   
   
   
   
   =8，所以
   
   h =
   
   
   
   l

   o

   g

   2

   n

   log_2 n
   
   
   
   
   
   
   l
   
   
   o
   
   
   
   g
   
   
   
   
   
   
   
   
   
   
   2
   
   
   
   
   
   ​
   
   
   
   
   
   
   
   
   
   
   
   
   n
   
   
   
   
   
   +1
   

2. n=9
   
   
   
   当区间长度为 9 时 ，所以
   
   
   
   l

   o

   g

   2

   9

   log_2 9
   
   
   
   
   
   
   l
   
   
   o
   
   
   
   g
   
   
   
   
   
   
   
   
   
   
   2
   
   
   
   
   
   ​
   
   
   
   
   
   
   
   
   
   
   
   
   9
   
   
   
   
   
   +1 向上取整， 即为 4+1，所以这种情况比较糟糕，不确定第 5 层的节点的位置，所以数组要开大一点： 高度 h =
   
   
   
   l

   o

   g

   2

   n

   log_2n
   
   
   
   
   
   
   l
   
   
   o
   
   
   
   g
   
   
   
   
   
   
   
   
   
   
   2
   
   
   
   
   
   ​
   
   
   
   
   
   
   
   
   
   
   
   
   n
   
   
   
   
   
   +1+1

所以第 n 层 就有 2

^n-1

个节点,因为最后要多开一层，所以是 n+1层，根据等比数列求和

S = (



a

0

a_0







a










0





​















*(1-q

ⁿ

)) / (1 – q)，所以代入 h 结果为