JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Error in LCA <O(N log N), O(log N)> solution? Revision History (1 edit)
Error in LCA <O(N log N), O(log N)> solution?
In the article's "Another easy solution in <o logn o>" of LCA, it uses dynamic programming, with the following recursion:

When j = 0, then: P[i] [j] = T[i];
When j > 0, then: P[i] [j] = P[ P[i] [j-1] ] [j-1]

Since P[i] [j] is the (2^j)-th ancestor of i, when j > 0, I think P[i][j] should be:

P[i] [j] = P[ P[i] [j-1] ] [1]

Please correct me if I am wrong. Thank you.</o>

Updated on 10/06/2015:
Never mind, the original version is correct.
Error in LCA <O(N log N), O(log N)> solution?
In the article's "Another easy solution in <O(N logN, O(logN)>" of LCA, it uses dynamic programming, with the following recursion:

When j = 0, then: P[i] [j] = T[i];
When j > 0, then: P[i] [j] = P[ P[i] [j-1] ] [j-1]

Since P[i] [j] is the (2^j)-th ancestor of i, when j > 0, I think P[i][j] should be:

P[i] [j] = P[ P[i] [j-1] ] [1]

Please correct me if I am wrong. Thank you.