JOIN
 Revision History
 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 My Post History  |  My Watches  |  User Settings Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Error in LCA solution? Revision History (1 edit)
 Error in LCA solution? In the article's "Another easy solution in " 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.Updated on 10/06/2015: Never mind, the original version is correct.
 Error in LCA solution? In the article's "Another easy solution in " 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.