Euler Tour Technique
Flatten a rooted tree into entry and exit times so subtree queries become interval queries on an array.
Euler Tour Technique
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Euler tour technique is the standard way to turn tree structure into array intervals. Once each subtree becomes one contiguous segment, the rest of the problem often becomes a Fenwick-tree or segment-tree task instead of a tree task.
When to Use It
Use Euler tour technique when:
queries are about subtrees of a rooted tree,
you want to map tree nodes to an array,
another array-based structure already solves the interval version.
Core Idea
Run DFS and record the entry time \(\texttt{tin[v]}\) of each node. If nodes are appended to an order array at entry time, then the subtree of \(v\) occupies one contiguous interval: \[ [\texttt{tin[v]}, \texttt{tout[v]}]. \]
Key Insight
DFS enters a subtree, finishes all of it, and only then leaves. That nesting property is exactly why every rooted subtree becomes a single interval in entry order.
Operations / Main Technique
root the tree,
DFS once to compute \(\texttt{tin}\), \(\texttt{tout}\), and the flattened order,
convert a subtree query into one array interval,
answer with Fenwick or segment tree if updates are also present.
Worked example.
If node \(v\) gets entry time \(7\) and its subtree ends at time \(12\), then ``sum over subtree \(v\)'' becomes ``sum over interval \([7,12]\)'' on the flattened array.
Correctness Intuition
During DFS, every node in the subtree of \(v\) is visited after entering \(v\) and before leaving it. No outside node can appear inside that interval, so the entry-order slice exactly matches the subtree.
Complexity Analysis
The flattening DFS is \(O(n)\). After that, the complexity is whatever interval structure is used on top of the order array.
Implementation
The code provides a reusable flattener with:
tin,tout,order,subtree interval accessors.
Common Pitfalls
Forgetting to root the tree consistently.
Confusing node times with edge times in edge-weighted tasks.
Assuming the same flattening also makes arbitrary paths contiguous. It usually does not.
Mixing inclusive and half-open interval conventions.
Variants / Extensions
Full Euler tour with entry and exit duplicates for LCA/RMQ style reductions.
Subtree add and subtree sum with a Fenwick or segment tree.
Mo on trees by combining an Euler tour with offline query ordering.
Practice Problems
Subtree sum with point updates.
Count colors or active markers inside subtrees.
Convert a tree DP precomputation into subtree interval updates.
References
Code
Contest-ready reference implementation for the idea explained above.
struct EulerTour {
vector<vector<int>> tree;
vector<int> tin;
vector<int> tout;
vector<int> order;
int timer = 0;
explicit EulerTour(int n) : tree(n), tin(n), tout(n), order(n) {}
void add_edge(int u, int v) {
tree[u].push_back(v);
tree[v].push_back(u);
}
void dfs(int v, int parent = -1) {
tin[v] = timer;
order[timer] = v;
++timer;
for (int to : tree[v]) {
if (to == parent) continue;
dfs(to, v);
}
tout[v] = timer - 1;
}
pair<int, int> subtree_interval(int v) const {
return {tin[v], tout[v]};
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.