OIWIKI 上关于线段树的数组长度计算,是这样写的:
线段树的深度是 ⌈logn⌉,在堆式储存下叶子节点(包括无用的叶子节点)数量为 2⌈logn⌉ ,又由于其为一棵完全二叉树,则其总节点个数 2⌈logn⌉+1−1 。
————上边理解没问题
你懒得计算的话可以直接把数组长度设为 4n ,因为 n2⌈logn⌉+1−1 的最大值在 n=2x+1(x∈N+) 时取到,此时节点数为 2⌈logn⌉+1−1=2x+2−1=4n−5。
————不能理解,第2段的“最大值在 n=2x+1(x∈N+) 时取到”,是怎么得出来的呢?为什么要除以n呢?各路大神能帮忙讲解一下吗?