Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Another easy solution in <O(N logN, O(logN)> | 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 <O(NlogN), O(logN)>" 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 node
return T[p];

Please correct me if i am wrong or missing something.