수십만 개의 데이터가 들어있는 배열에서 특정 구간의 합을 구하거나 값을 변경할 때, 매번 O(N)의 시간이 걸리는 것을 O(log N)으로 단축해 주는 구원자가 바로 세그먼트 트리(Segment Tree)입니다. 하지만 일반적인 세그먼트 트리에는 치명적인 약점이 하나 있습니다. 만약 "인덱스 0번부터 10만 번까지의 모든 숫자에 5를 더하시오"라는 구간 업데이트(Range Update) 명령이 내려진다면 어떻게 될까요? 트리의 맨 아래 리프 노드 10만 개를 일일이 찾아가서 값을 바꾸고 트리를 다시 거슬러 올라와야 하므로, 결국 최악의 경우 O(N log N)이라는 재앙적인 시간이 소요됩니다. 이 한계를 완벽하게 박살 내고, 거대한 구간의 업데이트조차 단 O(log N) 만에 처리해 내는 천재적인 기법이 바로 '느리게 갱신되는 세그먼트 트리(Lazy Propagation)'입니다. "당장 필요하지 않은 일은 나중으로 미룬다"는 게으름의 미학이 어떻게 알고리즘의 마법이 되는지 해부해 보겠습니다.
1. 구간 업데이트의 재앙과 게으름의 도입
기존 세그먼트 트리에서 구간 업데이트가 느린 이유는, 갱신해야 할 구간에 속한 모든 자식 노드들을 그 즉시 남김없이 파고들기 때문입니다. Lazy Propagation의 핵심 철학은 "어차피 지금 당장 그 밑에 있는 자식 노드들의 정확한 값이 필요하지 않다면, 굳이 지금 바닥까지 내려가서 고생할 필요가 없다"는 것입니다.
2. Lazy 배열: 미뤄둔 숙제 기록장
이 마법을 구현하기 위해 우리는 기존 트리 배열(tree[]) 외에, 똑같은 크기의 lazy[] 배열을 하나 더 만듭니다. 이 배열은 "내 자식 노드들에게 나중에 더해줘야 할(혹은 갱신해야 할) 미뤄둔 값"을 적어두는 메모장 역할을 합니다.
2-1. "나중에 할게" (Delay Update)
어떤 노드가 담당하는 구간이 우리가 업데이트하려는 구간에 완벽하게 포함된다고 가정해 봅시다. 이때 자식 노드로 더 이상 내려가지 않고, 현재 노드의 tree 값만 갱신한 뒤, "내 자식들에게는 나중에 5를 더해주면 돼"라고 lazy 배열에 5를 꾹 적어두고 탐색을 그 즉시 종료(Return)해 버립니다. 10만 개의 자식을 일일이 방문해야 했던 작업이, 부모 노드 하나에 메모를 남기는 O(1)의 작업으로 압축되는 순간입니다.
3. 게으른 업데이트 시뮬레이션 (Push-Down)
물론 영원히 미뤄둘 수는 없습니다. 언젠가 누군가가 특정 구간의 합을 조회(Query)하거나, 그보다 더 깊은 곳을 업데이트하기 위해 트리를 타고 내려와야 할 때가 생깁니다. 이때 노드를 방문하면서 다음 작업을 수행합니다.
3-1. 숙제 청산 (Propagation)
어떤 노드에 방문했을 때, 그 노드의 lazy 배열에 적혀 있는 값이 0이 아니라면(즉, 미뤄둔 숙제가 있다면) 다음 로직이 발동됩니다.
- 현재 노드의
tree값에lazy값을 반영하여 진짜 올바른 값으로 고칩니다. (예:tree[node] += lazy[node] * (구간의 길이)) - 현재 노드가 리프 노드가 아니라면, 나의
lazy값을 두 자식 노드의lazy배열로 물려줍니다(Push-Down). "아빠가 바빠서 못 한 숙제, 너희들이 나중에 해라"라고 떠넘기는 것입니다. - 현재 노드의
lazy값을 0으로 지워 숙제를 청산합니다.
이 전파(Propagation) 과정은 우리가 트리를 타고 내려가는 경로에 있는 노드들에 대해서만 꼭 필요할 때 쪼잔하게(Lazy) 이루어집니다. 따라서 아무리 넓은 구간을 업데이트하더라도 트리의 깊이만큼만 연산이 발생하여, 쿼리당 확정적으로 $O(\log N)$의 경이로운 시간 복잡도를 보장하게 됩니다.
1. Lazy Propagation은 세그먼트 트리에서 거대한 구간의 값을 한꺼번에 변경할 때, 자식 노드까지 내려가지 않고 업데이트를 지연시킴으로써 $O(\log N)$의 속도를 유지하는 기법입니다.
2. 변경할 값을 기록해 두는
lazy 배열을 추가로 운영하며, 구간이 완벽히 포함될 때 lazy 값만 갱신하고 탐색을 즉시 종료합니다.3. 이후 다른 연산으로 인해 해당 노드를 다시 방문하게 될 때만, 미뤄둔
lazy 값을 실제 tree에 반영하고 자식에게 숙제를 떠넘기는(Push-Down) 방식을 취합니다.