Lazy Propagation 완벽 이해: 세그먼트 트리에서 구간 업데이트를 효율적으로 처리하는 방법

세그먼트 트리에서 구간 단위로 값을 업데이트해야 할 경우, 단순하게 처리하면 **시간복잡도가 O(N)**이 되어버려 효율이 급격히 떨어집니다.
이를 해결하는 고급 기법이 바로 **Lazy Propagation(지연 전파)**입니다.

이번 글에서는 Lazy Propagation의 개념, 필요성, 작동 방식, Python 코드 구현, 실전 문제 적용까지 단계별로 정리합니다.

✅ Lazy Propagation이란?

세그먼트 트리에서 여러 구간을 한 번에 갱신할 때, 갱신 정보를 지연시켜 저장해 두었다가
**필요할 때만 적용(전파)**하는 최적화 기법입니다.

📉 왜 필요한가?

기존 세그먼트 트리로 아래와 같은 연산을 수행한다고 할 때:

arr[2:7] += 3
arr[0:5] += 1
query(3, 4)
query(0, 7)

이런 구간 업데이트가 많아지면, 모든 리프 노드를 갱신하는 방식은 비효율적입니다.
→ 이때 Lazy Propagation으로 성능을 극적으로 개선할 수 있습니다.

🔍 Lazy Propagation 동작 방식 요약

업데이트 요청이 왔을 때, 현재 노드의 값은 변경하지 않음
lazy 배열에 변경할 값만 저장해둠
이후 그 노드를 접근할 때(조회 또는 재귀 호출 시),
lazy 값을 해당 노드와 자식 노드로 전파(push down)

🛠 Python 코드 예제 (구간 합 + 구간 덧셈 업데이트)

class LazySegmentTree:
    def __init__(self, arr):
        self.N = len(arr)
        self.tree = [0] * (4 * self.N)
        self.lazy = [0] * (4 * self.N)
        self.build(arr, 0, 0, self.N - 1)

    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(arr, node*2+1, start, mid)
            self.build(arr, node*2+2, mid+1, end)
            self.tree[node] = self.tree[node*2+1] + self.tree[node*2+2]

    def push(self, node, start, end):
        if self.lazy[node] != 0:
            # 현재 노드에 lazy 반영
            self.tree[node] += (end - start + 1) * self.lazy[node]
            if start != end:
                self.lazy[node*2+1] += self.lazy[node]
                self.lazy[node*2+2] += self.lazy[node]
            self.lazy[node] = 0

    def update_range(self, l, r, val, node=0, 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] += val
            self.push(node, start, end)
            return
        mid = (start + end) // 2
        self.update_range(l, r, val, node*2+1, start, mid)
        self.update_range(l, r, val, node*2+2, mid+1, end)
        self.tree[node] = self.tree[node*2+1] + self.tree[node*2+2]

    def query_range(self, l, r, node=0, 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_range(l, r, node*2+1, start, mid)
        right = self.query_range(l, r, node*2+2, mid+1, end)
        return left + right

✅ 사용 예제

arr = [1, 2, 3, 4, 5, 6, 7, 8]
st = LazySegmentTree(arr)

print(st.query_range(2, 5))  # 출력: 3+4+5+6 = 18

st.update_range(2, 5, 10)  # arr[2:5] += 10 → [13,14,15,6]
print(st.query_range(2, 5))  # 출력: 13+14+15+6 = 48

print(st.query_range(0, 7))  # 전체 합 = 1+2+13+14+15+6+7+8 = 66

📘 백준 Lazy Propagation 실전 문제

번호 제목 설명

10999	구간 합 구하기 2	구간 덧셈 + 구간 합
12837	가계부	구간 업데이트 & 단일 쿼리
16975	수열과 쿼리 21	구간 갱신 & 구간 쿼리

🔄 일반 구간 업데이트 방식과 비교

항목 일반 세그먼트 트리 Lazy Propagation

구간 업데이트	O(N)	✅ O(log N)
쿼리 속도	O(log N)	✅ O(log N)
구현 난이도	쉬움	약간 복잡함
실전 활용도	제한적	✅ 고난도 문제 해결 가능

📌 결론 및 요약

Lazy Propagation은 세그먼트 트리의 구간 업데이트 성능을 극대화하는 핵심 기술입니다.
여러 번의 업데이트와 쿼리가 반복되는 문제에서는 성능 차이가 수십 배 이상 벌어질 수 있습니다.
실전에서는 반드시 이 구조를 연습하고 구현해보는 것이 중요합니다.

👉 다음 글에서는 **펜윅 트리(Fenwick Tree / Binary Indexed Tree)**를 통해
세그먼트 트리와의 차이, 사용 장단점, 구간 합 처리 방식을 비교해보겠습니다.

📚 참고자료 및 출처

『코딩 테스트 고득점 Kit』
백준 10999, 12837, 16975
CP-Algorithms – Lazy Propagation

세그먼트트리, lazy propagation, 지연전파, 구간업데이트, range update, 파이썬 자료구조, 알고리즘 최적화, 코딩테스트 고난도, 트리구조, SEO 최적화 10개