bakuganmaster's blog

Segment tree
By bakuganmaster, 12 years ago, In English

Hi guys :)) https://www.hackerrank.com/challenges/task-scheduling

I'm trying to solve this problem using segment tree.

I have an array of numbers , I need to add X from index L to R , and also I have to find maximum member of an array from index L to R (not the same L and R);

n---number of elements of an array; The problem I have here is that I want to answer and update this queries in O(lg(n)) time (lg^2(n) will be also okay ) , not O(n);

Can anyone tell me what is an approach to solve this problem ?

P.S in hackkerrank problem R is always N ....

thanks in advance )

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

»
12 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it 
int add( int k , int b , int e , int L , int R , int X ){
	if( R < b || e < L ) 
		return seg[k]+lazy[k];
	if( L <= b && e <= R ){
		lazy[k] += X ;
		return seg[k]+lazy[k];
	}
	seg[k]=max( add( 2*k , b , (b+e)/2 , L , R , X ) , add( 2*k+1 , (b+e)/2+1 , e , L , R , X ) );
	return seg[k]+lazy[k];
}
→ Reply