PrevNext
Not Frequent
 0/11

Euler Tour Technique

Authors: Benjamin Qi, Andi Qu, Andrew Wang

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

Introduction

Focus Problem – read through 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
CPHintroduces tree traversal array, how to solve above problem
SecondThread

Implementation

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

C++

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

Java

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

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

example input

Solution - Subtree Queries

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

C++

/**
* 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
*/

Java

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

Focus Problem – read through this problem before continuing!

Focus Problem – read through 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.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 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 – read through this problem before continuing!

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 NameDifficultyTagsSolutionURL
CSESNormal
Show Tags

Euler-Tree, PURS

GoldNormal
Show Tags

Euler-Tree, PURS, HLD

GoldNormal
Show Tags

Euler-Tree, LCA

PlatNormal
Show Tags

Euler-Tree, PURS

External Sol
IOIHard
Show Tags

Euler-Tree, Binary Search

External Sol
PlatHard
Show Tags

Euler-Tree, PURS

External Sol
DMOJVery Hard
Show Tags

Euler-Tree, PURS

Check DMOJ

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!

Give Us Feedback on Euler Tour Technique!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext