PrevNext
Somewhat Frequent
 0/31

Binary Jumping

Authors: Benjamin Qi, Neo Wang, Qi Wang

Introduces the problems of finding level ancestors in a tree and computing the lowest common ancestors.

Edit This Page

Binary Jumping

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

Tutorial

Pro Tip

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

Solution

To solve this problem, we can use a standard binary lifting implementation where jmp(int x, int d) corresponds to the dd-th ancestor of xx.

In our jmp(int x, int d) if our final value of xx is 00, then such a node does not exist and we can simply return 1-1. This is because the lowest number a node can be is 11 (the root of the tree).

In our implementation, we test if we jump in powers of two by using the &\& operator. If the iith bit on the right is toggled, then we jump. For example, a jump of 1313 would correspond to the binary number 11011101. We would jump 3 times on bits 0,2,30, 2, 3 (in that order) counting from the right.

Illustration of the jump method

To calculate the rows required for the int up[MS][MX] array, use the formula log2N\lceil \log_2{N} \rceil which in our case simplifies to log2(2105)=18\lceil \log_2{(2\cdot 10^5)}\rceil = 18.

Pro Tip

It never hurts to add additional rows - or columns, depending on your implementation - (as long as it's reasonable)!

C++

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORE(i, a, b) for (int i = (a); i <= (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define trav(a, x) for (auto &a : x)
int N, Q;

Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsBinary Jumping
CSESNormal
Show TagsFunctional Graph
CSESNormal
Show Tags2P, Binary Jumping, Binary Search
POINormal
CFNormal
Baltic OINormal
Baltic OINormal
PlatinumHard
Show TagsBinary Jumping
Baltic OIVery Hard

Lowest Common Ancestor

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

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

Solution (Company Queries II)

Resources
CPH

Brief description/solution

SansPapyrus683

Alternative implementation

To find lca(a,b)\textrm{lca}(a, b), we can first lift the lower node of aa and bb 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.

C++

Code Snippet: Benq Template (Click to expand)
int N, Q, T = 1;
int depth[200005];
int up[200005][20];
vi adj[200005];
void dfs(int v) {
FOR(i, 1, 20) { up[v][i] = up[up[v][i - 1]][i - 1]; }

Alternative Solution (Company Queries II)

As mentioned in the Euler Tour Technique module, let st,en,up\texttt{st}, \texttt{en}, \texttt{up} be the time-in, time-out, and ancestor table for all nodes in the tree.

These can be filled with a DFS traversal. up\texttt{up} can be generated because DFS allows the ancestors to be filled first before traversing the current node.

With this information, we can declare node aa an ancestor of bb if st[a]st[b]\texttt{st}[a] \le \texttt{st}[b] and en[a]en[b]\texttt{en}[a] \ge \texttt{en}[b].

We know that if aa is an ancestor of bb or bb is an ancestor of aa, the answer will be aa or bb respectively. Otherwise, we lift one of the nodes up (in this case, aa) decrementally while it is not the ancestor of bb. Therefore, if up[a][i]\texttt{up}[a][i] is not an ancestor of bb, then we can set aa to be up[a][i]\texttt{up}[a][i], else, we will decrement ii and try to find a lower common ancestor. Afterwards, our answer is the parent of aa.

C++

Code Snippet: Benq Template (Click to expand)
int N, Q, T = 1;
vi st, en;
int up[200005][20];
vi adj[200005];
void dfs(int v, int p) {
st[v] = T++;
up[v][0] = p;

Alternate Solution II (Company Queries II)

We can also find the LCA of two nodes using the Tarjan's Offline LCA algorithm. By taking advantage of the DFS traversal, we can precompute the answers to the queries through forming subtrees and calculating the common parent with a similar structure as Disjoint-Set Union.

C++

Code Snippet: Benq Template (Click to expand)
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma region
using ll = long long;
using db = long double; // or double, if TL is tight
Resources
cp-algo

Solution (Distance Queries)

Find LCA of node aa and bb as described above. Then, the distance between the two nodes would be the depth[a]+depth[b]2depth[lca(a,b)]\texttt{depth}[a] + \texttt{depth}[b] - 2 \cdot \texttt{depth}[\textrm{lca}(a, b)].

C++

Code Snippet: Benq Template (Click to expand)
int N, Q, T = 1;
int depth[200005];
int up[200005][20];
vi adj[200005];
void dfs(int v) {
FOR(i, 1, 20) { up[v][i] = up[up[v][i - 1]][i - 1]; }

Problems

USACO

StatusSourceProblem NameDifficultyTags
PlatinumEasy
Show TagsLCA
PlatinumNormal
Show TagsLCA
Old GoldNormal
Show TagsBinary Jumping, Euler Tour, Small to Large
PlatinumHard
Show TagsLCA
PlatinumHard
Show TagsDiameter
PlatinumHard
Show TagsLCA
PlatinumVery Hard
Show TagsLCA

General

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsBinary Jumping
CFNormal
Show TagsLCA
Baltic OINormal
CFNormal
Show TagsLCA
CFNormal
Show TagsLCA
CSANormal
Show TagsLCA
CFNormal
Show TagsLCA
Back to SchoolNormal
Show TagsLCA
Google KickstartHard
Show TagsBinary Jumping, DFS, LCA
CFHard
Show TagsBinary Jumping, LCA
TLXHard
Show TagsLCA
TLXHard
Show TagsLCA

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

figure out a better way to order these, difficulties aren't really accurate

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!

PrevNext