Euler Tour Technique

Introduction

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

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.

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

Solution - Subtree Queries

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

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

LCA

Tutorial

Implementation

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

Sparse Tables

The above code does $O(N)$ time preprocessing and allows LCA queries in $O(\log N)$ time. If we replace the segment tree that computes minimums with a sparse table, then we do $O(N\log N)$ time preprocessing and query in $O(1)$ time.

Resources

Implementation

Problems