The link: http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/. This is the quoted text:
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
corresponding node. All levels of the
constructed segment tree will be
completely filled except the last
level. Also, the tree will be a Full
Binary Tree because we always divide
segments in two halves at every level.
Since the constructed tree is always
full binary tree with n leaves, there
will be n-1 internal nodes. So total
number of nodes will be 2*n – 1.
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
2**2 ^(ceil(log(n))) - 1.
How is the memory allocated(last line of the above para) that much? How are the parent and child indexes stored in the code if it is correct? Please give reasoning behind this. If this is false then what is the correct value?