No. of nodes in a segment tree.

help
, ,
1

No. of nodes in a recursive segment tree of an array of size n is 2n-1.
But still choosing 2n- 1 as the size of segment tree gives a segmentation fault, and I have seen it in many places that it’s recommended to use size of segment tree as 4n. But why?

Can someone clarify on this?

2

@pshishod2645 , you can have a look to this link for a formal proof

1 Like
3

Thanks @aman_robotics

4

@pshishod2645 , If you like to build memory efficient program then you can build segment tree in iterative format. Then it will never use more than 2N memory and if you also want to have lazy propagation then it will require a total of 2N + N = 3*N memory ( extra N for lazy array ). :slight_smile:

5

Iterative version of segment tree is clear to me, I was just having a doubt about it’s recursive version.