[Algorithm | Python] HeavyLight Decomposition (HLD)

ㅎㄹㄷ

올려야지, 올려야지 하고 하던 걸 이제야 정리. 아직 완성되지 않았다

 

HeavyLight Decomposition (HLD)는 트리에서의 쿼리를 효율적으로 수행하도록 하는 테크닉이다.

 

다음과 같은 두 쿼리가 있다.

1. 트리의 정점 $u$ 에서 $v$ 로 가는 경로 중 가장 큰 가중치를 가진 정점을 찾는 쿼리

2. 정점의 가중치를 바꾸는 쿼리

 

배열에서 위 쿼리들을 처리하는 것은 간단하다. 세그먼트 트리나 펜윅 트리를 사용하면 $O(QlogN)$에 해결할 수 있다. 하지만 이는 배열이 선형인 점을 활용한 풀이법이기에, 비선형 자료구조인 트리에는 적용할 수 없다.

 

트리를 적당히 나눠서, 나눈 구간을 세그먼트 트리로 관리하면 어떨까? 라는 발상에서 나온 게 오늘 다룰 HeavyLight Decomposition이라고 하는 테크닉이다. 그래프의 간선을 무거운(Heavy) 것과 가벼운(Light) 것으로 분할(Decomposition)한다는 이야기다. 자세히 이야기하면 Heavy edge와 Light edge를 사용해 트리를 독립적인 경로(chain, path)들로 나누는 작업이다.

 

그렇다면 HLD에서의 가볍고 무거운 간선의 기준은 어떻게 될까? 위의 쿼리만 보면 가중치로 오해하기 쉽지만, HLD에서의 Light/Heavy Edge를 나누는 기준은 조금 다르다.

 

HLD에서의 간선을 구분하는 기준은 서브트리에 있다. 정점 $u$ 에서 자식 정점 $v$ 로 가는 간선이 있을 때, $v$ 를 루트로 하는 서브트리의 크기가 $u$ 를 루트로 하는 서브트리의 크기의 반 이상인 경우, 그 간선을 heavy하다고 하고, 그렇지 않으면 light하다고 한다.

이 때, 정점 $u$ 는 최대 한 개의 자식을 향한 Heavy Edge를 가진다는 점을 활용한다.

 

$u$ 가 $v$ 와 $w$를 자식으로 가진다고 하고, $(u, v)$ 와 $(u, w)$가 모두 heavy edge라고 한다면

$size(v)+size(w) > \frac{1}{2}size(u)+\frac{1}{2}size(u) = size(u)$ 이다.

하지만 $size(u)\geq size(v)+size(w)+1$ 에 따라 모순이 발생하므로

$u$ 는 최대 한 개의 자식을 향한 heavy edge를 가진다.

 

그렇게 되면 하나의 정점에서는 부모에게서 오는 하나의 Heavy edge와, 자식으로 뻗는 Heavy edge로 최대 두 개를 가질 수 있다. 하나의 그래프에서 Heavy Edge만 남기고 나머지를 지워 보면, 여러 개의 경로(chain)가 나타난다. 이를 체인이라고도 하는데, 이 체인들은 트리를 나누는(분해하는) 하나의 방법이 된다. 나아가 각 체인들은 트리의 리프 노드에서 루트 노드로 향할 때 지나야 하는 경로에 위치해있기도 하다.

 

$N$ 개의 정점으로 이루어진 그래프가 있다고 하자. 해당 그래프의 루트 노드에서 오직 Light Edge만을 타고 리프에 도달하려면, 최악의 경우 몇 번 내려가야 할까?

첫 번째 Light Edge를 타고 내려간 정점의 크기는 위 Heavy edge 조건에 의해 커봐야 $\frac{N}{2}$ 이다. 한 번 더 Light edge를 타고 내려간 정점의 크기는 커봐야 $\frac{N}{2^2}$ 가 될 것이다. 

따라서 어떤 경로에서든 루트에서 리프까지 도달하는 데 거치는 Light edge의 개수는 $O(logN)$이라는 결론이 나온다. 이게 쿼리를 효율적으로 수행하는 열쇠다.

 

이제 Light edge를 많이 타 봐야 $O(logN)$ 번만에 루트에 도달하는 것을 알았다. 그럼 Heavy edge는 어디에 사용할까?

위에서 Heavy edge들을 묶어 여러 개의 체인으로 나타낸다는 것을 보였다. 아래 트리를 보자.

이제 트리를 보고 각 간선이 Heavy한지, Light한지를 판단할 수 있다! 트리에서의 Heavy edge에 색을 입히면 아래와 같다.

인접한 Heavy edge는 같은 색으로 칠했다. 검은색 간선은 Light edge이다.

인접한 Heavy edge들을 묶어 하나의 체인으로 만들었다! 각 체인들은 리프에서 루트로 향할 때 건너는 경로에 포함되기도 한다.

모든 체인은 선형이라는 것이 아주 중요한 사실이다. 트리의 비선형적인 특징 때문에 세그먼트 트리를 적용하지 못했지만, 이제는 각 체인에 대해 세그먼트 트리를 만들어 관리할 수 있다. 트리에서는 루트에서 리프까지 가는 데 Light edge를 많아 봐야 $logN$번 거친다는 것을 보였기 때문에, 정말 많이 봐 봤자 $O(logN)$ 개의 체인만 확인하면 된다.

 

우리가 하고자 하는 것은 위의 두 쿼리를 효율적으로 연산하도록 하는 것이다. 정점 $u$ 에서 $v$ 로 가는 길에 Heavy chain은 $O(logN)$개 존재하고, 각 경로에 대해서 세그먼트 트리의 연산($O(logN)$)을 수행하면 된다. 따라서 이론적인 시간복잡도는 $O(Qlog^2N)$이 된다.

 

코드를 짜 보자! 나는 지금까지 PS를 계속 파이썬으로 고집해와서(...) 파이썬으로 작성한다. C++는 충분히 많은 자료가 있으니 참고해도 좋겠다~!

<구현 추가예정>