- Description of LCA
- The use of LCA
- Trivial solution n^2
- Better solutions
- This Project
- Brief overview
- more info here
- Brief overview
- more info here
- Perl for Bender
- C++ for vishkin
- Library with sample drivers
- To do: mpich
We achieve O(n) preprocessing by noticing some important details about trees. Suppose we label a tree using inorder numbering. Then by XOR'ing two nodes, we can find the lowest point of divergence.
But that alone doesn't give us enough information about the parent. We partition the tree into runs with the similar attributes. we then remember the parent of these runs.