Euler Tour and Subtree Queries

advanced30 min

The idea

Tree queries are awkward. Range queries on an array are well understood — prefix sums, Fenwick trees, segment trees all apply. The Euler tour converts one into the other.

Record the order in which a depth-first traversal enters and leaves each node. Then every subtree occupies one contiguous block of that ordering. A question about a subtree becomes a question about a range, and the full array toolkit becomes available.

Building the tour

Assign each node an entry time and an exit time.

static int[] tin, tout;
static int timer = 0;

static void dfs(int u, int parent) {
    tin[u] = timer++;
    for (int v : adj.get(u)) {
        if (v == parent) continue;
        dfs(v, u);
    }
    tout[u] = timer;                    // exclusive end
}

After this, the subtree of u is exactly the index range [tin[u], tout[u]). Its size is tout[u] - tin[u].

Two facts that make this work

Subtree as a range. Every descendant of u is entered after u and before the traversal leaves u, so their entry times all fall in [tin[u], tout[u]). Nothing outside the subtree does.

Ancestor test in O(1). u is an ancestor of v exactly when:

boolean isAncestor = tin[u] <= tin[v] && tout[v] <= tout[u];

That is a nesting check on intervals, and it replaces what would otherwise be a walk up the tree.

Using an exclusive tout — assigned after the children, without incrementing again — keeps the range half-open, which matches how array ranges are normally written and avoids +1/-1 confusion.

Flattening values

Place each node’s value at its entry index. Now a subtree’s values are a contiguous slice.

long[] flat = new long[n];
for (int u = 1; u <= n; u++) {
    flat[tin[u]] = value[u];
}

For queries with no updates, a prefix sum over flat answers “sum of values in a subtree” in O(1):

long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + flat[i];

long subtreeSum(int u) {
    return pre[tout[u]] - pre[tin[u]];
}

See Prefix Sums and Difference Arrays.

With updates

When values change between queries, replace the prefix sum with a Fenwick tree. Point update, prefix query, both O(log N).

static long[] bit;
static int n;

static void update(int i, long delta) {     // 0-based index
    for (int x = i + 1; x <= n; x += x & -x) {
        bit[x] += delta;
    }
}

static long prefix(int i) {                 // sum of [0, i)
    long s = 0;
    for (int x = i; x > 0; x -= x & -x) {
        s += bit[x];
    }
    return s;
}

static long subtreeSum(int u) {
    return prefix(tout[u]) - prefix(tin[u]);
}

static void setNodeValue(int u, long newValue) {
    update(tin[u], newValue - currentValue[u]);
    currentValue[u] = newValue;
}

The x & -x idiom isolates the lowest set bit, which is how a Fenwick tree walks its implicit structure. Note the internal array is 1-indexed while the interface is 0-indexed — mixing those up is the usual source of bugs here.

Updating a whole subtree

Reverse the roles. To add a value to every node in a subtree and later read individual nodes, use a difference array over the tour, or a Fenwick tree in range-update/point-query mode.

static void addToSubtree(int u, long delta) {
    update(tin[u], delta);
    update(tout[u], -delta);
}

static long nodeValue(int u) {
    return prefix(tin[u] + 1);           // accumulated deltas covering this position
}

Because the subtree is a contiguous range, a range update is two point updates on the difference structure — exactly the trick from the difference-array lesson, applied to the flattened tree.

What the flattening buys you

Tree question	Becomes	Structure
Sum over a subtree, no updates	Range sum	Prefix sums — O(1)
Sum over a subtree, with point updates	Range sum, point update	Fenwick tree — O(log N)
Add to every node in a subtree, read one node	Range update, point query	Difference + Fenwick — O(log N)
Is u an ancestor of v?	Interval nesting	`tin`/`tout` compare — O(1)
Min or max over a subtree	Range min/max	Segment tree — O(log N)
Count distinct values in a subtree	Range distinct count	Offline, sort queries by range

Path queries need more

The Euler tour handles subtrees, not arbitrary paths. A path between two nodes is generally not contiguous in the tour.

Two common workarounds:

Root-to-node paths can be handled with a running accumulation during the DFS, which is often enough — a path between u and v decomposes into root-to-u plus root-to-v minus twice root-to-their-lowest-common-ancestor.
Arbitrary paths with updates need heavy-light decomposition, which splits the tree into chains so a path spans O(log N) contiguous ranges. That is a substantial step up in complexity and rarely required.

Common mistakes

Off-by-one in the range. With exclusive tout, the subtree is [tin[u], tout[u]). Do not add 1.
Incrementing the timer twice. Assign tout[u] = timer without another increment if you want the half-open form.
Mixing 0-based and 1-based between the tour and the Fenwick tree.
Stack overflow on a deep tree. Same fix as any tree recursion — see Dynamic Programming on Trees.
Trying to answer path queries with a plain Euler tour.
Rebuilding the tour per query. Build it once.

Practice

Trees with up to 200,000 nodes and 200,000 queries.

Print the size of every subtree using tin and tout only.
Answer queries asking the sum of values in a node’s subtree, with no updates.
Same, but values can be updated between queries.
Support “add v to every node in the subtree of u” and “print the value at node u”.
Answer queries asking whether one node is an ancestor of another, in O(1) per query.

Hints

tout[u] - tin[u].
Flatten, then prefix sums.
Flatten, then a Fenwick tree; the query is a difference of two prefixes.
The range-update / point-query form — two point updates per subtree update.
The interval nesting comparison.

Dynamic Programming on Trees Segment Trees Prefix Sums and Difference Arrays Trees