Not Frequent
0/17

# Euler Tour Technique

Authors: Benjamin Qi, Andrew Wang, Neo Wang

Flattening a tree into an array to easily query and update subtrees.

## Introduction

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

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

Resources
CPH

introduces tree traversal array, how to solve above problem

### 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.

C++

#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;

Java

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;	}}

Python

# The graph represented as an adjacency list (0-indexed)neighbors = [[1, 2], , [0, 3, 4], , ]start =  * len(neighbors)end =  * 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

 Node Index 1 2 3 4 5 $\texttt{start}$ 0 0 0 0 0 $\texttt{end}$ 0 0 0 0 0

Since we call $\text{dfs}(1, 0)$, we set $\texttt{start}$ 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

 Node Index 1 2 3 4 5 $\texttt{start}$ 0 0 0 0 0 $\texttt{end}$ 0 0 0 0 0

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}$ to 1 and increment the timer. However, because node $2$ has no children, we don't call $\text{dfs}$. Instead, we set $\texttt{end}$ to 2 because our current timer is now 2.

Current timer value: 2

 Node Index 1 2 3 4 5 $\texttt{start}$ 0 1 0 0 0 $\texttt{end}$ 0 2 0 0 0

Now we must resolve $\text{dfs}(3, 1)$. Similar to before, we set $\texttt{start}$ 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

 Node Index 1 2 3 4 5 $\texttt{start}$ 0 1 2 0 0 $\texttt{end}$ 0 1 0 0 0

Now we must resolve $\text{dfs}(4, 3)$ and $\text{dfs}(5, 3)$. First, we resolve $\text{dfs}(4, 3)$ by setting $\texttt{start}$ to the value of the timer (3 in this case) and incrementing the timer. Then, since node $4$ has no children, set $\texttt{end}$ 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}$ to 4. Since node $5$ also has no children, set $\texttt{end}$ to 5.

Current timer value: 5

 Node Index 1 2 3 4 5 $\texttt{start}$ 0 1 2 3 4 $\texttt{end}$ 0 2 0 4 5

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

 Node Index 1 2 3 4 5 $\texttt{start}$ 0 1 2 3 4 $\texttt{end}$ 5 2 5 4 5

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

C++

#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

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

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

Resources
CPH
cp-algo

### Implementation

Resources
Benq

C++

int n;  // The number of nodes in the graphvector<int> graph;int timer = 0, tin, euler_tour;int segtree;  // 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) {

Java

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.

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

Resources
CPH

diagrams

PAPS

code

cp-algo

### Optional: Faster Preprocessing

From CPH:

There are also more sophisticated techniques where the preprocessing time is only $\mathcal{O}(N)$, but such algorithms are not needed in competitive programming.

Ex. the following:

C++

Resources
Benq

## Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsEuler Tour, PURS
CSESNormal
Show TagsEuler Tour, PURS
GoldNormal
Show TagsEuler Tour, HLD, PURS
GoldNormal
Show TagsEuler Tour, LCA
PlatNormal
Show TagsEuler Tour, PURS
ACNormal
Show TagsEuler Tour
ACNormal
Show TagsEuler Tour
ACNormal
Show TagsBinary Search, Euler Tour
ACHard
Show TagsLCA, PURS
IOIHard
Show TagsBinary Search, Euler Tour
PlatHard
Show TagsEuler Tour, Lazy SegTree, PURS
CFHard
Show TagsEuler Tour, RURQ
DMOPCVery Hard
Show TagsEuler Tour, PURS

### 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!