Binary Lifting algorithm

This week’s LeetCode 193 contest has an interesting question which is related to LCA. It can be solved by using the “Binary Lifting algorithm”.

5456. Kth Ancestor of a Tree Node

I have collected several related articles that introduce this algorithm (some are in Chinese). Please check those articles or videos from the reference.

Based on one pretty nice video from [5], we can have the solution as below:

class TreeAncestor {
    vector<vector<int>> p;
public:
    TreeAncestor(int n, vector<int>& parent) 
    {
        vector<vector<int>> p(n, vector<int>(32, -1));
        for(int i=0;i<n;++i)
            for(int j=0;j<32;++j)
            {
                if(j==0) p[i][j] = parent[i];
                else if(p[i][j-1]!=-1) p[i][j] = p[p[i][j-1]][j-1];
                else break;
            }
        this->p = p;
    }
    
    int getKthAncestor(int node, int k) 
    {
        for(int j=0; j<32;j++)
        {
            if (node==-1)break;
            if((k>>j)&1)node = p[node][j];
        }
        return node;
    }
};

Although this solution can get AC. It is not correct.

example from HERE.

It fails in this test case. This test case is modified from the example shown above. If we change the location of 1,2 and 5, 6, we will generate the following example.

["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,5,5,6,6,0,0]],[1,1],[3,2],[4,3]]

The correct code should change the order to the two-layer loops i and j.

The correct code is here:

class TreeAncestor {
    vector<vector<int>> p;
public:
    TreeAncestor(int n, vector<int>& parent) 
    {
        vector<vector<int>> p(n, vector<int>(32, -1));
        for(int j=0;j<32;++j)
            for(int i=0;i<n;++i)
            {
                if(j==0) p[i][j] = parent[i];
                else if(p[i][j-1]!=-1) p[i][j] = p[p[i][j-1]][j-1];
            }
        this->p = p;
    }
    
    int getKthAncestor(int node, int k) 
    {
        for(int j=0; j<32;j++)
        {
            if (node==-1)break;
            if((k>>j)&1)node = p[node][j];
        }
        return node;
    }
};

A simpler problem based on a binary tree.

See [7]

Reference

[1]https://blog.csdn.net/ccDLlyy/article/details/77509502

[2]https://www.luogu.com.cn/blog/morslin/solution-p3379

[3]https://ksmeow.moe/suffix_array/

[4]https://www.bilibili.com/video/BV19s411z77x?from=search&seid=390433741177245858

[5] https://youtu.be/XMM-lG6JqSY

[6]https://cp-algorithms.com/graph/lca_binary_lifting.html

[7]https://medium.com/@jim.morris.shen/basic-binary-tree-problems-b5593407f777?source=friends_link&sk=69df21a4b7723a691018d7afe4908398