Heavy-Light Decomposition (HLD)

개요

Heavy-Light Decomposition(HLD)은 트리 구조에서 경로 쿼리(Query)나 업데이트(Update)를 빠르게 처리하기 위해 고안된 분할 기법입니다. 트리의 간선을 무거운(Heavy) 간선과 가벼운(Light) 간선으로 분류하여, 경로를 소수의 구간(segment)으로 분해하고, 각 구간에 대해 세그먼트 트리(Segment Tree)나 펜윅 트리(Fenwick Tree) 같은 자료구조를 적용하여 O(log² n) 또는 O(log n) 시간 복잡도로 효율적인 처리를 가능하게 합니다.

---

1. 개념 및 정의

항목	내용
정의	트리를 Heavy 간선과 Light 간선으로 분할하여 경로 쿼리와 업데이트를 최적화하는 알고리즘적 테크닉
목적	트리 경로 질의의 시간 복잡도를 개선하여 고속 연산 지원
필요성	단순한 트리 탐색은 경로 쿼리에 대해 O(n) 시간이 걸려 비효율적임

HLD는 경로를 구간으로 변환함으로써, 트리 쿼리를 배열 쿼리처럼 빠르게 처리할 수 있게 합니다.

---

2. 특징

항목	HLD의 특징	유사 개념 비교
경로 분해	임의의 두 노드 사이 경로를 O(log n)개 구간으로 나눔	단순 DFS 탐색은 O(n) 시간 필요
세그먼트 트리 연계	분해된 구간 위에 세그먼트 트리를 구성	세그먼트 트리 단독 사용은 일반 배열 대상
동적 쿼리 최적화	경로 최대값, 최소값, 합계 등 다양한 질의 지원	Link-Cut Tree 대비 구현이 간단하고 빠름

HLD는 트리 경로 문제에 대해 실용적이면서 강력한 해법을 제공합니다.

---

3. 구성 요소

구성 요소	설명	역할
Heavy 간선	자식 중 가장 큰 서브트리를 연결하는 간선	깊이 있는 경로를 최대한 압축
Light 간선	나머지 모든 간선	경로 분해를 가능하게 함
Chain (사슬)	연속된 Heavy 간선들의 집합	경로를 최소 구간 수로 분해
세그먼트 트리	각 Chain 위에 구축되어 질의/업데이트 처리	구간 연산 최적화

이 구조를 통해 트리 쿼리를 효율적으로 배열 쿼리 형태로 변환할 수 있습니다.

---

4. 기술 요소

기술 요소	설명	적용 예시
DFS 기반 서브트리 크기 계산	트리를 순회하며 각 서브트리의 크기 측정	Heavy 간선 결정 기준 제공
HLD 재귀 분해	가장 큰 자식으로 Heavy 경로를 확장하고 나머지는 분리	Chain 구조를 형성
세그먼트 트리 질의/갱신	경로를 Chain 단위로 이동하며 구간 연산 수행	최댓값, 최솟값, 합계 등 지원

HLD는 DFS + 세그먼트 트리 + 경로 분할이 핵심 조합입니다.

---

5. 장점 및 이점

항목	내용	기대 효과
쿼리 시간 복잡도 감소	O(log² n) 또는 O(log n) 시간에 경로 질의 가능	대규모 트리에서도 고속 응답
다양한 연산 지원	최댓값, 최솟값, 합계, 경로 업데이트 등	문제 해결 유연성 증가
실용성과 구현 용이성	이론은 복잡하지만 실제 구현은 상대적으로 간단	알고리즘 대회, 그래프 문제에 최적

HLD는 트리 경로 문제를 해결하는 데 있어 실용성과 성능 모두를 갖춘 최고의 테크닉 중 하나입니다.

---

6. 주요 활용 사례 및 고려사항

사례	설명	고려사항
트리 경로 최대값 질의	임의의 두 노드 사이 최댓값 질의 최적화	Segment Tree 업데이트 전략 필요
경로 합계 및 업데이트	부분 경로 누적합 계산 및 수정	Lazy Propagation 최적화 고려 가능
그래프 기반 최적화 문제	도로망 관리, 통신 네트워크 최적화 등	사전 서브트리 크기 계산 정확성 중요

HLD 설계 시 Chain 인덱싱, 경로 이동 최적화, 세그먼트 트리 최적화까지 함께 고려해야 합니다.

---

7. 결론

Heavy-Light Decomposition은 트리 경로 질의 최적화를 위한 매우 강력한 알고리즘입니다. 빠른 성능, 다양한 질의 지원, 상대적 구현 용이성 덕분에 알고리즘 대회, 시스템 설계, 네트워크 최적화 등 광범위한 분야에서 활발히 활용되고 있습니다. 대규모 트리 데이터셋을 빠르게 다루려면 HLD는 사실상 필수적인 테크닉입니다.