오일러 투어 테크닉 (Euler Tour Technique)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 6분 · 2,054자/단어 #algorithm #tree #euler-tour #flattening #range-query

정의

오일러 투어 테크닉 (ETT, Euler Tour Technique) 은 트리를 DFS 방문 순서로 펼쳐 서브트리 쿼리를 구간 쿼리로 변환하는 정형. 각 노드 u 의 in-time tin[u], out-time tout[u] 를 기록하면, u 의 서브트리 = 구간 [tin[u], tout[u]] 로 표현되어 세그먼트 트리, 펜윅 트리 등 구간 자료구조에서 O(log N) 쿼리.

문제 상황과 동기

트리에서 “u 의 서브트리에 속한 모든 노드의 합 / 최댓값 / 개수” 를 Q 번 묻는다.

naive: 매 쿼리마다 서브트리 전체 DFS. O(N · Q). N=Q=10^5 면 10^10.
ETT + Segtree: O(N) 전처리 + O(log N) 쿼리. 총 O(N + Q log N).

핵심 통찰: 트리의 서브트리는 DFS 방문 순서에서 연속 구간. 따라서 트리 문제를 배열 문제로 환원.

시각화

핵심 아이디어

invariant: DFS 방문 순서대로 노드를 나열하면, u 의 서브트리 = [tin[u], tout[u]].

tin[u] = DFS 진입 시각
tout[u] = DFS 퇴각 시각

is_ancestor(u, v) = tin[u] <= tin[v] && tout[v] <= tout[u]
subtree_range(u) = [tin[u], tout[u]]

확장:

서브트리 갱신: 구간 갱신 (lazy propagation).
경로 쿼리 + HLD: HLD 와 결합하면 경로도 O(log^2 N).
LCA + RMQ: 오일러 투어 순서 위에 depth 배열로 LCA 를 O(1) RMQ 로.

알고리즘

dfs(u, parent):
    tin[u] = timer++
    euler[timer - 1] = u             # in-time 에 노드 기록
    for v in adj[u]:
        if v != parent:
            dfs(v, u)
    tout[u] = timer++
    euler[timer - 1] = u             # out-time 에 노드 기록 (선택)

build_euler_tour(root):
    timer = 0
    dfs(root, -1)

subtree_query(u):
    # u 의 서브트리 노드들은 euler[tin[u]..tout[u]] 에 모두 포함
    return range_query(segtree, tin[u], tout[u])

구현

// Euler Tour + 서브트리 합 쿼리 (Fenwick)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
vector<int> adj[MAXN];
int tin[MAXN], tout[MAXN], timer = 0;
long long val[MAXN], fenwick[MAXN * 2 + 5];
int N;

void update(int i, long long delta) {
  for (; i <= 2 * N; i += i & -i) fenwick[i] += delta;
}

long long query(int i) {
  long long res = 0;
  for (; i > 0; i -= i & -i) res += fenwick[i];
  return res;
}

void dfs(int u, int p) {
  tin[u] = ++timer;
  update(tin[u], val[u]);
  for (int v : adj[u]) if (v != p) dfs(v, u);
  tout[u] = timer;
}

int main() {
  int Q; cin >> N >> Q;
  for (int i = 0; i < N; i++) cin >> val[i];
  for (int i = 0; i < N - 1; i++) {
      int a, b; cin >> a >> b; a--; b--;
      adj[a].push_back(b); adj[b].push_back(a);
  }
  dfs(0, -1);
  while (Q--) {
      int u; cin >> u; u--;
      cout << query(tout[u]) - query(tin[u] - 1) << "\n";
  }
}

# Euler Tour + 서브트리 합
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, Q = map(int, input().split())
val = list(map(int, input().split()))
adj = [[] for _ in range(N)]
for _ in range(N - 1):
  a, b = map(int, input().split())
  a -= 1; b -= 1
  adj[a].append(b); adj[b].append(a)

tin = [0] * N
tout = [0] * N
timer = [0]

def dfs(u, p):
  timer[0] += 1
  tin[u] = timer[0]
  for v in adj[u]:
      if v != p:
          dfs(v, u)
  tout[u] = timer[0]

dfs(0, -1)

# 서브트리 합 = val[tin[u]..tout[u]] 구간 합
# prefix sum 으로 구현
prefix = [0] * (2 * N + 5)
for i in range(N):
  prefix[tin[i]] += val[i]
for i in range(1, 2 * N + 1):
  prefix[i] += prefix[i - 1]

out = []
for _ in range(Q):
  u = int(input()) - 1
  out.append(str(prefix[tout[u]] - prefix[tin[u] - 1]))
print("\n".join(out))

// Euler Tour + 서브트리 합
import java.util.*;
import java.io.*;
public class Main {
  static List<Integer>[] adj;
  static int[] tin, tout, val;
  static long[] prefix;
  static int timer = 0, N;

  static void dfs(int u, int p) {
      tin[u] = ++timer;
      for (int v : adj[u]) if (v != p) dfs(v, u);
      tout[u] = timer;
  }

  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      int Q = Integer.parseInt(st.nextToken());
      val = new int[N];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < N; i++) val[i] = Integer.parseInt(st.nextToken());
      adj = new ArrayList[N];
      for (int i = 0; i < N; i++) adj[i] = new ArrayList<>();
      for (int i = 0; i < N - 1; i++) {
          st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st.nextToken()) - 1;
          int b = Integer.parseInt(st.nextToken()) - 1;
          adj[a].add(b); adj[b].add(a);
      }
      tin = new int[N];
      tout = new int[N];
      dfs(0, -1);
      prefix = new long[2 * N + 5];
      for (int i = 0; i < N; i++) prefix[tin[i]] += val[i];
      for (int i = 1; i <= 2 * N; i++) prefix[i] += prefix[i - 1];
      StringBuilder sb = new StringBuilder();
      while (Q-- > 0) {
          int u = Integer.parseInt(br.readLine()) - 1;
          sb.append(prefix[tout[u]] - prefix[tin[u] - 1]).append('\n');
      }
      System.out.print(sb);
  }
}

stdin

결과

15
11
3

복잡도

항목	값
전처리 (DFS)	O(N) 시간, O(N) 공간
쿼리 (Segtree/Fenwick)	O(log N) 시간
전체	O(N + Q log N)

변형 / 활용

응용	설명
서브트리 갱신	구간 갱신 (lazy propagation)
LCA via RMQ	오일러 투어 순서에 depth 배열 → [[Sparse Table
경로 쿼리 + HLD	[[Heavy-Light Decomposition
동적 트리	[[Link-Cut Tree
재귀 없는 DFS	스택으로 in/out 시각 기록 가능

함정

1. in-time / out-time 혼동

tin[u] 는 DFS 진입, tout[u] 는 퇴각. 서브트리 구간은 [tin[u], tout[u]] (inclusive).

2. 0-indexed vs 1-indexed

Fenwick / Segtree 가 1-indexed 면 tin, tout 도 1-indexed 로 맞춰야. Python 은 0-indexed 가 자연스러움.

3. 서브트리만 가능, 경로는 HLD 필요

ETT 단독으로는 서브트리 쿼리만 O(log N). 경로 쿼리는 HLD 필요.

4. out-time 에 노드 중복 기록?

구현에 따라 euler 배열에 노드를 in/out 두 번 넣거나, in 만 넣거나. 서브트리 크기 계산 시 주의.

BOJ 예시 문제 풀이

Euler tour 를 실전에서 어떻게 활용하는지 4개의 대표 문제를 풀이 흐름으로 정리합니다. 원문 링크는 kokoa-lab boj-problems 저장소에서 확인할 수 있습니다.

BOJ 15681: 트리와 쿼리

문제 요약: 루트 $R$ 이 주어진 트리에서 각 정점 $u$ 를 루트로 하는 서브트리의 노드 개수를 여러 번 묻습니다.

N ≤ 10^5, Q ≤ 10^5

전형적 ETT. 서브트리 크기 자체가 답이므로 세그먼트 트리도 불필요.

풀이 흐름:

루트에서 DFS 를 돌며 tin[u], tout[u] 를 기록.
서브트리 크기 = tout[u] - tin[u] + 1 (in-time 만 카운트하는 경우) 또는 DFS 중 자식 크기 합.
쿼리마다 $u$ 의 서브트리 크기 반환.

dfs(u, parent):
    tin[u] = timer++
    size[u] = 1
    for v in adj[u]:
        if v != parent:
            dfs(v, u)
            size[u] += size[v]
    tout[u] = timer

query(u): return size[u]

시간 복잡도: 전처리 O(N), 쿼리 O(1). 매우 단순.

교훈: ETT 의 in/out-time 없이도 서브트리 크기 자체는 자식 크기 합으로 계산. 하지만 tin, tout 을 저장해두면 범위 쿼리 로 확장 가능하다는 점이 핵심.

확장 (합 버전): 각 정점에 값이 있다면 Fenwick 로 [tin[u], tout[u]] 구간 합 = 서브트리 합.

BOJ 원문: BOJ 15681

BOJ 13511: 트리와 쿼리 2

문제 요약: 가중치 트리에서 두 정점 $u, v$ 사이 경로 위:

간선 가중치의 합
경로 위 $k$ 번째 정점

N ≤ 10^5, Q ≤ 10^5

ETT 단독으로는 부족. 경로 쿼리는 LCA + prefix sum (또는 HLD) 필요.

풀이 흐름:

DFS 로 depth[u], distFromRoot[u] (루트에서 u 까지 간선 가중치 합) 계산. 동시에 tin[u] 를 기록해 오일러 투어 순서 확보.
Binary Lifting 으로 up[u][i] (2^i 조상) 테이블 구축.
쿼리 1 (경로 합): ${p a t h S u m} (u, v) = {d i s tF r o m R oo t} (u) + {d i s tF r o m R oo t} (v) - 2 \cdot {d i s tF r o m R oo t} ({l c a} (u, v))$ 자세한 것은 Path sum on tree 참조 (간선 가중치이므로 LCA 값 보정 없음).
쿼리 2 (k번째 정점):
- $L = {l c a} (u, v)$
- $u \to L$ 방향의 정점 수: ${d e pt h} (u) - {d e pt h} (L) + 1$
- $k$ 가 이 개수 이하 -> $u$ 의 $(k - 1)$ 번째 조상
- 아니면 $v$ 의 $({d e pt h} (u) + {d e pt h} (v) - 2 \cdot {d e pt h} (L) - k + 1)$ 번째 조상 (즉 $v \to L$ 반대 방향)
- 조상 찾기는 K번째 조상.

교훈: 경로 문제는 ETT 만으로 불가능. ETT + Binary Lifting + LCA 조합이 정통. HLD 도 대안이지만 구현 부담.

BOJ 원문: BOJ 13511

BOJ 17435: 합성함수와 쿼리

문제 요약: 함수 $f : {1, ..., m} \to {1, ..., m}$ 가 주어지고, 쿼리로 $(n, x)$ 에 대해 $f^{n} (x)$ (함수 $n$ 번 합성 결과) 를 구합니다.

m ≤ 200000, Q ≤ 200000, n ≤ 500000

엄밀히는 트리 문제 아님. 함수의 반복 적용은 functional graph 에서 다음 정점 따라가기와 동일. Binary lifting 이 그대로 적용.

풀이 흐름:

up[x][0] = f(x) (1번 적용).
up[x][i] = up[up[x][i-1]][i-1] (재귀 doubling).
쿼리 $(n, x)$ : $n$ 의 이진 표현대로 점프.

이는 트리 아닌 binary lifting 응용의 대표 예. Euler tour 와의 직접 연관은 약하지만, 트리 문제에서 doubling 사고를 배웠다면 자연스럽게 이 문제도 풀리는 관점이 형성됩니다.

교훈: doubling 은 트리에만 국한되지 않음. 결정적 이산 동역학 (deterministic discrete dynamics) 에 모두 적용 가능.

BOJ 원문: BOJ 17435

BOJ 3745: 오름세 (LIS)

문제 요약: 수열의 최장 증가 부분수열 (LIS) 길이.

N ≤ 200000

Euler tour 와 무관. 하지만 kokoa-lab 저장소 에서 함께 태그된 이유는 아마도:

패치 트리 이용 LIS: 트리 구조를 활용한 LIS 변형 문제군
Fenwick 로 LIS: dp[v] = 1 + max(dp[u] : u < v && val[u] < val[v]) 를 Fenwick 로 O(N log N).

트리 자료구조 (Fenwick) 를 이용하지만 Euler tour 의 in/out-time 개념은 사용하지 않습니다.

풀이 흐름 (표준 LIS):

값 좌표압축.
Fenwick 을 값 도메인에 만들고 bit[v] = “지금까지 값 v 로 끝나는 LIS 최댓값”.
각 원소 $a_{i}$ 에 대해 dp[i] = 1 + query(1..a_i - 1), 그 후 update(a_i, dp[i]).

교훈: “트리 관련 자료구조” 문제와 “트리 위의 문제” 는 다름. Fenwick / Segment tree 는 배열 위에서도 강력한 도구.

BOJ 원문: BOJ 3745

참고

이 글의 용어 (9개)

세그먼트 트리 (Segment Tree)algorithm: 정의 세그먼트 트리 (Segment Tree) 는 배열의 구간 쿼리 (range query) 와 점 갱신 (point update) 를 모두 O(log N) 에 처리하는 이진 트…
최소 공통 조상 (Lowest Common Ancestor)algorithm: 정의 최소 공통 조상 (LCA, Lowest Common Ancestor) 는 트리에서 두 노드 u, v 의 공통 조상 중 가장 깊은 (루트에서 가장 먼) 노드. Binary L…
트리 경로 합 (Path Sum on Tree)algorithm: 정의 트리 경로 합 (Path Sum on Tree) 는 트리에서 두 정점 $u, v$ 사이의 유일 경로 위 정점 (또는 간선) 값의 합 을 구하는 문제입니다. 문제 상황은 크게…
희소 배열 (Sparse Table)algorithm: 정의 희소 배열 (Sparse Table) 은 정적 배열에서 결합 법칙을 만족하는 idempotent 연산 (min, max, gcd, lcm 등) 의 구간 쿼리를 O(1) 시간…
Binary Lifting: 2의 지수 doublingalgorithm: 정의 Binary Lifting (이진 상승, doubling) 은 트리 (또는 functional graph) 에서 정점의 $2^k$ 번째 조상 을 미리 계산해 두어 임의의 $…
Dynamic Tree (Link/Cut Tree, Euler Tour Tree, Top Tree)algorithm: 정의 Dynamic Tree 는 트리에 간선 추가 (link) / 제거 (cut) 가 섞이는 환경에서 경로 / 서브트리 집계 쿼리 를 O(log N) 에 처리하는 자료구조 가족.…
Fenwick Tree (Binary Indexed Tree): 구간 합 O(log N)algorithm: 정의 Fenwick Tree (또는 BIT, Binary Indexed Tree) 는 배열의 prefix sum 을 O(log N) 에 갱신·조회 하는 자료구조입니다. Peter…
Heavy-Light Decompositionalgorithm: 정의 Heavy-Light Decomposition (HLD) 는 트리를 O(log N) 개의 경로 (chain) 로 분해해 임의 경로 쿼리 (u-v 경로의 합/최대/최소) 를 …
K번째 조상 (K-th Ancestor)algorithm: 정의 K번째 조상 문제 (K-th ancestor) 는 루트 트리에서 정점 $u$ 의 조상 중 $u$ 로부터 정확히 $k$ 만큼 위에 있는 정점 (즉, $u$ 의 $k$ 번째 부…

오일러 투어 테크닉 (Euler Tour Technique)

정의

문제 상황과 동기

시각화

핵심 아이디어

알고리즘

구현

복잡도

변형 / 활용

함정

1. in-time / out-time 혼동

2. 0-indexed vs 1-indexed

3. 서브트리만 가능, 경로는 HLD 필요

4. out-time 에 노드 중복 기록?

BOJ 예시 문제 풀이

BOJ 15681: 트리와 쿼리

BOJ 13511: 트리와 쿼리 2

BOJ 17435: 합성함수와 쿼리

BOJ 3745: 오름세 (LIS)

참고

이 개념을 다룬 위키 페이지 (8)

💬 댓글