# Binary Lifting Search

# Binary Lifting Search

Binary lifting search finds a target ancestor, state, or boundary by jumping in powers of two. It is common on trees, functional graphs, and ordered implicit structures where repeated "next" or "parent" moves are needed.

The method preprocesses jumps of length:

$$
1, 2, 4, 8, \dots
$$

Then a query combines these jumps to move quickly.

## Problem

Given a directed parent relation `parent[v]`, preprocess a table so that queries can find the $k$-th ancestor of a node $v$.

More generally, binary lifting can search for the farthest reachable state that satisfies a condition.

## Key Idea

Define:

$$
up[v][j]
$$

as the ancestor of node $v$ after $2^j$ parent steps.

Then:

$$
up[v][0] = parent[v]
$$

and

$$
up[v][j] = up[up[v][j-1]][j-1]
$$

This recurrence builds large jumps from smaller jumps.

## Preprocessing

```id="blift-pre"
build_binary_lifting(parent):
    n = length(parent)
    LOG = ceil(log2(n)) + 1

    up = table of size n by LOG

    for v from 0 to n - 1:
        up[v][0] = parent[v]

    for j from 1 to LOG - 1:
        for v from 0 to n - 1:
            if up[v][j - 1] == -1:
                up[v][j] = -1
            else:
                up[v][j] = up[up[v][j - 1]][j - 1]

    return up
```

## Query: K-th Ancestor

Use the binary representation of $k$. If bit $j$ is set, jump by $2^j$.

```id="blift-query"
kth_ancestor(up, v, k):
    j = 0

    while k > 0 and v != -1:
        if k & 1:
            v = up[v][j]
        k = k >> 1
        j = j + 1

    return v
```

## Example

Suppose the parent chain is:

$$
0 \leftarrow 1 \leftarrow 2 \leftarrow 3 \leftarrow 4
$$

Here:

| node | parent |
| ---- | ------ |
| 0    | -1     |
| 1    | 0      |
| 2    | 1      |
| 3    | 2      |
| 4    | 3      |

The $3$-rd ancestor of node $4$ is node $1$:

$$
4 \to 3 \to 2 \to 1
$$

Since:

$$
3 = 2 + 1
$$

the query uses one jump of length $2$ and one jump of length $1$.

## Search Form

Binary lifting can also find the highest ancestor satisfying a predicate.

```id="blift-search"
highest_ancestor_while(up, v, ok):
    for j from LOG - 1 down to 0:
        u = up[v][j]
        if u != -1 and ok(u):
            v = u

    return v
```

This is useful when `ok` remains true while moving upward, then becomes false beyond a boundary.

## Correctness

The preprocessing recurrence is correct because a jump of length $2^j$ can be decomposed into two jumps of length $2^{j-1}$.

During a query, the binary representation of $k$ decomposes the requested distance into powers of two. Each selected jump moves exactly that distance. Therefore the final node is the $k$-th ancestor, or `-1` if the chain ends.

For predicate search, the algorithm tests larger jumps first. It keeps only jumps that preserve the predicate, so it never crosses the boundary. When no larger valid jump remains, the current node is the farthest reachable valid state.

## Complexity

Let $n$ be the number of nodes and let:

$$
L = \lceil \log_2 n \rceil
$$

| operation           |    time |   space |
| ------------------- | ------: | ------: |
| preprocessing       | $O(nL)$ | $O(nL)$ |
| k-th ancestor query |  $O(L)$ |  $O(1)$ |
| predicate search    |  $O(L)$ |  $O(1)$ |

## Use Cases

* K-th ancestor in a tree
* Lowest common ancestor
* Jump pointers in functional graphs
* Farthest valid ancestor
* Searching over repeated transitions

## Notes

* Binary lifting requires static or mostly static structure.
* Updates are expensive if many parent links change.
* It is best when many queries justify preprocessing.
* The same idea applies to sparse tables and doubling DP.

## Implementation

```id="py-blift"
def build_binary_lifting(parent):
    n = len(parent)
    log = max(1, n.bit_length())
    up = [[-1] * log for _ in range(n)]

    for v in range(n):
        up[v][0] = parent[v]

    for j in range(1, log):
        for v in range(n):
            u = up[v][j - 1]
            up[v][j] = -1 if u == -1 else up[u][j - 1]

    return up

def kth_ancestor(up, v, k):
    j = 0
    while k > 0 and v != -1:
        if k & 1:
            if j >= len(up[v]):
                return -1
            v = up[v][j]
        k >>= 1
        j += 1
    return v
```

```id="go-blift"
func BuildBinaryLifting(parent []int) [][]int {
    n := len(parent)
    log := 1
    for (1 << log) <= n {
        log++
    }

    up := make([][]int, n)
    for v := 0; v < n; v++ {
        up[v] = make([]int, log)
        up[v][0] = parent[v]
    }

    for j := 1; j < log; j++ {
        for v := 0; v < n; v++ {
            u := up[v][j-1]
            if u == -1 {
                up[v][j] = -1
            } else {
                up[v][j] = up[u][j-1]
            }
        }
    }

    return up
}

func KthAncestor(up [][]int, v int, k int) int {
    j := 0
    for k > 0 && v != -1 {
        if k&1 == 1 {
            if j >= len(up[v]) {
                return -1
            }
            v = up[v][j]
        }
        k >>= 1
        j++
    }
    return v
}
```