OIWIKI 关于线段树的数组长度计算,不能理解
  • 板块学术版
  • 楼主RGYZ
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/1/23 11:19
  • 上次更新2023/10/28 11:28:42
查看原帖
OIWIKI 关于线段树的数组长度计算,不能理解
549289
RGYZ楼主2022/1/23 11:19

OIWIKI 上关于线段树的数组长度计算,是这样写的:

线段树的深度是 logn\left\lceil\log{n}\right\rceil,在堆式储存下叶子节点(包括无用的叶子节点)数量为 2logn2^{\left\lceil\log{n}\right\rceil} ,又由于其为一棵完全二叉树,则其总节点个数 2logn+112^{\left\lceil\log{n}\right\rceil+1}-1

————上边理解没问题

你懒得计算的话可以直接把数组长度设为 4n4n ,因为 2logn+11n\dfrac{2^{\left\lceil\log{n}\right\rceil+1}-1}{n} 的最大值在 n=2x+1(xN+)n=2^{x}+1(x\in N_{+}) 时取到,此时节点数为 2logn+11=2x+21=4n52^{\left\lceil\log{n}\right\rceil+1}-1=2^{x+2}-1=4n-5

————不能理解,第2段的“最大值在 n=2x+1(xN+)n=2^{x}+1(x\in N_{+}) 时取到”,是怎么得出来的呢?为什么要除以n呢?各路大神能帮忙讲解一下吗?

2022/1/23 11:19
加载中...