# Binary Jumping

Authors: Benjamin Qi, Neo Wang, Qi Wang

Contributors: Kevin Sheng, Mihnea Brebenel

Efficiently finding ancestors of a node.

### Terminology

Binary jumping is more commonly referred to as "binary lifting".

## Binary Jumping

Focus Problem – try your best to solve this problem before continuing!

Resources | ||||
---|---|---|---|---|

CPH | ||||

AryanshS | ||||

SecondThread |

### Explanation

Binary lifting consists of calculating the $2^k$-th ancestor of each node for all relevant values of $k$ and storing them in a table.

With this table, we can then efficiently answer queries regarding the $k$-th ancestor of all nodes. This is because any $k$ can be broken down into a sum of powers of $2$ with its binary representation.

This way, instead of directly computing, say, the $13$th ancestor of a node, we can go to the $8$th, then $4$th, then $1$st ancestor of the node. This results in a logarithmic complexity for computing the $k$th parent.

Here's an animation of how we jump if you're still confused:

To actually compute our binary jumping table, we start with the $2^0=1$st parents of each node, which is their direct parent. We then move on and calculate $2^1=2$nd parents, using the fact that the $2$nd parent can be calculated as the $1$st parent of the $1$st parent. Using similar logic, we move on to $2^2$, $2^3$, and so on. We stop when $2^n$ is greater than the size of the tree, since at that point we're definitely at the root.

### Implementation

**Time Complexity:** $\mathcal{O}((N+Q)\log N)$

C++

#include <cmath>#include <iostream>#include <vector>using std::cout;using std::endl;using std::vector;class Tree {private:

### Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsBinary Jumping | |||

CSES | Normal | ## Show TagsFunctional Graph | |||

CSES | Normal | ## Show Tags2P, Binary Jumping, Binary Search | |||

POI | Normal | ## Show TagsBinary Jumping, Sliding Window | |||

CF | Normal | ||||

Baltic OI | Normal | ||||

Baltic OI | Normal | ||||

Platinum | Hard | ## Show TagsBinary Jumping | |||

Baltic OI | Very Hard |

## Lowest Common Ancestor

Focus Problem – try your best to solve this problem before continuing!

Resources | ||||
---|---|---|---|---|

CPH | Brief description/solution | |||

SansPapyrus683 | Alternative implementation |

### Explanation 1

To find $\textrm{lca}(a, b)$, we can first lift the lower node of $a$ and $b$ to the same depth as the other. Then, we lift both nodes up decrementally. At the end, the parent of either node is the LCA of the two.

### Implementation

**Time Complexity:** $\mathcal{O}((N+Q)\log N)$

C++

#include <cmath>#include <iostream>#include <vector>using std::cout;using std::endl;using std::vector;class Tree {private:

### Explanation 2

We can also use an Euler tour of the tree to help us compute the LCAs as well.

Let $\texttt{start}$ and $\texttt{end}$ be the time-in and time-out table for the nodes in the tree. They'll be filled up in the exact same way the Euler tour module does it.

The cool thing is that while we're filling up $\texttt{start}$ and $\texttt{end}$, we can also calculate our binary jumping table in the exact same way we did in the previous solution! We can do this because in a DFS, we're guaranteed to have processed all of a node's parents before the node itself, so all the tables of any node's ancestors will have been filled when we reach the node.

Now, to actually calculate the LCA without the depths of the nodes, we can use the fact that node $a$ is an ancestor of node $b$ if $\texttt{start}[a] \le \texttt{start}[b]$ and $\texttt{end}[b] \le \texttt{end}[a]$.

In our LCA function, we first check if one node is already an ancestor of the other. In that case, we return the ancestor. If it isn't, then we lift up one of the nodes until its an ancestor of the other in a method that's basically the same as our previous binary jumping algorithm. After that, our answer is the parent of the node we lift up.

### Implementation

**Time Complexity:** $\mathcal{O}((N+Q)\log N)$

C++

#include <cmath>#include <iostream>#include <vector>using std::cout;using std::endl;using std::vector;class Tree {private:

### Explanation 3

We can also find the LCA of two nodes using Tarjan's Offline LCA algorithm.

By taking advantage of the DFS traversal, we can precompute the answers to the queries through forming subtrees and calculated the common parent with a similar structure as Disjoint-Set Union.

### Implementation

C++

#include <bits/stdc++.h>using namespace std;const int MAX = 2e5 + 1;bool vis[MAX];int lca[MAX], fa[MAX];vector<array<int, 2>> adj[MAX], qry[MAX];int find(int u) { return (fa[u] == u) ? u : fa[u] = find(fa[u]); }void tarjan(int node) {vis[node] = true;

Resources | ||||
---|---|---|---|---|

cp-algo |

Focus Problem – try your best to solve this problem before continuing!

### Explanation

Since we have the depth of all the nodes, the distance between two nodes $a$ and $b$ is $\texttt{depth}[a] + \texttt{depth}[b] - 2 \cdot \texttt{depth}[\textrm{lca}(a, b)]$.

Here's some intuition if you're confused about how this formula works.
To get from node $a$ to $b$, one way would be to go to the root of the tree
and then to $b$. This gives us a distance of $\texttt{depth}[a] + \texttt{depth}[b]$.
However, notice that we're passing through all the nodes above the LCA
*twice*.
Thus, we have to subtract off twice the depth of the LCA, giving us our final expression.

### Implementation

**Time Complexity:** $\mathcal{O}((N+Q)\log N)$

C++

#include <cmath>#include <iostream>#include <vector>using std::cout;using std::endl;using std::vector;Code Snippet: LCA Tree (Click to expand)

### Problems

#### USACO

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Platinum | Easy | ## Show TagsLCA | |||

Platinum | Normal | ## Show TagsLCA | |||

Old Gold | Normal | ## Show TagsBinary Jumping, Euler Tour, Small to Large | |||

Platinum | Hard | ## Show TagsLCA | |||

Platinum | Hard | ## Show TagsDiameter | |||

Platinum | Hard | ## Show TagsLCA | |||

Platinum | Very Hard | ## Show TagsLCA |

#### General

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CF | Easy | ## Show TagsBinary Jumping | |||

CF | Normal | ## Show TagsLCA | |||

Baltic OI | Normal | ||||

CF | Normal | ## Show TagsLCA | |||

CF | Normal | ## Show TagsLCA | |||

CSA | Normal | ## Show TagsLCA | |||

CF | Normal | ## Show TagsLCA | |||

Back to School | Normal | ## Show TagsLCA | |||

Google Kickstart | Hard | ## Show TagsBinary Jumping, DFS, LCA | |||

CF | Hard | ## Show TagsBinary Jumping, LCA | |||

TLX | Hard | ## Show TagsLCA | |||

TLX | Hard | ## Show TagsLCA |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!