Thank you. That clears it up. I have read at multiple places that size of Segment Tree in the worst case can go upto 4 times the space of array, may be I have to re-look into that.
2 Likes
Below I’ll discuss the space requirement for an array based implementation of the segment tree.
Let’s consider the base array A[] to be of size N.
All the array elements are placed in the leaf nodes. So, the number of leaf nodes is N.
What’s the maximum size of the segment tree?
We consider the case where the last level contains at least one of the leaf nodes.
Then, the tree would have the following distribution of nodes:
level | number of nodes
0 | 2 ^ 0
1 | 2 ^ 1
2 | 2 ^ 2
. | .
. | .
. | .
n | 2 ^ n
. . . where, 2^n is the lowest power of 2 which is not less than N.
So, the size of the segment tree is the sum of the G.P.
\approx 2 ^ {\lceil log_2 N\rceil + 1} - 1
\approx 2 ^ {\lceil log_2 N\rceil + 1}
\approx 2 ^ {log_2 N + 2}
= 2 ^ {log_2 N} \times 2 ^ 2
= N \times 4
= 4N
Please correct me if I went wrong anywhere. Thank you. 
5 Likes
Give me a treat? It’s because of my post 