Lazy Propagation (지연 전파)

Lazy Propagation (지연 전파)

세그먼트 트리에서 구간 갱신(Range Update)을 O(log n)에 처리하기 위해 갱신 정보를 즉시 전파하지 않고 자식 노드 방문 시 지연 전파하는 최적화 기법

목적: 구간 갱신 최적화, O(n) → O(log n), 불필요한 갱신 방지

특징: 지연 배열(lazy[]), 필요 시 전파(push-down), 구간 갱신+구간 쿼리 동시 지원

동작 원리: ① 구간 갱신 시 해당 노드에 lazy 값 저장 ② 쿼리/갱신으로 자식 방문 시 lazy 값을 자식에 전파(push-down) ③ 현재 노드의 lazy 초기화

시간 복잡도: 구간 갱신 O(log n), 구간 쿼리 O(log n)

장점: 구간 갱신 효율화, 단일 갱신 대비 대폭 성능 향상

단점: 구현 복잡도 증가, push-down 로직 실수 가능

적용사례: 구간 덧셈, 구간 최솟값 갱신, 페인팅 문제, 알고리즘 경시대회

비교: Lazy Propagation(구간갱신 O(log n)) vs 단순 세그먼트(단일갱신 O(log n)/구간갱신 O(n log n))

연관: 세그먼트 트리, 구간 쿼리, Fenwick 트리