Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Error in LCA <O(N log N), O(log N)> solution? | Reply
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.