Binary Lifting(DP on trees). Many of you must have heard about binary lifting and must have been intimidated by the thought of it(even i was). Then i thought to learn about the concept and write a blog for the same making things easier for the community :) Binary lifting is DP approach to find Kth ancestors of a node in a tree (or a graph).

If we talk about the brute force approach — Lets say we are given Q queries and we need to find Kth ancestor of every query, we can easily make a parent array for every node if not already given, or run a DFS and fill the parents. To find the Kth ancestor we can just do -

for(auto q:Q)  
{  
    //q={node,k};  
    int node = q.first;  
    int k = q.second;  
    int kthNode = node;  
    for(int i=0;i<K;i++)  
    {  
        kthNode = parent[kthNode];  
    }  
    cout<<kthNode<<"\n";  
}

Given a skew tree or if we look out for constraints 1<=k<n<=5*10⁴ and 1<=Q.size()<=n, our solution would be of time complexity O(Q*K) =~ O(N²). Thats where binary lifting comes into play. Binary lifting can be summed up into 2 phases - the pre-computation and the query calculation.

Pre-computation

The core concept of binary lifting is to precompute information about each node in the tree, which allows for fast queries. This information is stored in a 2d table. Binary lifting precomputes the ancestors of each node at specific powers of 2 because every number can be written as sum of powers of 2. when we define the array vector<vector<int>>up; the state is defined as up[i][j] → 2^j th ancestor of i^th node So, the up[i][0] means 2^⁰ th parent of i^th node, i.e 1st parent (original parent) this would be the base case. We can populate the table by -

for(int i=0;i<n;i++)  
{  
    up[i][0]=parent[i];  
}

Now moving on to the main computation part We can define LOG as the max log2 of the constraints, because at the worst case we need to check all the bits of a number and the max number of bits in a number is log2(n) This is the intuition - processing queries in logN time rather than N. Moving to the code → initialize the up table by -1.

for(int j=1;j<LOG;j++)  
{  
    for(int i=0;i<=n;i++)  
    {  
        if(up[i][j-1]!=-1)  
        up[i][j] = up[up[i][j-1]][j-1];  
        else  
        up[i][j]=-1;  
    }  
}

Now the relation up[i][j] = up[up[i][j-1]][j-1]; can be seen as →if we want to jump (2^x) places , we can jump (2^x-1) places two times, because (2^x-1) + (2^x-1) = (2^x). So in the relation up[i][j] = up[up[i][j-1]][j-1]; , first we are jumping to 2^j-1 places , then from that node(up[i][j-1]) we jump further 2^j-1 places. If its a -1, there is no ancestor of the given node at that place.

Query calculation

Le need to process the k jump as powers of 2. Lets say 5th ancestor → binary representation of 5 = 101, in the table we have answers of 2^i th ancestors so 5 can be rewritten as 2² + 2⁰, so we calculate answer according to the set bit. The below code is self explanatory -

int getKthAncestor(int node, int k) {  
    if(k==1)  
    return up[node][0];//returning the parent  

    int ans=node;  
    for(int j=0;j<=LOG;j++) //O(log(N))  
    {  
        if(k&(1<<j))//checking the set bit  
        {  
            ans=up[ans][j];  
            if(ans==-1)  
            break;  
        }  
    }  
    return ans;  
}

If we have a very large value of k, lets say 10⁹, we can easily process that by using binary lifting. The overall time complexity of the technique would be NlogN for precomputation and logN to find the answers to the query i.e. O(NlogN + logN), which is much better than O(N²) for large testcases as log2(1e9)=~30.

Below is the overall code for the algorithm-

class TreeAncestor {
public:
 vector<vector<int>>up;//table to calculate ancestors, N x log(N)
    //up array is defined as up[i][j] --> 2^j th ancestor of ith node
    int LOG;
    TreeAncestor(int n, vector<int>& parent) {
        LOG = ceil(log2(1e9)); //max value of `k` according to constraints
        up.resize(n,vector<int>(LOG+1,-1));
        for(int i=0;i<=n;i++)
        {
            up[i][0]=parent[i];//2^0, i.e first ancestor of a node is its parent
        }   

        for(int j=1;j<LOG;j++)
        {
            for(int i=0;i<=n;i++)
            {
                if(up[i][j-1]!=-1)
                up[i][j] = up[up[i][j-1]][j-1];
                else 
                up[i][j]=-1;

            }
        }
    }

    int getKthAncestor(int node, int k) {

  if(k==1)
  return up[node][0];


  int ans=node;
  for(int j=0;j<=LOG;j++) //O(log(N))
  {
   if(k&(1<<j))
   {
    ans=up[ans][j];
    if(ans==-1)
    break;

    k-=(1<<j);
   }
  }
  return ans;
    }
};

Related problems —

https://leetcode.com/problems/kth-ancestor-of-a-tree-node/description/

https://cses.fi/problemset/task/1750

https://cses.fi/problemset/task/1687