关于n=2^k+1的情况需要的数组空间

Question

令n=5,只需要1+2+4+8=15=3n的存储空间即可。不需要4n,因为令蓝色部分为2n是在n=2^k的情况下，当n=2^k+1的时候蓝色部分不再等于n，因此红色部分也不再等于2n.

Answer 1

何时才能成大佬 2019-10-06 14:56:29

/*

* 对于满二叉树（设根节点所在的层为第1层）来说

* 第i层有 2^(i-1)个元素

* 前i层共有 2^i-1个元素

* 前i-1层共有 2^(i-1)-1个元素

* 故：第i层的元素个数=前i-1层共有的元素个数+1

* 

*假设区间里有n个元素

* 第一种情况：n=2^k (k是正整数)

* 此时开辟的满二叉树的空间大小为：n+(n-1)=2n-1

* 

*第二种情况：n≠2^k (k是正整数)

*此时假设2^p < n < 2^q  且q=p+1  (p、q都是正整数)

*此时开辟的满二叉树的空间大小为： 2^q+2^p+(2^p-1) =2^(p+1)+2^p+2^p-1

* =(2^p)*2+2^p+2^p-1

* <n*2+n+n-1

* =4n-1

* 

* 

* 因为2n-1 < 4n-1

* 所以对于n个元素,需要开辟4n-1个空间

* */

Answer 2

liuyubobobo 2018-05-19 16:30:26

对于n=5的情况，你是对的：）

首先，在线段树中，需要4n的存储空间，这个4n是一个上界，这个上界不是对所有的n的取值都是“紧”的。但是他是一个对所有n都成立的上界。但是3n不是。

依然以n=2^k+1的情况为例，当k=3，即n=9的时候，我们就需要1 + 2 + 4 + 8 + 16 = 31的存储空间，此时3*n=27 < 31，3n的空间是不够的。有兴趣可以尝试多验证几个k的值。事实上，可以数学的证明出，当k >= 3时，3n的空间都是不够的，有兴趣也可以尝试自己数学证明一下：）

• 不知所措_Kevin #1

  老师，我觉得4n有些浪费了啊。当n=2^k+j时，是不是取2^（k+2）个比较好。

• liuyubobobo 回复 不知所措_Kevin #2

  赞！但是这样还要反推一下k的值，在大多数情况下，线段树的实现，使用4n的存储空间是没有问题的。但你给出的上界确实更“紧”：）