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

  1. https://www.youtube.com/watch?v=ZBHKZF5w4YU
  2. https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/
  3. http://ayurjain.blogspot.in/

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

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

paste/link the code

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

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