JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Dynamic RMQ using Segment Tree | Reply
What is dynamic RMQ? How to modify the segment tree code given in the article for dynamic RMQ?
Re: Dynamic RMQ using Segment Tree (response to post by Phoenix.) | Reply
Might be something like this:

void update(int index,int new_value,int b,int e,int node,int M[MAXIND], int A[MAXN], int N)
{
//below condition will be true only when b==index && e==index
if(b==e)
	{
		A[index]=new_value;
	}
else if(index<b || index >e) //index not in this interval =>discard this interval
	{
		return ;
	}
else  //try for update in left and right son
	{
		update(index,new_value,b,(b+e)/2,2*node,M,A,N);
		update(index,new_value,(b+e)/2 +1,e,2*node+1,M,A,N);
 
	}
//Now if update has made a change in minimum value , change should propogate from interval (index,index) to (0,N-1)
if(node !=1 && A[M[node/2]] >=A[M[node]]) //since ,root doesn't have parent
	M[node/2]=M[node];
}
 
 


And this works in O(lgN)
RSS