arraysmemorydata-structurestreesegment-tree

How is the memory of the array of segment tree 2 * 2 ^(ceil(log(n))) - 1?

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 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 .

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?

Solution

  • What is happening here is, if you have an array of n elements, then the segment tree will have a leaf node for each of these n entries. Thus, we have (n) leaf nodes, and also (n-1) internal nodes.

    Total number of nodes= n + (n-1) = 2n-1 Now, we know its a full binary tree and thus the height is: ceil(Log2(n)) +1

    Total no. of nodes = 2^0 + 2^1 + 2^2 + … + 2^ceil(Log2(n)) // which is a geometric progression where 2^i denotes, the number of nodes at level i.

    Formula of summation G.P. = a * (r^size - 1)/(r-1) where a=2^0

    Total no. of nodes = 1*(2^(ceil(Log2(n))+1) -1)/(2-1)

    = 2* [2^ceil(Log2(n))] -1 (you need space in the array for each of the internal as well as leaf nodes which are this count in number), thus it is the array of size.

    = O(4 * n) approx..

    You may also think of it this way, Let the below be the segment tree:

        10
   /  \
  3    7
 /\    /\
1  2  3  4

    If the above is you segment tree, then you array of segment tree will be: 10,3,7,1,2,3,4 i.e. 0th element will store the sum of 1st and 2nd entries, 1st entry will store the sum of 3rd and 4th and 2nd will store the sum of 5th and 6th entry!!

    Also, the better explanation is: if the array size n is a power of 2, then we have exactly n-1 internal nodes, summing up to 2n-1 total nodes. But not always, we have n as the power of 2, so we basically need the smallest power of 2 which is greater than n. That means this,

    int s=1;
for(; s<n; s<<=1);

    You may see my same answer here