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++

1const int MX = 2e5+5;
2vector<int> adj[MX];
3int timer = 0, st[MX], en[MX];
4
5void dfs(int node, int parent) {
6 st[node] = timer++;
7 for (int i : adj[node]) {
8 if (i != parent) {
9 dfs(i, node);
10 }

Java

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

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

example input

Solution - Subtree Queries

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

C++

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

Java

1import java.util.*;
2import java.io.*;
3
4public class Main {
5 public static int[] st;
6 public static int[] en;
7 public static int timer, n;
8 public static ArrayList<Integer> g[];
9
10 //Segtree code

LCA

Focus Problem – read through this problem before continuing!

Focus Problem – read through this problem before continuing!

Tutorial

Implementation

Resources
Benq

C++

1int n; // The number of nodes in the graph
2vector<int> graph[100000];
3int timer = 0, tin[100000], euler_tour[200000];
4int segtree[800000]; // Segment tree for RMQ
5
6void dfs(int node = 0, int parent = -1) {
7 tin[node] = timer; // The time when we first visit a node
8 euler_tour[timer++] = node;
9 for (int i : graph[node]) {
10 if (i != parent) {

Java

1import java.util.*;
2import java.io.*;
3
4public class LCA {
5 public static int[] euler_tour, tin;
6 public static int timer, size, N;
7 public static ArrayList<Integer> g[];
8
9 //Segtree code
10 public static final int maxsize = (int)1e7; // limit for array size

Sparse Tables

The above code does O(N)O(N) time preprocessing and allows LCA queries in O(logN)O(\log N) time. If we replace the segment tree that computes minimums with a sparse table, then we do O(NlogN)O(N\log N) time preprocessing and query in O(1)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)O(N), but such algorithms are not needed in competitive programming.

Ex. the following:

Implementation

C++

Resources
Benq

Problems

StatusSourceProblem NameDifficultyTagsSolution
CSESNormal
Show Tags

Euler-Tree, PURS

GoldNormal
Show Tags

Euler-Tree, PURS, HLD

GoldNormal
Show Tags

Euler-Tree, LCA

External Sol
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:

Give Us Feedback on Euler Tour Technique!

PrevNext