PrevNext
Not Frequent
 0/16

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

SecondThread

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], [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 start\texttt{start} and end\texttt{end} arrays are initialized with zeros. In this visualization, the first row represents the node indices, the second row represents start\texttt{start}, and the third represents end\texttt{end}.

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

Current timer value: 0

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

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

Current timer value: 1

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

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

Current timer value: 2

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

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

Current timer value: 3

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

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

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

Current timer value: 5

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

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

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

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

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!

Tutorial

Implementation

Resources
Benq

C++

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) {

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 O(N)\mathcal{O}(N) time preprocessing and allows LCA queries in O(logN)\mathcal{O}(\log N) time. If we replace the segment tree that computes minimums with a sparse table, then we do O(NlogN)\mathcal{O}(N\log N) time preprocessing and query in O(1)\mathcal{O}(1) time.

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

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

C++

#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

Optional: Faster Preprocessing

From CPH:

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

Ex. the following:

Implementation

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
PlatinumNormal
Show TagsEuler Tour, PURS
ACNormal
Show TagsEuler Tour
CFNormal
Show TagsEuler Tour
ACNormal
Show TagsBinary Search, Euler Tour
ACHard
Show TagsLCA, PURS
IOIHard
Show TagsBinary Search, Euler Tour
PlatinumHard
Show TagsEuler Tour, Lazy SegTree, PURS
DMOPCVery Hard
Show TagsEuler Tour, PURS

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