链接:http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/。这是引用的文本:
内存分配了多少(上面段落的最后一行)?如果正确,父索引和子索引如何存储在代码中?请给出其背后的理由。如果这是错误的,那么正确的值是什么?
最佳答案
这里发生的是,如果您有n个元素的数组,则段树将为这n个条目中的每一个都有一个叶节点。因此,我们有(n)个叶节点,还有(n-1)个内部节点。
节点总数= n +(n-1)= 2n-1现在,我们知道它是完整的二叉树,因此高度为:ceil(Log2(n))+1
总数节点数= 2 ^ 0 + 2 ^ 1 + 2 ^ 2 +…+ 2 ^ ceil(Log2(n))//这是一个几何级数,其中2 ^ i表示级别i的节点数。
求和公式G.P. =一个*(r ^ size-1)/(r-1)
其中a = 2 ^ 0
总数节点数= 1 *(2 ^(ceil(Log2(n))+ 1)-1)/(2-1)
= 2 * [2 ^ ceil(Log2(n))] -1(您需要在数组中为内部和叶节点中的每个节点留出空间,这些节点和节点的数量在此数量),因此它是大小的数组。
=约O(4 * n)
您也可能会这样想,让下面成为细分树:
10
/ \
3 7
/\ /\
1 2 3 4
如果以上是您的分段树,则分段树的数组将为:10,3,7,1,2,3,4,即第0个元素将存储第1个和第2个条目的总和,第一个条目将存储第一个和第二个条目的总和第三和第四和第二将存储第五和第六项的总和!
此外,更好的解释是:如果数组大小 n 是2的幂,那么我们恰好具有 n-1 内部节点,总计总计 2n-1 总节点。但并非总是如此,我们将 n 作为2的幂,因此我们基本上需要 2 的最小幂,大于 n 。就是这个意思
int s=1;
for(; s<n; s<<=1);
您可能会看到相同的答案here