title: How is the memory of the array of segment tree 2 * 2 ^(ceil(log(n))) - 1?
body: <p>The link: <a href="http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/" rel="noreferrer">http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/</a>. This is the quoted text:</p>
  
  <blockquote>
    <p>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
    <img src="https://latex.codecogs.com/gif.latex?%5C(2&space;*&space;2%5E%7B%5Cleft%5Clceil%5Clog&space;_%7B2%7D&space;n%5Cright%5Crceil%7D-1%5C)" title="\(2 * 2^{\left\lceil\log _{2} n\right\rceil}-1\)" />.</p>
  </blockquote>
  
  <p>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 the reasoning behind this. If this is false, then what is the correct value?</p>