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?