Chapter 25 of 30
Binary Lifting, LCA & Euler Tour
Master binary lifting for ancestor queries, lowest common ancestor, and Euler tour technique for subtree queries.
Binary LiftingLowest Common Ancestor (LCA)Euler Tour
Share:
Binary Lifting, LCA & Euler Tour
These are the advanced tree techniques that turn O(n) queries into O(log n) or O(1). Binary lifting preprocesses a tree to answer ancestor queries in O(log n); Euler tour flattens the tree for efficient subtree and path queries.
Binary Lifting
Precompute 2^k-th ancestors for every node:
hljs cpp
const int MAX_LOG = 20; // enough for n ≤ 10^6
vector<int> depth(n, 0);
vector<vector<int>> up(n, vector<int>(MAX_LOG, -1));
// First DFS: compute parent (up[i][0]) and depth
function<void(int, int)> dfs = [&](int u, int p) {
up[u][0] = p;
for (int v : adj[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
};
dfs(0, -1);
// Build binary lifting table
for (int j = 1; j < MAX_LOG; j++) {
for (int i = 0; i < n; i++) {
if (up[i][j - 1] != -1) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
}
Query: k-th Ancestor
hljs cpp
int kthAncestor(int node, int k) {
for (int j = 0; j < MAX_LOG; j++) {
if (k & (1 << j)) {
node = up[node][j];
if (node == -1) break;
}
}
return node;
}
Time Complexity
- Preprocessing: O(n log n)
- Query: O(log n)
Lowest Common Ancestor (LCA)
The LCA of nodes u and v is the deepest node that is an ancestor of both.
Using Binary Lifting
hljs cpp
int lca(int u, int v) {
// Make u deeper
if (depth[u] < depth[v]) swap(u, v);
// Lift u to the same depth as v
int diff = depth[u] - depth[v];
for (int j = 0; j < MAX_LOG; j++) {
if (diff & (1 << j)) {
u = up[u][j];
}
}
if (u == v) return u;
// Binary search for LCA
for (int j = MAX_LOG - 1; j >= 0; j--) {
if (up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
}
Distance Between Two Nodes
hljs cpp
int dist(int u, int v) {
int anc = lca(u, v);
return depth[u] + depth[v] - 2 * depth[anc];
}
Euler Tour
Flattens a tree into an array by recording each node's entry and exit times:
hljs cpp
vector<int> euler; // Euler tour sequence
vector<int> tin(n), tout(n); // entry and exit times
int timer = 0;
function<void(int, int)> dfs = [&](int u, int p) {
tin[u] = timer++;
euler.push_back(u);
for (int v : adj[u]) {
if (v != p) {
dfs(v, u);
}
}
tout[u] = timer++;
euler.push_back(u);
};
dfs(0, -1);
Properties
tin[u] < tin[v]andtout[u] > tout[v]if and only ifuis an ancestor ofv- Subtree of
ucorresponds to a contiguous segment in the Euler tour
Subtree Query Using Euler Tour + Fenwick Tree
hljs cpp
// Mark each node's subtree as a range in the Euler tour
// Use Fenwick tree for range updates and point queries
Fenwick fw(n);
// Add value to subtree of u
void updateSubtree(int u, long long val) {
fw.update(tin[u], val);
fw.update(tout[u] + 1, -val);
}
// Query value at node u
long long queryNode(int u) {
return fw.query(tin[u]);
}
Path Queries Using Euler Tour + Fenwick Tree
hljs cpp
// Add value to path from root to u
void updatePath(int u, long long val) {
fw.update(tin[u], val);
fw.update(tout[u] + 1, -val);
}
// Query value at node u (sum of all root-to-u updates)
long long queryNode(int u) {
return fw.query(tin[u]);
}
Summary
- Binary lifting: O(n log n) preprocessing, O(log n) ancestor queries
- LCA: O(log n) using binary lifting (lift deeper node, then binary search)
- Euler tour: flattens tree to array, enables subtree/path queries with Fenwick/segment tree
tin[u]andtout[u]define the subtree range in the Euler tour- These techniques combined solve most tree query problems in O(n log n)
Prefer reading offline? Download the full book as a PDF.
Download Free Book