Graph/Tree

HLD (Heavy Light Decomposition)

unordered_map 2024. 10. 8. 01:12

https://justicehui.github.io/hard-algorithm/2020/01/24/hld/ : 이 글이 이론의 전반적인 이해에 큰 도움이 되었다. GOAT.

 

오일러 투어 테크닉, LCA 등의 쉬운 트리 이론은 트리 문제 하나로 전부 정리된다고 생각한다. 해당 문제를 풀 수 있으면 심화 트리 이론을 공부할 수 있는 것이고, 해당 문제를 풀 수 없다면 기초부터 다시 다지고 올라와야한다.

 

여기서 쉬운 트리 이론과 심화 트리 이론을 당당하게 나누어 말할 수 있는 이유는 난이도 차이가 실제로 매우 크기 때문이다.

 

심화 트리 이론의 첫 단계라고도 말할 수 있는 HLD는 쉬운 트리 이론은 물론이거니와 세그먼트 트리까지 완벽하게 장착하고 있어야 이해할 수 있는 이론이다. 반대로 말하면, 쉬운 트리 이론과 세그먼트 트리에 대한 이해도만 있다면 HLD를 이해하는 것은 그렇게 어렵지 않다. 2년 전에는 공부하는 과정에서 많이 허둥댔는데, 오랜만에 다시 보니 난해하지 않음을 새삼 깨닫는다.

 

IDEA MOTIVATION

 

HLD (Heavy Light Decomposition)은 트리의 경로에서 쿼리를 처리하는 방법론이다.

 

이미 오일러 투어 테크닉을 통해 서브트리에 대한 쿼리를 세그먼트 트리로 처리한 적은 있으나, 경로는 조금 이야기가 다르다. 서브트리는 정확히 N개이지만, 경로는 N(N-1)/2개가 나온다는 점부터 처리하기가 매우 까다로울 것으로 예상된다. 이를 조금 특이한 하나의 아이디어로, 시간복잡도 O(lgN)을 추가소비하여 해결하는 방법론이라고 설명하는 것이 가장 간단하다.

 

HLD의 Idea Motivation은 오일러 투어 테크닉을 그대로 계승하는 것에서 시작한다. 만약 루트에서 시작해서 가장 왼쪽으로만 계속 내려가는 경로였다면, 이미 세그먼트 트리 상에 해당 경로가 구간으로 존재할 것이다. 그렇다면 계속 왼쪽으로만 내려간다는 것의 확률을 높이면 되지 않을까?

 

따라서 HLD는 DFS를 2번 돌린다. 2번째 DFS는 오일러 투어 테크닉의 DFS와 동일하지만, 1번째 DFS는 자식 정점들을 정렬하는 과정이다. 사실 정렬까지 하지 않아도, 가장 size가 큰 서브트리를 가지는, Heavy한 자식 정점을 가장 왼쪽에 배치하면 우리가 원하는 바를 이룰 수 있다. 이렇게 정렬해주면, 어떤 노드에서 왼쪽으로 계속 내려가는 것은 '트리의 경로'이자, '세그먼트 트리의 구간'이 된다. 이를 하나의 '사슬'로 잡자.

 

이때, 임의의 경로에서 이용하는 '사슬'의 수는 최대 O(lgN)개임이 수학적으로 증명되며, 자세한 내용은 생략한다. 따라서 세그먼트 트리에 적절히 쿼리를 O(lgN)번 날림으로써 해결하는 것이 HLD의 풀이이다. 오일러 투어 테크닉을 그대로 계승했기에, 세그먼트 트리를 건드리지는 않았다. 그저 DFS order를 약간 손봐주었을 뿐이다. 이에 따라 일반적인 경우 전체 시간복잡도 O(Nlg^2N)에 문제가 해결된다.

 

장단점

 

구현이 생각보다 간단하다. 물론 당연히 하나의 문제에 DFS와 세그먼트 트리를 동시에 써야하니 미관상 간결하다고 말할 수는 없지만, 그래프와 세그먼트 트리가 완전히 분리되어있기 때문에 머리가 덜 아픈 편이다. 원하는 세그먼트 트리를 구현해주면 되고, 그래프와 연결할 때 in[ ]만 적용해주면 된다. 사실 이는 HLD 이전의 오일러 투어 테크닉의 장점이기도 하다.

 

단점은 아이디어가 기가 막히게 좋은 문제가 많지 않다. 그저 모르면 못 풀기에 공부하는 이론이며, 코드가 길지만 처음부터 끝까지 기계적으로 짜야한다. 다른 문제와 융합되면 하나로 합쳐지지 않고 그냥 1+1으로 따로 논다. 스킬 하나를 더 배웠지만 스킬콤보가 이루어지지 않는 느낌. 자신이 팀의 트리 담당이라면 잠자코 공부하도록 하자.

 

HLD 연습문제

 

남극 탐험 [BOJ 2927] (D5)

- HLD 기본 문제. 오프라인 쿼리임을 이용하면 추가 단계가 어렵지 않다.

- 온라인 쿼리 버전도 있다.

 

국제 메시 기구 [BOJ 17429] (D4)

- HLD + Lazy Propagation

- HLD의 장점, seg에서 lazyseg로 바꿔주기만 하면 동일한 구현으로 해결된다.

- mod 2^32는 unsigned int를 사용하고 자연스럽게 overflow가 일어나도록 두면 된다.

 

안전한 비상연락망 [BOJ 10169] (D4)

- HLD + Lazy Minimum

- 디테일이 좀 많으니 컨디션 좋은 날, 흐름 끊기지 않고 구현할 것!

- 경로의 간선에 쿼리를 칠 때는 LCA를 제외하고 구간 쿼리를 적용해야한다. (쿼리를 한 번만 날리는 간단한 방법이 없을지 고민해보았으나 찾지는 못했다.)

 

트리와 쿼리 10 [BOJ 13519] (D3)

- HLD + Lazy Mine

- HLD에서 교환법칙이 성립하지 않는 요소들을 적용하기 위해서는 순서와 방향을 잘 고려해주어야 한다.

- HLD의 기본 방법론은 건드리지 않지만 기본 코드를 건드릴 수 있어야 해결할 수 있다.

- 이 문제에서 Trouble Shooting의 필요성과 방법론을 혼자 떠올렸다면 HLD를 다룰 수 있다고 말할 수 있을 것 같다.