Wednesday, September 14, 2011

The beauty of SQRT(N) -- part II

Another good SQRT(N) trick can be applied to Lowest Common Ancestor (LCA) problem.

LCA
This problem consists in identifying the lowest common ancestor given two nodes in a tree. One way is to split the tree vertically in SQRT(H) parts, where H is height of the tree. So for each part, we should store the ancestor situated in the part immediately above. That is easy because the ancestor for each border section is the father of the section (e.g. the node at the frontier).

So assume that the node i, has father F[i], we can pre-compute an array P [1..N] as it follows

if (i is at first level) P[i] = 1   // first level
else if (i is at the border of one of the SQRT(H) partitions than P[i] = F[i]) // border
else (P[i] = P [ F[ i] ])  // any other node

So we have SQRT(H) partitions and the pre computation is linear. We use P for reducing the cost of LCA to SQRT(H) as it follows

while (P[x] != P[y])          // different section
if (L[x] > L[y])     // up with the longest
x = P[x];         // up one section
else
y = P[y];       // up one section

while (x != y)           // same section
if (L[x] > L[y])     // up with the longest
x = F[x];         // take the father
else
y = F[y];
return x;