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

general
, ,
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
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?

2

What is happening here is, if you have an array of n elements, then the segment tree will have leaf a node for each of these n entries. Thus, we have n leaf nodes and thus, (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 G.P.
where 2^i denotes, the number of nodes at level i.

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

Total no. of nodes = 2*(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 this way, is the segment tree is this:

   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 3 and 4th and 2nd will store the sum of 5th and 6th entry!!

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

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

If in case you are confused about the height thing, refer this.

2 Likes
3

Isn’t there a contradiction? As in first it has been mentioned that the total no. of nodes is 2*(n-1).Next it is said that the total no. of nodes is 2* 2 ceil(Log2(n)) -1(I understood the explanation behind that). But aren’t we allocating extra memory by considering 2* 2 ceil(Log2(n)) -1 when n is not a power of 2. Is it right to assume that a segment tree requires 2* n-1 array size for all n since 2* n-1 is the total no. of nodes for a full binary tree and that is what is required in a segment tree. Is that right? If not what is the purpose behind allocating 2* 2 ceil(Log2(n)) -1.

4

Also I edited the part where they wwere taking 22 ceil(log2(n)) as the memory and changed it to 2 n-1. There was no difference in the output and no runtime error.