Heavy Light Decomposition

Heavy Light Decomposition(HLD)은 트리 위의 임의의 두 점을 지나는 경로가 $O(logN)$개의 직선만 지나도록 트리를 직선들로 나누는 것을 말한다. 직선에 세그먼트 트리를 넣는다면 여러 쿼리 연산을 쉽게 처리할 수 있다.

HLD를 이해하는 데에는 다음과 같은 링크가 도움이 된다.

• 한국말로 쉽게 설명이 되어 있다.

http://theyearlyprophet.com/heavy-light-decomposition.html

• 위의 링크보다 코드 구현이 간단하다. 영어가 된다면 이걸 보는게 더 좋을 것 같다.

https://blog.anudeep2011.com/heavy-light-decomposition/