Euler Tour Technique

Introduction

If we can preprocess a rooted tree such that every subtree corresponds to a contiguous range on an array, we can do updates and range queries on it!

Tutorial

Implementation

After running $\text{dfs}()$, each range $[\texttt{st}[i], \texttt{en}[i]]$ contains all ranges $[\texttt{st}[j], \texttt{en}[j]]$ for each $j$ in the subtree of $i$. Also, $\texttt{en}[i]-\texttt{st}[i]+1$ is equal to the subtree size of $i$.

Copy
const int MX = 2e5+5;
vector<int> adj[MX];
int timer = 0, st[MX], en[MX];

void dfs(int node, int parent) {
	st[node] = timer++;
	for (int i : adj[node]) {
		if (i != parent) {
			dfs(i, node);
		}
	}
	en[node] = timer-1;
}

Copy
public static void dfs(int i, int p) {
	st[i] = timer++;
	for (int next : g[i]) {
		if(next != p) dfs(next, i);
	}
	en[i] = timer-1;
}

Example Input

5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 3
1 5 3
2 3

Our example input corresponds to the following graph:

Before the DFS, our $\texttt{st}$ and $\texttt{en}$ arrays are initialized with zeros. In this visualization, the first row represents the node indices, the second row represents $\texttt{st}$, and the third represents $\texttt{en}$.

Current timer value: 0

Since we call $\text{dfs}(1, 0)$, we set $\texttt{st}[1]$ to the current timer value of $0$. Then, we proceed to call $\text{dfs}(2, 1)$ and $\text{dfs}(3, 1)$.

Current timer value: 1

Now we must resolve $\text{dfs}(2, 1)$ and $\text{dfs}(3, 1)$. It does not matter which order we process these in, so for this example, we start with $\text{dfs}(2, 1)$. Since the timer value is 1, we set $\texttt{st}[2]$ to 1 and increment the timer. However, because node $2$ has no children, we don't call $\text{dfs}$. Instead, we set $\texttt{en}[2]$ to 1 because our current timer is now 2.

Current timer value: 2

Now we must resolve $\text{dfs}(3, 1)$. Similar to before, we set $\texttt{st}[3]$ to the value of the timer (2 in this case) and increment the timer. Then, we proceed to make the calls $\text{dfs}(4, 3)$ and $\text{dfs}(5, 3)$.

Current timer value: 3

Now we must resolve $\text{dfs}(4, 3)$ and $\text{dfs}(5, 3)$. First, we resolve $\text{dfs}(4, 3)$ by setting $\texttt{st}[4]$ to the value of the timer (3 in this case) and incrementing the timer. Then, since node $4$ has no children, set $\texttt{en}[4]$ to 3.

Now the value of the timer is 4, and we must resolve $\text{dfs}(5, 3)$. Similar to before, we set $\texttt{st}[5]$ to 4. Since node $5$ also has no children, set $\texttt{en}[5]$ to 4.

Current timer value: 5

Now, we must resolve the remaining $\texttt{en}[\text{node}] = \text{timer} - 1$ calls. We first encounter and resolve node $3$, setting $\texttt{en}[3]$ to 4. We then do the same for node $1$, setting $\texttt{en}[1]$ to 4. Our DFS traversal is now complete.

Solution - Subtree Queries

Assumes that dfs() code is included. Uses a segment tree.

Copy
/**
 * Description: 1D point update, range query where \texttt{comb} is
	* any associative operation. If $N=2^p$ then \texttt{seg[1]==query(0,N-1)}.
 * Time: O(\log N)
 * Source:
	* http://codeforces.com/blog/entry/18051
	* KACTL
 * Verification: SPOJ Fenwick
 */

Copy
import java.util.*;
import java.io.*;

public class Main {
	public static int[] st;
	public static int[] en;
	public static int timer, n;
	public static ArrayList<Integer> g[];

	//Segtree code

LCA

Tutorial

Implementation

Copy
int n; // The number of nodes in the graph
vector<int> graph[100000];
int timer = 0, tin[100000], euler_tour[200000];
int segtree[800000]; // Segment tree for RMQ

void dfs(int node = 0, int parent = -1) {
	tin[node] = timer; // The time when we first visit a node
	euler_tour[timer++] = node;
	for (int i : graph[node]) {
		if (i != parent) {

Copy
import java.util.*;
import java.io.*;

public class LCA {
	public static int[] euler_tour, tin;
	public static int timer, size, N;
	public static ArrayList<Integer> g[];

   	//Segtree code
	public static final int maxsize = (int)1e7;  // limit for array size

Sparse Tables

The above code does $\mathcal{O}(N)$ time preprocessing and allows LCA queries in $\mathcal{O}(\log N)$ time. If we replace the segment tree that computes minimums with a sparse table, then we do $\mathcal{O}(N\log N)$ time preprocessing and query in $\mathcal{O}(1)$ time.

Resources

Implementation

Problems