JOIN
 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 | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Dynamic RMQ using Segment Tree
 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(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)
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Dynamic RMQ using Segment Tree Previous Thread  |  Next Thread