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

Let's use the below graph for a quick demo of the technique:

Here's the code we're going to use to perform a Euler Tour on the graph. Notice that it follows the same general structure as a normal depth-first search. It's just that in this algorithm, we're keeping a few auxiliary variables we're going to use later on.

Copy
#include <iostream>
#include <vector>

using std::vector;

// The graph represented as an adjacency list (0-indexed)
vector<vector<int>> neighbors{{1, 2}, {0}, {0, 3, 4}, {2}, {2}};
vector<int> start(neighbors.size());
vector<int> end(neighbors.size());
int timer = 0;

Copy
public class EulerTour {
	// The graph represented as an adjacency list (0-indexed)
	static int[][] neighbors = new int[][] {{1, 2}, {0}, {0, 3, 4}, {2}, {2}};
	static int[] start = new int[neighbors.length];
	static int[] end = new int[neighbors.length];
	static int timer = 0;

	static void eulerTour(int at, int prev) {
		start[at] = timer++;
		for (int n : neighbors[at]) {
			if (n != prev) { eulerTour(n, at); }
		}
		end[at] = timer;
	}
}

Copy
# The graph represented as an adjacency list (0-indexed)
neighbors = [[1, 2], [0], [0, 3, 4], [2], [2]]
start = [0] * len(neighbors)
end = [0] * len(neighbors)
timer = 0


def euler_tour(at: int, prev: int):
	global timer
	start[at] = timer
	timer += 1
	for n in neighbors[at]:
		if n != prev:
			euler_tour(n, at)
	end[at] = timer

Tour Walkthrough

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

For brevity's sake, in this walkthrough, we're going to use $\text{dfs}$ instead of the full above function name.

Current timer value: 0

Since we call $\text{dfs}(1, 0)$, we set $\texttt{start}[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{start}[2]$ to 1 and increment the timer. However, because node $2$ has no children, we don't call $\text{dfs}$. Instead, we set $\texttt{end}[2]$ to 2 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{start}[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{start}[4]$ to the value of the timer (3 in this case) and incrementing the timer. Then, since node $4$ has no children, set $\texttt{end}[4]$ to 4.

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

Current timer value: 5

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

Notice that after running $\text{dfs}$, each range $[\texttt{start}[i], \texttt{end}[i]]$ contains all ranges $[\texttt{start}[j], \texttt{end}[j]]$ for each $j$ in the subtree of $i$. Also, $\texttt{end}[i]-\texttt{start}[i]$ is equal to the subtree size of $i$.

Here's a small animation of the tour if you're still confused:

Solution - Subtree Queries

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

 Code Snippet: BIT (from PURS module) (Click to expand)

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.io.*;
import java.util.*;

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.

The following is an example implementation of a sparse table and code that answers LCA queries. Build time is $\mathcal{O}(N\log N)$, and queries are $\mathcal{O}(1)$.

Copy
#include <bits/stdc++.h>
using namespace std;

template <typename T> class SparseTable {
  private:
	int n, log2dist;
	vector<vector<T>> st;

  public:
	SparseTable(const vector<T> &v) {

Resources

Implementation

Problems