syxsyxsyx
commented
4 years ago 最后这个证明4n的问题，假如有数组有6([1,2,3,4,5,6])个数，那么放在线段树里面的话，树的高度h(根的高度为1的话)为3才能放下所有的叶子节点数。假如数组有8个数,那么需要h=4才能放下。可以转化为求高为h(最下一层可以填满,不是数组里面的数可以用0填充)的二叉树的节点总数sum,只需要计算这个sum的极限值。sum = 2^(h-1)+2^(h-2) +...+ 2^0，因为是二叉树，h 和n也是有关系的 大概这 lgN = h 。。我感觉这个思路是可以的。。但是我算的极限值是2n，肯定有一个地方我弄错了。。。。。
https://www.desgard.com/algo/docs/part3/ch02/2-segment-tree-combat/
线段树实战要点