NiVeR's blog

Learning Segment Trees
By NiVeR, 12 years ago, In English

Hi everyone, I am doing my first steps into segment trees. So I have coded a simple code( http://pastebin.com/GAUJHpZb ) for RMQ, for finding the minimum element in a range. But It doesn't seem to be working. Can someone check it, please?

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think you should rewrite the query function. When asking the minimum value on a segment, we need to split the query in two smaller, and then take the minimum value of queries on these two segments, which your code does not do currently.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you mean I am not doing so, I am calling it over (start,mid) and (mid,end)...at least I think so..

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      As also ocozalp mentioned, you need to return the minimum of the results of these two new queries, and return it as a result of the current query. Now only one of them is being returned.

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this block has to be changed

if(l >= start || r >= end)return A[node];

into

if(l <= start && r >= end)return A[node];

also you should change this code block in order to calculate values both for left and right subtrees. ("else" block prevents your program to do so)

if(l <= mid && start <= r )
	res = min(res, query(2*node,start,mid,l,r));
else
	res = min(res, query(2*node+1,mid+1,end,l,r));

you should have a look at topcoder tutorial for segment trees.

→ Reply