Binary Lifting (Jumps)
Binary Lifting (Jumps)
Introduction
The most basic task for binary lifting sounds like this: Given a weighted tree with vertices. It is required to answer queries of the form - find the -th ancestor of vertex .
Binary Lifting (Jumps)
The most basic task for binary lifting sounds like this: Given a weighted tree with vertices. It is required to answer queries of the form - find the -th ancestor of vertex .
Let denote the ancestor of vertex . Then to find the -th ancestor of vertex you need to do times .
This solution works slowly, namely in .
When we move up from one vertex to an ancestor, let's call it a jump. In the above solution we made jumps of length (i.e. moved up to the ancestor).
The idea of binary lifting is to make jumps not only of length , but also of length for any . Hence the name of this technique.
Let mean the -th ancestor of vertex . We have:
Thus you can move up times from vertex in . Since can be represented as no more than powers of two. For example, for you can jump only times with lengths .
The asymptotic complexity will be .
There are also various other types of tasks where you also need to be able to jump efficiently from one point to another. For example, the idea of a Sparse Table can be represented in this form too.
Given an array of numbers. It is required to process queries of the form: find the minimum on the segment .
Let's slightly rephrase the condition of the problem. A turtle is at position and will move to the right times. What is the minimum number it will encounter along the way? Let's call this get_min.
Let be the minimum number that the turtle will encounter on its path starting at position going right times and not including position itself. Then we have:
And the answer on the segment will be get_min
int find_par(int x, int k) {
for (int i = 0; i < k; i++) {
x = par[x];
}
return x;
}
const int L = 20; // log(N)
void init() {
for (int i = 1; i <= n; i++) {
par[i][0] = p[i]; // p[i] is parent of vertex i
}
for (int i = 1; i < L; i++) {
for (int j = 1; j <= n; j++) {
par[j][i] = par[par[j][i - 1]][i - 1];
}
}
}
int get_par(int x, int k) {
for (int i = 0; i < L; i++) {
if (k & (1 << i)) {
x = par[x][i];
}
}
return x;
}
const int L = 20; // log(N)
void init() {
for (int i = 1; i < n; i++) {
f[i][0] = A[i + 1];
}
for (int i = 1; i < L; i++) {
for (int j = 1; j + (1 << i) <= n; j++) {
f[j][i] = min(f[j][i - 1], f[j + (1 << i - 1)][i - 1]);
}
}
}
int get_min(int x, int k) {
int res = A[x];
for (int i = 0; i < L; i++) {
if (k & (1 << i)) {
res = min(res, f[x][i]); // update answer
x += (1 << i); // jump with length 2^i
}
}
return res;
}