What is the max size that a segment tree can have? And why?
Segment tree size
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…
if you want to ask something about this feel free to ask
i hope this helps
if yes show your response with 
and don’t forgot to mark doubt as resolved
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.