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 Another easy solution in
 Another easy solution in | Reply This complete tutorial on RMQ and LCA is excellent! I have a quick implementation question on the query method of the dynamic programming approach in the "Another easy solution in " approach:In the query(...) method before we get to the last piece of the code shown below (from the tutorial), it is made sure that p and q are on the same level if they already are not. Also i understand that T[p], is tree parent of p i.e. the immediate parent in the tree.If that's the case then i think in the implementation the code below needs an else part to actually move up a level to get closer to the common parent even when P[p][i] != -1 and P[p][i] == P[q][i] so we can return T[p] in the end before returning. //we compute LCA(p, q) using the values in P for (i = log; i >= 0; i--) if (P[p][i] != -1 && P[p][i] != P[q][i]) p = P[p][i], q = P[q][i]; //move closer to the common parent else if(P[p][i] != -1 && P[p][i] == P[q][i]) p = P[p][i], q = P[q][i];//In the end we can return tree parent of the nodereturn T[p];Please correct me if i am wrong or missing something.
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Another easy solution in Previous Thread  |  Next Thread