JOIN
 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 | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Error in LCA solution?
 Error in LCA solution? | Reply 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.
 Subject Author Date Error in LCA solution? jxiang.sd Jun 23, 2015 at 10:27 AM EDT
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Error in LCA solution? Previous Thread  |  Next Thread