链接：http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/ http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/。这是引用的文字：
We start with a segment arr[0 . . . n-1]. And every time we divide the current segment into two halves(if it has not yet become a segment of length 1), and then call the same procedure on both halves, and for each such segment, we store the sum in the corresponding node. All levels of the constructed segment tree will be filled except the last level. Also, the tree will be a Full Binary Tree because we always divide segments into two halves at every level. Since the constructed tree is always a full binary tree with n leaves, there will be n-1 internal nodes. So the total number of nodes will be 2n – 1. The height of the segment tree will be ceil[log(n)]. Since the tree is represented using array and relation between parent and child indexes must be maintained, size of memory allocated for segment tree will be
.
内存是如何分配的（上面段落的最后一行）那么多？如果正确的话，父索引和子索引如何存储在代码中？请给出这背后的理由。如果这是错误的，那么正确的值是多少？
这里发生的情况是，如果有一个包含 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.求和公式= a * (r^大小 - 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个条目的总和，第1个条目将存储第1个和第2个条目的总和第三、第四和第二将存储第五和第六条目的总和！
另外，更好的解释是：如果数组大小n是 2 的幂，那么我们正好有n-1内部节点，总结为2n-1总节点数。但并非总是如此，我们有n作为 2 的幂，所以我们基本上需要 的最小幂2这大于n。这意味着，
int s=1;
for(; s<n; s<<=1);
你可能会看到我同样的答案here http://discuss.codechef.com/questions/64305/how-is-the-memory-of-the-array-of-segment-tree-2-2-ceillogn-1