JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Re: Dynamic RMQ using Segment Tree Revision History (1 edit)
 Re: Dynamic RMQ using Segment Tree (response to post by Phoenix.) 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(indexe) //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)
 Re: Dynamic RMQ using Segment Tree (response to post by Phoenix.) 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(indexe) //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 does have parent M[node/2]=M[node]; }     ```And this works in O(lgN)