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 (oldest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Dynamic RMQ using Segment Tree
 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)
 Dynamic RMQ using Segment Tree | Reply What is dynamic RMQ? How to modify the segment tree code given in the article for dynamic RMQ?
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Dynamic RMQ using Segment Tree Previous Thread  |  Next Thread