Finding ancestors
The $k$th ancestor of a node $x$ in a rooted tree
is the node that we will reach if we move $k$
levels up from $x$.
Let ancestor}(x,k) denote the $k$th ancestor of a node $x$
(or $0$ if there is no such an ancestor).
For example, in the following tree,
An easy way to calculate any value of ancestor(x,k)
is to perform a sequence of $k$ moves in the tree.
However, the time complexity of this method
is $O(k)$, which may be slow, because a tree of $n$
nodes may have a chain of $n$ nodes.
Fortunately, using a technique similar to that
used in Chapter 16.3, any value of ancestor(x,k)
can be efficiently calculated in $O(\log k)$ time
after preprocessing.
The idea is to precalculate all values ancestor(x,k)
where $k \le n$ is a power of two.
For example, the values for the above tree
are as follows:
| x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
ancestor(x,1) | 0 | 1 | 4 | 1 | 1 | 2 | 4 | 7 |
ancestor(x,2) | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 4 |
ancestor(x,4) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
The preprocessing takes $O(n \log n)$ time,
because $O(\log n)$ values are calculated for each node.
After this, any value of ancestor(x,k) can be calculated
in $O(\log k)$ time by representing $k$
as a sum where each term is a power of two.