Segment Trees Doubt.!

I am trying to learn Segment Trees from the following resource.

I tried building the segment tree first. However I am facing a doubt. When I use the array as 1,2,3,4,5,6 to build my segment tree I noticed that the tree array has value 0 at index 9 and 10(garbage values). Since I declared the tree array of a larger size and tree has only 11 nodes there are 2 indexes missing and are not calculated in the code. (At index 2 it becomes constructSTUtil(arr,2,2,st,4) and from there it does not calculate the values of indexes 9 and 10)

Is this a wrong code at the link above or am I missing something.!

Code on Ideone:

Why is the last element in the tree array 0? The tree should have 11 nodes and I have put the limits accordingly while printing out the tree array.

paste/link the code

Few sources which made me comfortable with segment tree


These links have very good explanation go through them in order, geeksforgeeks break the segments tree into different functions and it gets complicated to understand.

1 Like

The best segment tree explanation -

It also has various links to other tutorials and problems.

1 Like

@ashwanigautam I have edited my question . Check it now.

Yes node 9 and 10 will be empty because, 2x4+1 = 9 and 2x4 + 2=10, and it the segment tree that will generate after the code runs

![alt text][1]

I guess the image is okay to make your query clear

1 Like

Yes I have the same image in front of me. :slight_smile:

But my question is Will this not affect the various operations that I do on this segment tree array like updating the value and finding the queries.?

No those values won’t get accessed and you’re seeing 0 because new int[xyz] initialises and sets arr to 0 that is all cells are 0 until modified, you can use memset to clear it to -1 and you’ll see it’ll stay -1 and cell 9 and 10 won’t change after the segment tree is created because when node 4 of segment tree gets updated to 2, it doesn’t break it into two halves ie 9 and 10, since ss=se=2 ie if block of your code gets executed. So node 9 and 10 won’t be accessed nor affected.

yes i went through it is really great