# Segment Trees Doubt.!

I am trying to learn Segment Trees from the following resource. http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

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: http://ideone.com/xzurlR

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.

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 - https://www.commonlounge.com/discussion/58e0c0af5d1f487c9942f4625bfd4cc2

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]: https://discuss.codechef.com/upfiles/74606483-0978-45b9-8388-85d22d9d6e7b.jpg

1 Like

Yes I have the same image in front of me.

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

//