Heavy Light Decomposition (HLD)

shijun 2025. 10. 4. 21:53

HLD (Heavy Light Decomposition)는 트리에서 구간 쿼리를 O(log^2 N) (N : 노드 수)에 수행하는 자료구조이다. 기본적으로 ETT (Euler Tour Technique)를 기반으로 하는데, 먼저 이에 대해 설명하겠다.

1. Euler Tour Technique

쉽게 말하자면, 노드에 방문 순서대로 번호를 매기는 것이다. 다음과 같은 트리를 생각해 보자.

ETT에서는 각 정점에 두 개의 변수를 저장한다. 바로 in과 out인데, in은 정점을 방문한 순서, out은 정점의 하위 노드 중 가장 큰 방문 순서 즉, 가장 늦게 방문된 노드의 in 값을 저장한다.

void dfs(int node) {
    in[node] = ++cur;
    for (int i:Edges[node]) {
        dfs(i);
    }
    out[node] = cur;
}

이렇게 번호를 매기고 나면, 우리는 노드들을 가지고 세그먼트 트리를 만들 수 있다. 각 노드를 in 값이 작은 순으로 배열하고, 그 배열에 대해서 구간 연산을 진행할 수 있다. 이런 식으로 노드를 배열하면 무엇이 좋을까? 바로, 각 정점을 루트로 하는 서브 트리가 하나의 연속된 구간에 나타나게 된다는 것이다.

예를 들어서 서브 트리 속 모든 노드의 가중치 합을 구한다고 하자. 먼저 각 노드의 in 값에 대응되는 구간합 세그먼트 트리의 인덱스에 원래의 가중치를 더해준다. 특정한 노드의 가중치를 업데이트하고 싶다면, in 값에 대응되는 세그먼트 트리의 인덱스에 새로운 가중치를 대입하면 된다. 특정한 노드 (Root)의 서브 트리 속 모든 노드의 가중치 합을 구하기 위해서 우리는 세그먼트 트리의 [in[Root], out[Root]] 구간합을 구할 수 있다. 아까 말했듯이, Root의 서브 트리의 원소들은 모두 세그먼트 트리에서 하나의 연속된 구간에 나타나므로, 업데이트와 쿼리를 모두 O(logN)에 해결할 수 있다.

2. Heavy Light Decomposition

서브 트리에서의 구간 연산을 할 수 있다면, 임의의 두 노드 간의 경로에 대해서는 어떻게 해야 할까? 이를 위한 방법이 바로 HLD이다. 먼저, 간선을 무거운 (heavy) 간선과 가벼운 (light) 간선으로 구분한다. 부모 노드 u의 자식들 중 가장 서브트리의 크기가 큰 v와의 간선을 heavy 한 간선이라고 하고, 나머지 자식과의 간선을 light한 간선으로 정의한다.

이 트리에서 heavy한 간선을 표시하면 다음과 같다.

이렇게 간선을 구분하면 무엇이 좋을까? 바로 시간복잡도가 유의미하게 개선된다는 것인데, light 간선을 타고 올라가면 서브 트리의 크기가 최소 2배 증가한다! 이는 생각해 보면 당연한데, 만약 u의 자식 노드가 v이고, u와 v가 light 간선으로 연결되어 있다면, u의 다른 자식 v'이 존재해서 그 서브트리의 크기가 v보다 크거나 같으므로 u의 서브트리의 크기는 무조건 v의 2배 이상이다. 이렇게 생각해 보면, 어떤 정점에서 루트로 올라갈 때, 최대 O(logN) 개의 light 한 간선을 지나게 된다. 그러면 heavy한 간선은 몇 번 지나게 될까? 사실 이는 중요하지 않다. 우리는 연속된 heavy한 간선을 체인과 같이 이을 것이다. 즉, 위의 트리에서 보면, 8번 노드에서 바로 1번 노드로 넘어갈 것이라는 거다. 이를 구현하는 것은 조금 뒤에 알아보고, 이런 방법을 사용하게 되면 결국 이어진 heavy한 간선들은 light한 간선의 개수와 같은 최대 O(logN) 개를 지남을 알 수 있고, 결국 모든 임의의 정점에서 루트 노드까지 이동하는 데 O(logN)번이면 충분하다!

먼저 heavy한 간선과 light한 간선을 구분해 보자.

void dfs(int node) {
    sz[node] = 1;
    for (int i:Adj[node]) {
        if (par[node] == i) continue;
        par[i] = node;
        dep[i] = dep[node]+1;
        dfs(i);
        sz[node] += sz[i];
        Chd[node].push_back(i);
        if (sz[Chd[node][0]]<sz[i]) swap(Chd[node][0], Chd[node].back());
    }
}

void hld(int node) {
    in[node] = ++cur;
    for (int i:Chd[node]) {
        if (i == Chd[node][0]) top[i] = top[node];
        else top[i] = i;
        hld(i);
    }
    out[node] = cur;
}

간단히 설명하면, 먼저 dfs(Root)를 호출한다. 각 노드에는 자식 노드를 저장하는 Chd를 만드는데, 여기서 서브 트리 크기 비교를 통해 Chd[node][0] 번에는 node의 자식 중 제일 서브 트리 크기가 큰 자식의 번호를 넣는다.

그다음에 hld(Root)를 호출하는데, 여기서 ETT를 사용한다. 먼저 설명한 ETT와의 다른 점은, top이라는 변수를 만드는 것이다. top[node]는 node에서 출발하여 heavy 한 간선만을 이용해 올라갈 수 있는 최소 depth의 노드를 저장한다. Chd[node][0]에 제일 서브 트리의 크기가 큰 자식을 저장했으므로 top을 top[node]와 같게 설정하고 (heavy), 이외의 자식은 모두 자신 그대로로 설정한다 (light). 이 방식을 사용해 아까 말한 것 처럼, 연속한 heavy한 간선을 이어서 한 번에 이동할 수 있다. 후에 더 설명하겠지만, 이 방식이 통하는 이유는 각 노드에서 heavy한 간선을 제일 먼저 방문하기 때문에, 연속된 heavy한 간선끼리는 in 값이 모두 연속적으로 들어가게 된다. 즉, 세그먼트 트리에서 인접하므로 구간 쿼리를 사용할 수 있는 것이다.

본격적으로 업데이트와 쿼리를 알아보자.

void hldUpd(int u, int v, ll val) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        upd(1, N, 1, in[top[u]], in[u], val);
        u = par[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    upd(1, N, 1, in[v], in[u], val);
}

두 노드의 top이 같아질 때까지 즉, 같은 체인에 속할 때까지 u와 v를 올려준다. u와 v 중에서 top의 depth가 더 큰 노드를 고르고, 그 노드의 heavy 한 간선들의 체인에 대해서 구간 업데이트를 해준다. 여기서 upd는 상황에 따라 다른 세그먼트 트리를 사용하면 된다. 그리고 고른 노드를 top[노드]의 부모로 설정한다. 이를 반복하다 두 노드의 top이 같아진다면, u와 v를 잇는 체인에 대해 구간 업데이트를 한 번 해주면 된다.

int hldQuery(int u, int v) {
    int ret = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        ret += query(1, N, 1, in[top[u]], in[u]));
        u = par[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    ret += query(1, N, 1, in[v], in[u]));
    return ret;
}

쿼리도 같은 방식으로 진행하면 된다. 단지 업데이트 대신에 각각의 구간에서 나온 결과를 합해주면 된다. 업데이트, 쿼리의 시간복잡도는 모두 O(log^2 N)이다.

3. 연습문제

14268 회사 문화 2 -> ETT 기초 예제

13510 트리와 쿼리 1 -> HLD 기초 예제

17429 국제 메시 기구 -> 이 블로그에서 소개한 모든 내용을 다 쓴다.