binary lifting

in a rooted tree, how to find the th ancestor of a node?

straightforward approach

#

if we have the list parent ¹, we can travel times upward using the list.

def kth_ancestor(k, v):
    for _ in range(k):
        v = parent[v]
    return v

what is the time complexity? suppose the tree has node, the algorithm runs in time, bounded by the height of tree.

what if we have queries? then the algorithm runs in time. if and is large (e.g. ), the algorithm is too slow. can we do better? yes, introducing binary lifting.

using binary lifting

#

suppose we want to find the th ancestor of a node, we have to travel up steps upward in the previous approach. if we somehow know the values of the th ancestors of each node, we can travel up in steps via the st, th, nd, th ancestors.

this is the idea of binary lifting. we first pre-calculate the table of values of the th ancestors of each node. then we can answer each query using the table.

the time and space complexity of the pre-calculation is and each query requires time, resulting time for the queries.

implementation notes

#

here is the implementation of the precalculation.

def precalc():
    up = [[0] * LOG for _ in range(n)]

    for i in range(n):
        up[i][0] = parent[i]
    for j in range(1, LOG):
        for i in range(n):
            up[i][j] = up[up[i][j - 1]][j - 1]

    return up

the following implementation assumes all nodes have a parent of a node with a smaller value, i.e. parent[i] < i.

def precalc():
    up = [[0] * LOG for _ in range(n)]

    for i in range(n):
        up[i][0] = parent[i]
        for j in range(1, LOG):
            up[i][j] = up[up[i][j - 1]][j - 1]

    return up

then we can find the th ancestor as follow.

def kth_ancestor(k, v):
    for j in range(LOG):
        if (k >> j) & 1:
            v = up[v][j]
    return v

sometimes we have to return -1 if the th ancestor does not exist. then the above implementation will not work since when v travels to the root, it will stay at the root via the self-loop. to avoid this, we need the list depth and add a check before travelling.

def kth_ancestor(k, v):
    if depth[v] < k:
        return -1

    for j in range(LOG):
        if (k >> j) & 1:
            v = up[v][j]
    return v

applications

#

lowest common ancestor

related problems

#

• CSES 1687 - Company Queries I
• CSES 1750 - Planets Queries I

further readings

#

Binary Lifting and LCA

references

#

Binary Lifting (Kth Ancestor of a Tree Node)

footnotes

#