Binary Lifting

Competitive Programming

What’s this ?

Binary Lifting is a simple computation technique which makes use of 2 simple facts :

  • Any number can be represented as sum of some powers of 2’s
  • Dynamic Programming

I will be using an example problem to demonstrate the binary lifting process . The problem is to find the kth ancestor of a node in a tree .

Spoiler Although I will be using a tree for this , you can use this same idea outside trees also . Try to find use cases after reading the whole article :p

Okay , How do you do that ?

First things first .

  • Any number can be represented as sum of some powers of 2’s

Taking advantage of this , if we want to know kth ancestor , we can represent taking k steps as taking no more than log(k) steps . Now how do we solve the problem by taking log(k) steps ? After all taking log(k) steps ain’t the same as taking k steps :smirk: Otherwise we would have done that earlier !

Here’s how we do this ,

Imagine this is the tree . The parent of 1 is 2 , parent of 2 is 3 and so on . Now , what we do is basically use the information known so far to compute my curent step . Suppose we want to know the 2nd ancestor of 1 . You can easily see that this is nothing other than 1st ancestor (i.e his parent in this case) of 2 . We can do this as we already know the information of 1st ancestors of all the nodes . This is how we solve our problem by taking advantage of the information we know so far . The fancy name of what we did so far is Dynamic Programming .

This is what we did so far in pseudocode

1
2
3
4
5
6
7
8
9
10
# ancestor[i][j] = 2^j th ancestor of ith node

for i in nodes:
    ancestor[i][0] = parent[i]

for j in 1 to log(k):
    for i in nodes:
        middle_man = ancestor[i][j-1] # this guy helps me to calculate my current step
        ancestor[i][j] = ancestor[middle_man][j-1] # 2^(j-1) th ancestor's 2^(j-1) th ancestor is what we want

Now , we know all 2 j th ancestors . How to find the kth ancestor where k is not a power of 2 . Simple ! Just you can represet 

1
6 = 2^2 + 2^1

the same way you can find the kth ancestor . The pseudocode is as follows :

1
2
3
4
# node is the one that we are finding the ancestor of aka the one we are lifting
for j in log(k) to 1:
    if jth bit is set in k:
        node = ancestor[node][j]

Woah , Where is this gonna help ?

Binary Lifting_ has a lot of use cases . Most common is that in finding _Least Common Ancestor (LCA) . But who says this is the only thing that you can do ! You can do like path queries (minimum in a path) and many more !
And who says you can only use this ideas in trees ? You can use this same idea in Sparse Table , Binary Index Trees and in many more cases !

Practice Problems

  • Sloth Naptime

  • Cycle Free Flow

    Idea

    We can use an additional array to track the minimum cost.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # ancestor[i][j] = 2^j th ancestor of ith node
    # minimum[i][j] = minimum distance upto 2^j th ancestor of ith node

    for i in nodes:
        ancestor[i][0] = parent[i]
        minimum[i][0] = cost[{i,parent[i]}] 

    for j in 1 to log(k):
        for i in nodes:
            middle_man = ancestor[i][j-1] # this guy helps me to calculate my current step
            ancestor[i][j] = ancestor[middle_man][j-1] # 2^(j-1) th ancestor's 2^(j-1) th ancestor is what we want
            minimum[i][j] = min(minimum[i][j-1],minimum[middle_man][j-1]) 
            # here , minimum[i][j-1] is the path from ith node to his 2^(j-1) th ancestor and minimum[middle_man][j-1] is the path from 2^(j-1) th ancestor to its 2^(j-1) th ancestor. Basically the minumum of the 2 paths indicated in the picture in red arrows

Applications (First complete the practice problems)

LCA (Lowest Common Ancestor)

Idea

The idea is to :

  • First make the levels same
    • We do this by binary lifting the deeper node
  • Second , we lift both the nodes up as long as both of their parents are not same
    • We do this by binary lifting both the nodes
Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

/**

Description
============
Given 2 nodes  , find the Lowest Common Ancestor

**/

/** Which of the favors of your Lord will you deny ? **/

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define MP make_pair
#define F first
#define S second
#define INF INT_MAX

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int nmax = 1e4+7;
const LL LINF = 1e17;

string to_str(LL x)
{
    stringstream ss;
    ss<<x;
    return ss.str();
}

vector<int>adj[nmax];
map<PII,int>cost;
int parent[nmax];
int L[nmax];
int dist[nmax];
int sptable[nmax][15]; /** adjust 15 according to log of nmax **/

void dfs(int u,int par,int lvl)
{
    parent[u] = par;
    L[u] = lvl;

    if(par!=-1)
        dist[u] = dist[par] + cost[{par,u}];

    for(int v:adj[u])
    {
        if(v!=par)
            dfs(v,u,lvl+1);
    }
}

void lca_init(int n)
{
    memset(sptable,-1,sizeof sptable);

    for(int i=1; i<=n; i++)
        sptable[i][0] = parent[i];

    for(int j=1; (1<<j)<n; j++)
        for(int i=1; i<=n; i++)
            if(sptable[i][j-1]!=-1)
                sptable[i][j] = sptable[sptable[i][j-1]][j-1];
}

int lca_query(int u,int v)
{
    if(L[u]<L[v])
        swap(u,v);

    int dis = L[u] - L[v];

    int log;
    for(log = 1; (1<<log)<=L[u]; log++);
    log--;

    ///making the levels same
    for(int i=log; i>=0; i--)
        if(dis &(1<<i))
            u = sptable[u][i];

    if(u==v)
        return u;

    for(int i=log; i>=0; i--)
        if(sptable[u][i]!=-1 && sptable[v][i]!=-1 && sptable[u][i]!=sptable[v][i])
        {
            u = sptable[u][i];
            v = sptable[v][i];
        }

    return parent[u];
}

int main()
{
    //freopen("OUT.txt","w",stdout);

    int n;
    cin>>n;

    for(int i=0; i<=n; i++)
    {
        adj[i].clear();
        dist[i] = 0;
    }

    for(int i=1; i<n; i++)
    {
        int u,v,c;
        cin>>u>>v>>c;

        adj[u].push_back(v);
        adj[v].push_back(u);

        cost[{u,v}] = c;
        cost[{v,u}] = c;
    }

    /** PRE-WORK **/
    dfs(1,-1,0);
    lca_init(n);

    int node_a , node_b;
    cin>>node_a>>node_b;

    int lca = lca_query(node_a,node_b); /** finding LCA **/
    cout<<"LCA : "<<lca<<endl;

    return 0;
}

Path Query (Minimum/Maximum) without any update

Idea

We can use an additional array to track the minimum cost.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# ancestor[i][j] = 2^j th ancestor of ith node
# minimum[i][j] = minimum distance upto 2^j th ancestor of ith node

for i in nodes:
    ancestor[i][0] = parent[i]
    minimum[i][0] = cost[{i,parent[i]}] 

for j in 1 to log(k):
    for i in nodes:
        middle_man = ancestor[i][j-1] # this guy helps me to calculate my current step
        ancestor[i][j] = ancestor[middle_man][j-1] # 2^(j-1) th ancestor's 2^(j-1) th ancestor is what we want
        minimum[i][j] = min(minimum[i][j-1],minimum[middle_man][j-1]) 
        # here , minimum[i][j-1] is the path from ith node to his 2^(j-1) th ancestor and minimum[middle_man][j-1] is the path from 2^(j-1) th ancestor to its 2^(j-1) th ancestor. Basically the minumum of the 2 paths indicated in the picture in red arrows

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271

/**

Description
===========
Given 2 nodes per query : find the minimum & maximum weight in their path
Note :
1. Input is a tree
2. No update

Reference Problem
=================
LightOj 1162

**/

/** Which of the favors of your Lord will you deny ? **/

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define F first
#define S second

#define ALL(x)      (x).begin(), (x).end()
#define READ        freopen("alu.txt", "r", stdin)
#define WRITE       freopen("vorta.txt", "w", stdout)

#ifndef ONLINE_JUDGE
#define DBG(x)      cout << __LINE__ << " says: " << #x << " = " << (x) << endl
#else
#define DBG(x)
#define endl "\n"
#endif

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int nmax = 1e5+7;

vector<vector<PII>>adj;

vector<PII>parent;
vector<int>L;

int sptable[nmax][17]; /** adjust 2nd dimension according to log of nmax **/
int minD_sptable[nmax][17]; /// this is to store the minimum values of all the paths
int maxD_sptable[nmax][17]; /// this is to store the minimum values of all the paths

void dfs(int u,int par,int lvl)
{
    parent[u].F = par;
    L[u] = lvl;

    for(PII next:adj[u])
    {
        int v = next.F;

        if(v!=par)
        {
            parent[v].S = next.S; /// the edge weight to parent
            dfs(v,u,lvl+1);
        }
    }
}

void lca_init(int n)
{
    memset(sptable,-1,sizeof sptable);

    for(int i=1; i<=n; i++)
        sptable[i][0] = parent[i].F; /// 2^0 th parent

    for(int j=1; (1<<j)<n; j++)
        for(int i=1; i<=n; i++)
            if(sptable[i][j-1]!=-1)
                sptable[i][j] = sptable[sptable[i][j-1]][j-1];

    memset(minD_sptable,-1,sizeof minD_sptable);

    for(int i=1; i<=n; i++)
        minD_sptable[i][0] = parent[i].S; /// 2^0 th parent's edge weight

    for(int j=1; (1<<j)<n; j++)
        for(int i=1; i<=n; i++)
            if(minD_sptable[i][j-1]!=-1)
                minD_sptable[i][j] = min(minD_sptable[i][j-1],minD_sptable[sptable[i][j-1]][j-1]);

    memset(maxD_sptable,-1,sizeof maxD_sptable);

    for(int i=1; i<=n; i++)
        maxD_sptable[i][0] = parent[i].S; /// 2^0 th parent's edge weight

    for(int j=1; (1<<j)<n; j++)
        for(int i=1; i<=n; i++)
            if(maxD_sptable[i][j-1]!=-1)
                maxD_sptable[i][j] = max(maxD_sptable[i][j-1],maxD_sptable[sptable[i][j-1]][j-1]);
}

int lca_query(int u,int v)
{
    if(L[u]<L[v])
        swap(u,v);

    int dis = L[u] - L[v];

    int log;
    for(log = 1; (1<<log)<=L[u]; log++);
    log--;

    ///making the levels same
    for(int i=log; i>=0; i--)
        if(dis &(1<<i))
            u = sptable[u][i];

    if(u==v)
        return u;

    for(int i=log; i>=0; i--)
        if(sptable[u][i]!=-1 && sptable[v][i]!=-1 && sptable[u][i]!=sptable[v][i])
        {
            u = sptable[u][i];
            v = sptable[v][i];
        }

    return parent[u].F;
}

int Distance(int a,int b)
{
    return L[a] + L[b] - 2*L[lca_query(a,b)];
}

PII Lift(int node,int level) /// lift the node up by this many level and query
{
    int log;
    for(log = 1; (1<<log)<=L[node]; log++);
    log--;

    int mn = INT_MAX;
    int mx = 0;

    for(int i=log; i>=0; i--)
        if(level&(1<<i))
        {
            mn = min(mn,minD_sptable[node][i]);
            mx = max(mx,maxD_sptable[node][i]);
            node = sptable[node][i];
        }


    return {mn,mx};
}

PII min_max_query(int u,int v)
{
    int lca = lca_query(u,v);

    int d_ul = Distance(u,lca);
    int d_vl = Distance(v,lca);

    PII p1 = Lift(u,d_ul);
    PII p2 = Lift(v,d_vl);

    return {min(p1.F,p2.F),max(p1.S,p2.S)};
}

void INIT(int len)
{
    adj = vector<vector<PII>>(len);
    parent = vector<PII>(len);
    L = vector<int>(len);
}

int main()
{
    optimizeIO();

    int tc;
    scanf("%d",&tc);

    int cs = 0;

    while(tc--)
    {
        printf("Case %d:\n",++cs);

        int n;
        scanf("%d",&n);

        INIT(n+1);

        int m = n-1;

        for(int i=1; i<=m; i++)
        {
            int u,v,c;
            scanf("%d %d %d",&u,&v,&c);

            adj[u].push_back({v,c});
            adj[v].push_back({u,c});
        }

        /** PRE-WORK **/
        dfs(1,-1,0);
        lca_init(n);

        int q;
        scanf("%d",&q);

        while(q--)
        {
            int node_a, node_b;
            scanf("%d %d",&node_a,&node_b);

            PII ans = min_max_query(node_a,node_b);
            printf("%d %d\n",ans.F,ans.S);
        }
    }



    return 0;
}

/**
**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(int i=0; i<v.size(); i++)
    {
        os<<v[i]<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}

Sparse Table

Idea

Check cp-algorithms