Heavy-Light Decomposition

Introduction

트리를 분할하는 방법으로는 대표적으로 Centroid Decomposition과 Heavy-Light Decomposition이 있다. Centroid Decomposition의 경우, 주로 트리에서 분할정복을 위해 이용되며, Heavy-Light Decomposition은 우리가 다루기 더 쉬운 형태인 선형 배열의 형태로 트리를 바꾸어 문제를 해결하기 위하여 사용한다. 이번 포스팅에서는 Heavy-Light Decomposition을 다룬다.

 

Heavy-Light Decomposition

Heavy-Light Decomposition(HLD)는 트리의 정점을 여러 경로의 집합으로 나누는 방법이다.

HLD를 수행하기 위해서 일단 임의의 정점의 트리의 루트로 잡는다. 이후, 루트에서 부터 subtree의 크기가 가장 큰 자식을 선택해 나가는 방법으로 경로를 구성한다. 그렇게 형성된 경로를 제외하고 남은 forest의 각 subtree에서 같은 방법을 수행하면 된다.

HLD를 수행한 모습

HLD는 아이디어가 간단한 만큼 구현도 어렵지 않다. 트리에서의 동적계획법을 이용하여 subtree의 크기를 계산하고 그에 따라 분할을 진행하기만 하면 된다. 아래는 HLD를 구현한 코드이다.

https://github.com/P4rkingZ0eN/Well_Known/blob/main/HLD.cpp#L1

GitHub - P4rkingZ0eN/Well_Known: Famous Algorithm

 

마치며...

HLD가 중요한 이유는 우리가 선형 배열에서 합, 부분합, 최대, 최소 등을 구하는 행위를 segment tree를 이용하여 \(O(\log(N))\)에 처리할 수 있다든 데에 있다. HLD를 수행했을 경우 각각의 나눠진 경로(heavy path)에 대해서 로그 시간에 쿼리를 처리할 수 있다. 그렇기에 보통 HLD를 이용할 때는 segment tree를 함께 이용한다.