Блог пользователя NiVeR

Learning Segment Trees
Автор NiVeR, 12 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить