
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. 