← 루비 V

세그먼트 트리 비츠

구간 chmin/chmax 갱신을 amortized 복잡도로.

자료 구조

루비 V

선수 지식: 느리게 갱신되는 세그먼트 트리

1강 Segment Tree Beats의 아이디어 공식

풀 수 없어 보이는 구간 갱신

다음 연산을 모두 $O(\log)$ 근처로 처리하고 싶다.

구간 $$[l, r]$$ 의 모든 원소에 $a_i \leftarrow \min(a_i, x)$ (chmin)
구간 합 / 구간 최댓값 질의

chmin은 일부 원소만 바꾸므로 평범한 lazy로는 안 된다. Segment Tree Beats(지대룡 트릭) 의 핵심은 조건부 lazy다.

노드가 저장하는 정보

각 노드에 다음을 유지한다.

변수	의미
`mx1`	구간 최댓값
`mx2`	구간 두 번째 최댓값(strict, < mx1)
`cnt`	최댓값을 가진 원소 개수
`sum`	구간 합

chmin의 세 갈래

구간에 $\min(\cdot, x)$ 를 적용할 때 노드에서:

$x \ge mx1$ : 아무것도 안 바뀜 → 즉시 종료(break).
$$mx2 < x < mx1$$ : 최댓값 원소들만 $$x$$ 로 줄어듦.
- sum -= (mx1 - x) * cnt, mx1 = x. → lazy로 처리(tag).
$x \le mx2$ : 경계가 애매함 → 자식으로 재귀(recurse).

세 번째 경우만 깊이 들어간다. 이 "비싼" 경우가 드물게 일어난다는 것이 복잡도의 핵심이다.

복잡도: amortized $O(n \log^2 n)$

증명은 potential 함수 $\Phi$ = (모든 노드에서 서로 다른 최댓값 태그의 수)로 한다. case 3 재귀가 일어날 때마다 서로 다른 값의 "종류"가 합쳐져 $\Phi$ 가 감소한다. 각 chmin 연산이 $\Phi$ 를 $O(\log n)$ 만큼 증가시키고, 비싼 재귀가 $\Phi$ 를 그만큼 소모하므로 총 작업량이 $O((n+q)\log^2 n)$ 로 묶인다.

엄밀히: $\Phi = \sum_v (\text{노드 } v \text{ 서브트리에 나타나는 서로 다른 값의 개수})$ . 초기 $\Phi = O(n \log n)$ . 각 case-3 하강은 $\Phi$ 를 최소 1 감소시킨다.

확장: 양방향 + 구간 덧셈

chmax를 추가하려면 최솟값 쌍(mn1, mn2, cntmin)도 같이 유지한다. 구간 덧셈(add)까지 넣으면 lazy가 (add 태그, chmin 태그, chmax 태그) 세 종류로 늘고, 태그 합성 순서를 조심해야 한다. 일반적으로 add → chmin/chmax 순으로 정규화한다.

정리

chmin/chmax는 "최댓값/최솟값만 건드리는 lazy"로 본다.
break / tag / recurse의 3분기가 핵심.
분석은 potential argument로 amortized $O(\log^2)$ .

다음 강의에서 add + chmin + 구간합을 모두 지원하는 구현을 본다.

2강 Beats 구현: add + chmin + 합 공식

노드 구조

struct Node {
    long long sum;
    long long mx1, mx2;   // 최댓값, 둘째 최댓값(strict)
    int cnt;              // 최댓값 개수
    long long add;        // 보류 중인 구간 덧셈
};
Node t[4 * MAXN];

합성 / 갱신 헬퍼

void applyAdd(int x, int len, long long v) {
    t[x].sum += v * len;
    t[x].mx1 += v;
    if (t[x].mx2 != LLONG_MIN) t[x].mx2 += v;
    t[x].add += v;
}

void applyChmin(int x, long long v) {
    // 전제: t[x].mx2 < v < t[x].mx1
    t[x].sum -= (t[x].mx1 - v) * t[x].cnt;
    t[x].mx1 = v;
}

void pull(int x) {
    int l = x << 1, r = l | 1;
    t[x].sum = t[l].sum + t[r].sum;
    if (t[l].mx1 == t[r].mx1) {
        t[x].mx1 = t[l].mx1;
        t[x].cnt = t[l].cnt + t[r].cnt;
        t[x].mx2 = max(t[l].mx2, t[r].mx2);
    } else {
        int big = (t[l].mx1 > t[r].mx1) ? l : r;
        int sml = big ^ 1;
        t[x].mx1 = t[big].mx1;
        t[x].cnt = t[big].cnt;
        t[x].mx2 = max(t[sml].mx1, t[big].mx2);
    }
}

push down

void push(int x, int lc, int rc, int llen, int rlen) {
    if (t[x].add) {
        applyAdd(lc, llen, t[x].add);
        applyAdd(rc, rlen, t[x].add);
        t[x].add = 0;
    }
    if (t[lc].mx1 > t[x].mx1) applyChmin(lc, t[x].mx1);
    if (t[rc].mx1 > t[x].mx1) applyChmin(rc, t[x].mx1);
}

add를 먼저 내린 뒤 chmin 태그를 전파하는 순서가 중요하다.

구간 덧셈

void rangeAdd(int x, int lo, int hi, int l, int r, long long v) {
    if (r < lo || hi < l) return;
    if (l <= lo && hi <= r) { applyAdd(x, hi - lo + 1, v); return; }
    int mid = (lo + hi) >> 1, lc = x << 1, rc = lc | 1;
    push(x, lc, rc, mid - lo + 1, hi - mid);
    rangeAdd(lc, lo, mid, l, r, v);
    rangeAdd(rc, mid + 1, hi, l, r, v);
    pull(x);
}

chmin (3분기)

void rangeChmin(int x, int lo, int hi, int l, int r, long long v) {
    if (r < lo || hi < l || v >= t[x].mx1) return;   // case 1: break
    if (l <= lo && hi <= r && v > t[x].mx2) {         // case 2: tag
        applyChmin(x, v); return;
    }
    int mid = (lo + hi) >> 1, lc = x << 1, rc = lc | 1;  // case 3: recurse
    push(x, lc, rc, mid - lo + 1, hi - mid);
    rangeChmin(lc, lo, mid, l, r, v);
    rangeChmin(rc, mid + 1, hi, l, r, v);
    pull(x);
}

구간 합 질의

long long querySum(int x, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return 0;
    if (l <= lo && hi <= r) return t[x].sum;
    int mid = (lo + hi) >> 1, lc = x << 1, rc = lc | 1;
    push(x, lc, rc, mid - lo + 1, hi - mid);
    return querySum(lc, lo, mid, l, r) + querySum(rc, mid + 1, hi, l, r);
}

함정

mx2 초깃값은 LLONG_MIN. 리프는 mx2 = LLONG_MIN, cnt = 1.
case 2의 조건 v > mx2가 빠지면 정답이 깨진다. 반드시 strict 둘째 최댓값을 써야 한다.
add 오버플로 주의: long long 사용.

연습: 백준 "수열과 쿼리" 계열(chmin/chmax/add/sum 조합)으로 위 코드를 검증하라. amortized $O((n+q)\log^2 n)$ 으로 $n, q \le 10^6$ 급도 통과한다.