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

Автор fabianun, история, 8 лет назад, По-английски

Hello everyone,

I am doing some segment tree problems and I get stuck in this

http://www.spoj.com/problems/RPLN/

I just use a recursive implementation of segment tree and always get time limit. This is my code

https://ideone.com/PRIfI5

So, can someone help me to improve the speed of my code (the segment tree) but keep doing with recursion (do not go with iterative implementation please.)

Thank you in advance.

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

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

You can use 2 function one to build tree and other to query over the tree to find answer over the range A to B.

Code for buildtree :

void buildtree(int node,int b,int e){ if(b==e) M[node]=a[b]; else{ buildtree(2*node,b,(b+e)/2); buildtree(2*node+1,(b+e)/2+1,e); M[node]=min(M[2*node],M[2*node+1]); } }

Code for query from i to j:

int query(int node,int b,int e,int i,int j){ int p1, p2;

if (i>e || j<b) return inf;

  if (b>=i && e<=j) return M[node];

  p1 = query(2*node,b,(b+e)/2,i,j);
  p2 = query(2*node+1,(b+e)/2+1,e,i,j);

  return min(p1,p2);

}