Segment tree size

#1

prateek bhaiya says size of segment tree should be 4n+1
shouldnt it be only 2n + 1??

#2

@shameek.agarwal hey, Let’s take the example of having the length of the array that you’re creating the segment tree as a power of 2 .

length of array, len = 2^xlen=2
x

Now in this case the number of nodes in its segment tree is 1 + 2 + 4 … 2^x = 2^{x+1} -11+2+4…2
x
=2
x+1
−1

Therefore number of nodes in segment tree = 2*number\ of\ leaf\ nodes2∗number of leaf nodes (Excluded the minus one since it’s just a constant)

Now let’s take the case when lenlen is not a power of 2
In this case the segment number of leaf nodes = 2^{log(len)+1}2
log(len)+1

Therefore total number of nodes in the segment tree = 2*number\ of\ leaf\ nodes2∗number of leaf nodes = 2 * 2^{log(len)+1}2∗2
log(len)+1
= 2^{log(len)+2}2
log(len)+2
= 4 * len4∗len

#3

@shameek.agarwal also, 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…

1 Like
#4


can u pls help me with this problem??
my code : works fine with the testcases given
would be glad if you could help
(EDIT 1: IT WORKED ON MAKING THE ARRAY GLOBAL)

#5

@shameek.agarwal ,hey please is question me doubt raise krdo I will explain you as I am notable to see the content.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.