트리 쿼리 알고리즘 비교: Euler Tour Tree vs Heavy-Light Decomposition

트리 쿼리 알고리즘 비교: Euler Tour Tree vs Heavy-Light Decomposition

지금까지 우리는 트리 쿼리를 처리하는 다양한 알고리즘 중
**Euler Tour Tree (ETT)**와 **Heavy-Light Decomposition (HLD)**를 학습해왔습니다.
이번 글에서는 두 방법론을 성능, 유연성, 적용 가능 문제 유형 관점에서 비교해보고,
실전에서 어떤 상황에 어떤 기법을 선택할지 기준을 제시합니다.

---

✅ 공통 목표: 트리 쿼리를 빠르게 처리

트리에서 다음과 같은 쿼리를 빠르게 처리하고자 할 때:

• 경로의 합/최댓값/최솟값
• 경로에 대한 업데이트
• 서브트리 통계 계산
• 노드 색칠 및 통계
• 동적 트리 간선 연결/삭제

우리는 보통 ETT, HLD, LCT 중 하나를 선택하게 됩니다.
이번 글에서는 그 중 ETT vs HLD를 집중 비교합니다.

---

🧠 Euler Tour Tree (ETT): 개념 정리

• DFS를 통해 트리를 배열로 펼쳐 in[u], out[u] 인덱스를 기록
• in[u] ~ out[u] 범위가 서브트리에 해당
• 이 배열에 대해 세그먼트 트리 or BIT로 쿼리 처리

장점

• 구현이 쉽고 직관적
• 서브트리 쿼리에 매우 강력
• 노드 개수의 2배 배열로 관리 → 구간처리 편리

단점

• 경로 쿼리에 직접 사용하기 어려움 (보통 LCA, HLD 필요)
• 정적 트리에만 사용 가능

---

🧠 Heavy-Light Decomposition (HLD): 개념 정리

반응형

• 트리를 체인으로 나누고, 각 체인별로 세그먼트 트리 적용
• 경로 질의를 체인 단위로 분할 처리

장점

• 경로 쿼리 처리가 강력 (합/최댓값/업데이트)
• 경로 → O(log N)개의 체인으로 분할 가능
• 정적 쿼리에서 매우 빠른 처리 가능 (O(log² N) 또는 O(log N))

단점

• 구현 난이도 중간 이상
• 서브트리 쿼리는 추가 구현 필요
• 트리 변경은 불가능 (정적 트리 전제)

---

📊 정리 비교표

항목 Euler Tour Tree (ETT) Heavy-Light Decomposition (HLD)

구현 난이도	낮음	중간
경로 쿼리	❌ 어려움 (보조 필요)	✅ 매우 강함
서브트리 쿼리	✅ 매우 강함	⚠️ 약함 (보완 필요)
동적 트리 지원	❌ 안 됨	❌ 안 됨
Lazy Propagation	✅ 쉬움	✅ 가능하지만 구현 복잡
배열 크기	2 * N	N
LCA 활용 여부	보통 필요	보통 불필요
노드 색 통계 등	매우 유리	일반 구현에선 불편

---

💡 실전에서 선택 기준

문제 유형 추천 알고리즘

서브트리 합, 색 통계, 노드 수	ETT
경로 질의, 경로 업데이트	HLD
노드/간선 변경 포함 트리	❌ (LCT 필요)
간단한 쿼리 & 빠른 구현이 필요할 때	ETT or 간단한 HLD

---

✅ 실전 문제 추천

문제 제목 기법 추천 플랫폼

백준 13510 트리 쿼리	HLD + Lazy	BOJ
AtCoder ABC 222E	ETT	AtCoder
Codeforces 1328E	HLD	CF
Library Contest Tree	ETT or HLD	기타

---

✅ 결론 요약

• ETT는 서브트리 문제에 강하다, HLD는 경로 문제에 강하다
• 둘 다 정적 트리에 적합하고, Lazy Propagation과 세그먼트 트리를 결합 가능
• 자신의 문제에 따라 필요한 연산을 기준으로 선택할 것

👉 다음 글에서는 Link/Cut Tree, Euler Tour Tree, HLD를 종합해
트리 기반 알고리즘 마스터 로드맵을 정리합니다.

---

📚 참고자료

• CP-Algorithms – Tree Algorithms Overview
• AtCoder, Codeforces Editorials
• Stanford CS166 – Tree Data Structures
• USACO Camp – Tree Path Queries

---

 

EulerTourTree, HeavyLightDecomposition, 트리쿼리비교, pathQuery, 서브트리Query, 정적트리, 세그먼트트리, 파이썬알고리즘, 알고리즘선택가이드, SEO 최적화 10개