느리게 갱신되는 세그먼트 트리

왜 게으름이 필요한가

일반 세그먼트 트리는 점 갱신과 구간 질의를 각각 \(O(\log N)\)에 처리한다.
그런데 "구간 \([l, r]\)의 모든 원소에 \(v\)를 더하라" 같은 구간 갱신을
정직하게 처리하면 구간 길이만큼의 리프를 건드려야 해서 한 번에 \(O(N)\)이 든다.

핵심 아이디어는 "지금 당장 자손 전부를 갱신하지 말고, 갱신해야 한다는 사실만
노드에 메모해 두자" 이다. 이 메모를 lazy 값이라 부르고, 실제 내려보내는
일을 나중으로 미루는 것을 게으른 전파(lazy propagation) 라 한다.

불변식

각 노드는 두 정보를 든다.

• tree[x]: 이 노드가 담당하는 구간 전체에 lazy가 이미 반영된 집계값.
• lazy[x]: 이 노드의 자식들에게 아직 내려보내지 않은 보류 갱신.

여기서 가장 중요한 불변식은 다음과 같다.

tree[x]는 자기 자신의 lazy까지 모두 반영한 정답이다. 다만 lazy[x]는
자식에게는 아직 적용되지 않았다.

따라서 어떤 노드의 자식으로 내려가기 직전에만 lazy를 한 단계 밀어내면
(push_down), 항상 정확한 값을 보게 된다.

push_down 과정

구간 더하기 + 구간 합 질의를 예로 들면, 노드 \(x\)가 길이 \(len\) 구간을 담당할 때
"구간 전체에 \(v\) 더하기"는 합에 \(v \times len\)을 더하는 것과 같다.

전파가 끝나면 lazy[x] = 0으로 비운다. 더하기는 교환·결합법칙이 성립하므로
보류된 갱신을 누적해 두었다가 한꺼번에 적용해도 결과가 같다. 이 성질이 lazy
전파가 성립하는 근본 이유다.

정당성과 복잡도

구간 갱신과 질의 모두 표준 세그먼트 트리처럼 완전히 덮이는 노드에서 멈춘다.
이런 노드는 깊이마다 최대 4개뿐이므로 방문 노드 수는 \(O(\log N)\)이고,
각 노드에서 하는 일(\(O(1)\) push_down 포함)도 상수 시간이다. 결국 갱신·질의가
모두 \(O(\log N)\)으로 떨어진다.

주의할 점은 곱하기와 더하기가 섞이면 lazy의 결합 순서가 중요해진다는
것이다. "먼저 곱하고 더한다" 같은 우선순위를 정해 두 종류의 lazy를 함께
관리해야 하며, 이때 전파 공식은 \(a \cdot x + b\) 꼴의 affine 변환 합성으로
일반화된다.

구간 더하기 / 구간 합 레퍼런스

1-indexed 배열을 재귀로 만든 표준 구현이다. 합이 커질 수 있으므로 long long을
쓴다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1 << 20;

ll tree[2 * MAXN], lazy[2 * MAXN];
int N;

void apply(int x, int len, ll v) {
    tree[x] += v * len;   // 구간 전체에 v를 더한 효과
    lazy[x] += v;         // 자식에게 보류
}

void push_down(int x, int len) {
    if (lazy[x] == 0) return;
    apply(x * 2,     len / 2, lazy[x]);
    apply(x * 2 + 1, len / 2, lazy[x]);
    lazy[x] = 0;          // 내려보냈으니 비운다
}

// [l, r] 구간에 v 더하기. 현재 노드 x는 [s, e] 담당.
void update(int x, int s, int e, int l, int r, ll v) {
    if (r < s || e < l) return;          // 겹치지 않음
    if (l <= s && e <= r) {              // 완전히 덮임
        apply(x, e - s + 1, v);
        return;
    }
    push_down(x, e - s + 1);            // 내려가기 전에 전파
    int m = (s + e) / 2;
    update(x * 2,     s,     m, l, r, v);
    update(x * 2 + 1, m + 1, e, l, r, v);
    tree[x] = tree[x * 2] + tree[x * 2 + 1];
}

ll query(int x, int s, int e, int l, int r) {
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) return tree[x];
    push_down(x, e - s + 1);
    int m = (s + e) / 2;
    return query(x * 2, s, m, l, r) + query(x * 2 + 1, m + 1, e, l, r);
}

흔한 실수

• push_down 누락 — 자식으로 재귀하기 직전에 반드시 전파해야 한다. 빠뜨리면
  오래된 값을 보고 오답을 낸다.
• 길이 인자 혼동 — 합 모드에서는 v * len을 더해야 한다. 최댓값 모드라면
  길이와 무관하게 tree[x] += v이고 전파 공식도 달라진다.
• 곱셈 lazy의 초기값 — 곱하기 lazy는 0이 아니라 1로 초기화해야 한다.
  "갱신 없음"을 나타내는 항등원이 연산마다 다르다는 점을 기억하자.
• 오버플로 — 더한 값과 길이가 모두 크면 \(10^{18}\)를 쉽게 넘는다.

자주 나오는 응용

대표 응용으로는 구간에 등차수열 더하기(차분 + 두 번 적용), 2차원으로
확장한 누적 갱신, 그리고 오프라인 좌표 압축 후 직사각형 넓이 합집합을
스캔라인으로 구하는 문제가 있다. lazy 세그 트리는 이후 등장할 머지 소트 트리,
퍼시스턴트 세그 트리, HLD의 토대가 되므로 전파 공식을 손으로 유도하는 연습을
충분히 해 두자.