Heavy-Light Decomposition (HLD): 동적 트리 문제 해결의 핵심 알고리즘

Heavy-Light Decomposition (HLD): 동적 트리 문제 해결의 핵심 알고리즘

**Heavy-Light Decomposition (HLD)**는 트리 구조에서 동적 구간 쿼리를 효율적으로 처리하기 위한 기법입니다.
주로 동적 경로 문제, LCA + 구간 쿼리 문제에서 필수적으로 사용됩니다.

이번 글에서는 HLD의 개념, 구성 방법, 세그먼트 트리와의 결합을 통해
동적 트리 문제를 효율적으로 해결하는 방법을 단계별로 정리합니다.

---

✅ Heavy-Light Decomposition(HLD)란?

트리의 경로 쿼리를 **O(log² N)**으로 효율적으로 처리하는 고급 기법입니다.
트리를 Heavy 경로와 Light 경로로 나누어
트리 경로 문제를 여러 개의 구간 문제로 분리하여 해결합니다.

---

🔑 HLD의 핵심 아이디어

1. Heavy 경로 (Heavy Path):
   • 부모에서 자식으로 내려갈 때 서브트리 크기가 가장 큰 방향
   • 한 경로가 최대한 길어지도록 설정
2. Light 경로 (Light Path):
   • 서브트리 크기가 작은 방향
   • 한 번 이동하면 다른 경로로 넘어가야 함

---

📝 HLD의 특징

특징 설명

경로 분할	Heavy 경로는 길게, Light 경로는 짧게
구간 문제로 변환	각 경로를 세그먼트 트리로 관리
트리 경로를 여러 구간으로 분리	O(log² N) 복잡도로 문제 해결 가능

---

🛠 Python 구현 (Heavy-Light Decomposition + Segment Tree)

1. HLD 클래스 정의

class SegmentTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (4 * size)

    def update(self, idx, value, node=1, start=0, end=None):
        if end is None:
            end = self.n - 1
        if start == end:
            self.tree[node] = value
        else:
            mid = (start + end) // 2
            if start <= idx <= mid:
                self.update(idx, value, node * 2, start, mid)
            else:
                self.update(idx, value, node * 2 + 1, mid + 1, end)
            self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def query(self, l, r, node=1, start=0, end=None):
        if end is None:
            end = self.n - 1
        if r < start or end < l:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        left = self.query(l, r, node * 2, start, mid)
        right = self.query(l, r, node * 2 + 1, mid + 1, end)
        return left + right

---

2. HLD 클래스 정의

반응형

class HLD:
    def __init__(self, n):
        self.n = n
        self.tree = [[] for _ in range(n)]
        self.parent = [-1] * n
        self.depth = [0] * n
        self.subtree_size = [1] * n
        self.chain_head = [-1] * n
        self.pos_in_base = [-1] * n
        self.base_array = []
        self.seg_tree = None

    def add_edge(self, u, v):
        self.tree[u].append(v)
        self.tree[v].append(u)

    def dfs(self, u):
        for v in self.tree[u]:
            if v != self.parent[u]:
                self.parent[v] = u
                self.depth[v] = self.depth[u] + 1
                self.dfs(v)
                self.subtree_size[u] += self.subtree_size[v]

    def hld(self, u, head):
        self.chain_head[u] = head
        self.pos_in_base[u] = len(self.base_array)
        self.base_array.append(0)

        heavy = -1
        for v in self.tree[u]:
            if v != self.parent[u] and (heavy == -1 or self.subtree_size[v] > self.subtree_size[heavy]):
                heavy = v

        if heavy != -1:
            self.hld(heavy, head)

        for v in self.tree[u]:
            if v != self.parent[u] and v != heavy:
                self.hld(v, v)

    def query_up(self, u, v):
        res = 0
        while self.chain_head[u] != self.chain_head[v]:
            if self.depth[self.chain_head[u]] < self.depth[self.chain_head[v]]:
                u, v = v, u
            head = self.chain_head[u]
            res += self.seg_tree.query(self.pos_in_base[head], self.pos_in_base[u])
            u = self.parent[head]
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        res += self.seg_tree.query(self.pos_in_base[u], self.pos_in_base[v])
        return res

    def build_segment_tree(self):
        self.seg_tree = SegmentTree(len(self.base_array))

    def update(self, u, value):
        self.seg_tree.update(self.pos_in_base[u], value)

---

✅ 사용 예시

n = 7
hld = HLD(n)

edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]
for u, v in edges:
    hld.add_edge(u, v)

hld.dfs(0)
hld.hld(0, 0)
hld.build_segment_tree()

# 노드 값 갱신
hld.update(3, 10)
hld.update(4, 20)
hld.update(5, 15)

# 두 노드 간 경로 쿼리
print(hld.query_up(3, 5))  # 출력: 25 (10 + 15)
print(hld.query_up(4, 6))  # 출력: 20 (4번 노드 값)

---

📘 실전 활용 문제

문제 번호 제목 유형

13510	트리와 쿼리 1	HLD + 세그먼트 트리
17435	합성함수와 쿼리	HLD 기반 경로 쿼리
13306	두 배열의 최소 공통 조상 찾기	HLD + LCA

---

📌 결론 및 요약

• HLD는 트리 경로 문제를 여러 구간 문제로 분리하여 처리합니다.
• Heavy 경로는 길게, Light 경로는 짧게 설정하여
  O(log² N) 시간에 경로 쿼리를 처리할 수 있습니다.
• 세그먼트 트리와 결합하여 동적 경로 쿼리 문제에서 필수적으로 사용됩니다.

👉 다음 글에서는 HLD와 Lazy Propagation을 결합하여
구간 업데이트 + 경로 쿼리를 동시에 처리하는 고급 알고리즘을 다루겠습니다.

---

📚 참고자료 및 출처

• 『알고리즘 문제 해결 전략』 (구종만)
• 백준 13510, 17435
• CP-Algorithms – HLD

---

 

HLD, Heavy-Light Decomposition, 동적 트리, 세그먼트 트리, 구간 경로 문제, 트리 최적화, 파이썬 알고리즘, 동적 경로 쿼리, 코딩테스트 대비, SEO 최적화 10개