fabianun's blog

Some help with time limit.
By fabianun, history, 8 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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);

}

→ Reply