Quaternary Lifting

In a lot of problems with trees we want to quickly access the $$$k$$$-th ancestor of a node. This is usually done with binary lifting in $$$O(\log N)$$$ time complexity. In normal binary lifting we precompute

$$$\text{jmp}[i][k]$$$ = the vertex we end up after jumping $$$2^k$$$ times from $$$i$$$

However there is a way to half the memory usage — Quaternary lifting ( idk if that is the real name ). In quaternary lifting

$$$\text{jmp}[i][k]$$$ = the vertex we end up after jumping $$$4^k$$$ times from $$$i$$$

In binary lifting we represent the number that represents how many times we want to jump in base-2 and in quaternary lifting we represent it in base-4.

Example

Suppose we want to jump 9 steps from vertex v.

Base-4 representation of 9: $$$21 = 2 \cdot 4^1 + 1 \cdot 4^0$$$

Jump process:

Jump $$$4^1$$$ twice ($$$\text{jmp}[v][1]$$$ 2 times)

Jump $$$4^0$$$ once ($$$\text{jmp}[v][0]$$$ one time)

This shows that if in base-4 a digit is $$$ \gt 1$$$ we perform multiple jumps at the same height.

Why is it useful?

Quaternary lifting has

Space = $$$N \log_4 N$$$ = $$$N \frac{\log_2 N}{\log_2 4}$$$ = $$$\frac{1}{2} N \log_2 N$$$. So it uses 2 times less memory than normal binary lifting!

const int MAXN = 100000;
const int K = 10;
int jmp[K][MAXN];
void init(vector<int> parent) {
    for (int i = 0; i < parent.size(); i++) {
        jmp[0][i] = parent[i];
    }
    
    for (int i = 1; i < K; i++) {
        for (int j = 0; j < MAXN; j++) {
             jmp[i][j] = jmp[i - 1][jmp[i - 1][jmp[i - 1][jmp[i - 1][j]]]];
        }
    }
}

int jump(int v, int x) {
    int i = 0;
    while (x >= 1) {
        for (int o = 0; o < x % 4; o++) {
              v = jmp[i][v];
        }
        x /= 4;
        i++;
    }
    return v;
}

But there is a way to do binary lifting in $$$O(N)$$$ memory — Binary Lifting, No Memory Wasted