Heavy-Light Decomposition (HLD)

Heavy-Light Decomposition (HLD)

트리를 Heavy Edge와 Light Edge로 분류하여 Heavy Path들의 체인으로 분해하는 기법으로, 경로 쿼리와 갱신을 O(log^2 N) 또는 O(log N)에 처리

목적: 트리 경로 쿼리 최적화, 구간 자료구조 활용, 트리 DP

특징: Heavy/Light 분류, O(log N) 체인, 세그먼트 트리 결합, 경로 분해

Heavy Edge / Light Edge

• •Heavy Edge: 가장 큰 서브트리의 자식으로 가는 간선
• •Light Edge: 나머지 간선
• •루트에서 임의 노드까지 Light Edge 최대 O(log N)개

분해 과정

Euler Tour와 결합: 각 체인을 세그먼트 트리의 연속 구간에 매핑

경로 쿼리 처리

시간 복잡도: 전처리 O(N), 쿼리/갱신 O(log^2 N) 또는 O(log N)

공간 복잡도: O(N)

장점: 트리 경로 쿼리 효율화, 세그먼트 트리 활용, 다양한 쿼리 지원

단점: 구현 복잡도, 상수 크기, 트리 전용

적용사례: 경로 합/최대/최소 쿼리, 경로 갱신, 트리 경로 문제

비교: HLD(O(log^2 N)/범용) vs Link-Cut Tree(O(log N)/동적) vs Euler Tour(서브트리)

연관: 세그먼트 트리, LCA, 트리, 경로 쿼리, Link-Cut Tree