이 글로 이동해주세요!!
전에 HLD 설명글을 쓴 적이 있습니다. 그러나 그 글에 설명되어있는 방식보다 더 쉽게 구현하는 방법이 있어 소개하고자 합니다.
이 글을 많이 참고하였습니다.
목차
- 우리는 뭘 해야 하죠? - 처리해야 할 두 가지의 쿼리를 알아봅시다.
- 트리가 싫어요! - 조금 쉬운 버전의 문제를 먼저 봅시다.
- HLD가 뭔가요? - HLD의 개념을 알아봅시다.
- 그래서 구현은 어떻게 해요? - 전처리를 알아봅시다.
- 세그트리 구현하기 싫어요! - 세그트리 구현의 부담을 덜어봅시다.
- LCA 싫어요! - LCA를 생략합시다.
- 그래서 구현은? - 구현 소스코드!
우리는 뭘 해야 하죠?
우리는 트리 상에 주어지는 두 가지 쿼리를 처리해야 합니다.
- update u v k : 정점 u, v를 연결하는 간선의 가중치를 k로 변경한다.
- query u v : 정점 u, v 사이의 간선 중 최댓값을 구한다.
트리가 싫어요!
트리에서는 어떻게 할지 감이 잘 잡히지 않으니 만만한 선형으로 문제를 바꿔서 풀어봅시다.
트리가 선형(체인)처럼 생겼다면, 왼쪽부터 차례대로 정점 번호를 다시 매겨준 다음에 Segment Tree와 같은 자료구조로 처리를 해주면 됩니다.
HLD가 뭔가요?
Heavy-Light Decomposition(HLD)는 트리를 몇 개의 체인으로 분할하여 임의의 두 정점 사이의 경로에 최대 logN개의 체인만 존재하도록 하는 자료구조입니다. 각각의 체인을 효율적으로 관리할 수 있는 자료구조가 있다면(Segment Tree, Fenwick Tree, etc) 트리에서 두 정점 사이의 경로에 대한 쿼리를 빠르게 처리할 수 있습니다.
HLD는 간선을 무거운 간선(Heavy Edge)와 가벼운 간선(Light Edge)로 구분합니다. size(son) ≥ size(parent)/2 를 만족하는 간선을 무거운 간선, 그렇지 않으면 가벼운 간선이라고 판단합니다. 한 정점에서 밑으로 내려가는 간선 중에서 무거운 간선은 최대 한 개만 존재해야 한다는 것을 주의해야 합니다.
보통 HLD를 코드로 직접 구현할 때는 구현의 편의를 위해 무거운 간선의 기준을 size(son) ≥ size(parent)/2 대신 size(son)이 가장 큰 간선 을 무거운 간선의 기준으로 잡습니다. 이렇게 정의를 해도 복잡도 등의 분석은 크게 달라지지 않습니다.
위에서 HLD는 트리를 몇 개의 체인(경로)로 분할한다고 했습니다. 간선들을 Heavy Edge와 Light Edge로 구분한 것을 이용해 어떻게 트리를 분할하는지 간단하게 알아봅시다.
이 트리에서 Heavy Edge를 굵은 선으로 표시하면 아래와 같이 됩니다.
각 정점에서 아래로 뻗어나가는 간선 중에서 무거운 간선은 최대 한 개입니다. 그러므로 인접한 무거운 간선끼리는 같은 체인으로 묶어줘도 이상이 없습니다. 그 체인들을 무거운 경로라고 부릅시다.
구현의 편의 상 무거운 경로가 시작되는 간선보다 하나 위에 있는 간선도 무거운 경로에 포함시켜줍시다. 그러면 아래 그림처럼 됩니다.
무거운 경로에 포함되지 않은 간선들은 각각을 하나의 체인으로 처리합시다. 최종적으로 아래 그림과 같이 분할이 완료됩니다.
기본적인 개념은 링크에서 볼 수 있습니다. 해당 링크에 있는 구현이 너무 복잡하기 때문에 이 글을 통해서 더 쉬운 구현을 설명하고자 합니다.
그래서 구현은 어떻게 해요?
무거운 간선을 구하기 위해서는 당연히 각 정점을 루트로 하는 서브트리의 크기를 구해야 합니다. 서브트리의 크기를 구했으면, 체인으로 분할해야 합니다. 그러므로 두 개의 DFS를 구현하면 됩니다.
세그트리 구현하기 싫어요!
Fenwick Tree와 같이 구간을 관리하기 위해 특정한 자료구조가 필요하지 않는 한, 대부분 세그 트리를 이용해 구간을 관리합니다.
안심해도 될 점은, 단 하나의 세그 트리만 만들면 된다는 점입니다. DFS Ordering을 잘 매겨주면 체인에서 연속한 정점은 연속한 번호가 다시 매겨지기 때문에 한 개의 세그 트리만 이용해도 트리 전체를 관리할 수 있습니다.
LCA 싫어요!
LCA를 구하는 함수를 따로 분리해놓으면 보기 싫습니다. 그렇다고 query함수에 넣는 것은 더 보기 싫죠. 그러니까 LCA를 구하는 과정을 최대한 간략화 하면 어떨까요?
최댓값을 구하는 쿼리를 날릴 두 개의 정점 u, v가 있다고 합시다. u와 v가 같은 체인에 속한다면 그냥 세그 트리에 쿼리를 날리면 되겠죠.
그렇지 않다면 체인에서 가장 높이 있는 정점을 고릅시다. 그리고 그 정점으로 넘어갑니다. 마치 LCA를 구할 때 조상으로 점프하는 것 처럼 넘어가면 됩니다. 이 과정을 u와 v가 같은 체인에 속할 때 까지 해주면 됩니다.
이렇게 하면 LCA를 구하는 것과 결과를 찾는 것을 한 번에 처리할 수 있습니다.
그래서 구현은?
코드
제가 짠 코드 아닙니다.