동적 트리 문제 해결을 위한 HLD + Lazy Propagation: 구간 업데이트와 경로 쿼리를 동시에 처리하기

동적 트리 문제 해결을 위한 HLD + Lazy Propagation: 구간 업데이트와 경로 쿼리를 동시에 처리하기

**Heavy-Light Decomposition (HLD)**는 트리 구조에서 경로 쿼리를 효율적으로 처리하는 기법입니다.
하지만 구간 업데이트까지 필요할 때는 기본 HLD만으로는 한계가 있습니다.

이번 글에서는 HLD와 Lazy Propagation을 결합하여
동적 트리 문제에서 구간 업데이트와 경로 쿼리를 동시에 처리하는 방법을 단계별로 정리합니다.

---

✅ 문제 상황: 경로 쿼리와 구간 업데이트

HLD를 사용하면 트리 경로 문제를 **O(log² N)**에 처리할 수 있습니다.
하지만 구간 업데이트까지 포함되는 문제는 다음과 같은 상황을 처리해야 합니다:

• 노드 값 갱신: 특정 노드의 값을 증가시키기
• 경로 구간 합: 두 노드 사이 경로의 합 구하기
• 구간 업데이트: 경로상 모든 노드 값을 한꺼번에 증가

이때 필요한 최적화 기법이 바로 Lazy Propagation입니다.

---

🔧 핵심 아이디어: HLD + Lazy Propagation

요소 역할

HLD	트리를 Heavy 경로와 Light 경로로 분리
세그먼트 트리	구간 쿼리와 업데이트를 처리
Lazy Propagation	구간 업데이트를 효율적으로 처리

---

🛠 Python 구현: HLD + Lazy Propagation

1. 세그먼트 트리 + Lazy Propagation 클래스

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

    def push(self, node, start, end):
        if self.lazy[node] != 0:
            self.tree[node] += (end - start + 1) * self.lazy[node]
            if start != end:
                self.lazy[node * 2] += self.lazy[node]
                self.lazy[node * 2 + 1] += self.lazy[node]
            self.lazy[node] = 0

    def update(self, l, r, value, node=1, start=0, end=None):
        if end is None:
            end = self.n - 1
        self.push(node, start, end)
        if r < start or end < l:
            return
        if l <= start and end <= r:
            self.lazy[node] += value
            self.push(node, start, end)
            return
        mid = (start + end) // 2
        self.update(l, r, value, node * 2, start, mid)
        self.update(l, r, 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
        self.push(node, start, end)
        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 build_segment_tree(self):
        self.seg_tree = SegmentTree(len(self.base_array))

    def update_path(self, u, v, value):
        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]
            self.seg_tree.update(self.pos_in_base[head], self.pos_in_base[u], value)
            u = self.parent[head]
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        self.seg_tree.update(self.pos_in_base[u], self.pos_in_base[v], value)

    def query_path(self, u, v):
        result = 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]
            result += 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
        result += self.seg_tree.query(self.pos_in_base[u], self.pos_in_base[v])
        return result

---

✅ 사용 예시

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_path(3, 6, 5)  # 경로에 +5

# 경로 쿼리
print(hld.query_path(3, 6))  # 출력: 15 (5 + 5 + 5)

---

📌 결론 및 요약

• HLD + Lazy Propagation으로 구간 업데이트와 경로 쿼리를 효율적으로 처리할 수 있습니다.
• 구간 업데이트 시 Lazy Propagation을 활용하여 O(log² N) 복잡도를 유지합니다.
• 실전 문제에서 구간 갱신과 경로 쿼리가 모두 필요한 경우에 필수적인 기법입니다.

👉 다음 글에서는 Link/Cut Tree를 통해 동적 트리 구조 변경을
효율적으로 처리하는 고급 알고리즘을 다루겠습니다.

---

📚 참고자료 및 출처

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

---

 

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