스플레이 트리

회전으로 균형을 맞추는 BBST — 구간 뒤집기까지.

다이아몬드 IV

선수 지식: 세그먼트 트리

1강 자가 조정 BBST: 스플레이 트리 공식

동기

균형 이진 탐색 트리는 보통 회전 규칙(AVL, Red-Black)으로 높이를 $O(\log n)$ 으로 유지한다. 스플레이 트리는 명시적 균형 정보를 두지 않고, 접근한 노드를 매번 루트로 끌어올리는 스플레이 연산 하나로 amortized $O(\log n)$ 을 달성한다. 단순하면서도 구간 뒤집기·구간 합 같은 시퀀스 연산까지 자연스럽게 확장된다.

스플레이 연산

노드 $$x$$ 를 루트로 올리는 회전 묶음. 부모 $$p$$ , 조부모 $$g$$ 의 모양에 따라 세 경우:

zig ( $$p$$ 가 루트): $$x$$ 와 $$p$$ 를 한 번 회전.
zig-zig ( $$x,p$$ 가 같은 쪽 자식): 먼저 $$p$$ – $$g$$ 회전, 다음 $$x$$ – $$p$$ 회전.
zig-zag (반대쪽): $$x$$ – $$p$$ , 이어서 $$x$$ – $$g$$ 회전.

zig-zig를 "조부모 먼저" 돌리는 것이 핵심으로, 이것이 경로를 절반으로 접어 amortized 보장을 만든다.

Amortized 분석 (포텐셜)

노드 $$v$$ 의 크기를 $$s(v)$$ , 랭크 $r(v)=\log_2 s(v)$ , 포텐셜 $\Phi = \sum_v r(v)$ 로 정의한다. 한 번의 스플레이 비용(회전 수)은

$\text{amortized cost} \le 3\big(r(\text{root}) - r(x)\big) + 1 = O(\log n)$

임이 Access Lemma로 증명된다. 따라서 $$m$$ 번 연산의 총비용은 $O((m+n)\log n)$ .

시퀀스로서의 스플레이 트리

원소를 중위 순회 순서 = 배열 인덱스로 보면, 스플레이 트리는 동적 배열이 된다. $$k$$ 번째 원소 찾기는 서브트리 크기로 내려가고, $$[l,r]$$ 구간을 다루려면 그 구간을 한 서브트리로 고립(splay 2번) 시킨다: $$l-1$$ 번째를 루트로, $$r+1$$ 번째를 그 오른쪽 자식 루트로 올리면 가운데 서브트리가 정확히 $$[l,r]$$ .

lazy 전파

구간 뒤집기는 노드에 rev 플래그를 두고, 내려갈 때 자식 좌우를 swap하며 전파한다. 구간 덧셈/합도 동일한 lazy 패턴. 회전 전에는 반드시 push_down, 회전 후에는 pull_up(크기/합 재계산).

비교

구조	균형	구간 뒤집기	비고
스플레이	amort. $O(\log n)$	가능	단순, 상수 다소 큼
Treap	기대 $O(\log n)$	가능(implicit)	난수 의존
Red-Black	최악 $O(\log n)$	어려움	STL map 내부

2강 구현: implicit 스플레이 트리와 구간 뒤집기 공식

implicit 키 스플레이 트리

배열 $$[1..n]$$ 에 대해 구간 뒤집기를 지원한다. 키 대신 서브트리 크기로 위치를 찾는다.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
struct Node { int ch[2], par, sz, val; bool rev; } t[MAXN];
int root, cnt;

void pull(int x){ t[x].sz = t[t[x].ch[0]].sz + t[t[x].ch[1]].sz + 1; }
void push(int x){
    if (t[x].rev) {
        swap(t[x].ch[0], t[x].ch[1]);
        for (int c : {t[x].ch[0], t[x].ch[1]}) if (c) t[c].rev ^= 1;
        t[x].rev = false;
    }
}
int dir(int x){ return t[t[x].par].ch[1] == x; }       // x가 부모의 오른쪽?
void rotate(int x){
    int p = t[x].par, g = t[p].par, d = dir(x);
    if (g) t[g].ch[dir(p)] = x; t[x].par = g;
    t[p].ch[d] = t[x].ch[d ^ 1];
    if (t[x].ch[d ^ 1]) t[t[x].ch[d ^ 1]].par = p;
    t[x].ch[d ^ 1] = p; t[p].par = x;
    pull(p); pull(x);
}
void splay(int x, int goal = 0){
    while (t[x].par != goal) {
        int p = t[x].par, g = t[p].par;
        if (g != goal) (dir(x) == dir(p)) ? rotate(p) : rotate(x);
        rotate(x);
    }
    if (!goal) root = x;
}
int kth(int k){                                        // k번째 노드를 루트로
    int x = root;
    while (x) { push(x);
        int ls = t[t[x].ch[0]].sz;
        if (k == ls + 1) break;
        if (k <= ls) x = t[x].ch[0];
        else { k -= ls + 1; x = t[x].ch[1]; }
    }
    splay(x); return x;
}
void reverse_range(int l, int r){                      // [l, r] 뒤집기 (1-indexed, 양끝 보초 포함)
    int a = kth(l - 1);
    int b = kth(r + 1);
    splay(a); splay(b, a);
    t[t[b].ch[0]].rev ^= 1;                            // 가운데 서브트리에 lazy
}

자주 하는 실수

push_down 누락. kth/splay 로 내려가기 전에 반드시 push. 빼먹으면 뒤집기 lazy가 꼬인다.
보초(sentinel). 양끝에 더미 노드 두 개를 두면 $$[1,n]$$ 전체 구간도 kth(0)/kth(n+1) 로 안전하게 고립된다.
rotate에서 par 갱신. 조부모·자식의 부모 포인터를 모두 갱신해야 한다. 한 줄만 빠져도 트리가 끊긴다.
pull 순서. 회전 후 pull(p) 다음 pull(x) (아래부터 위로).

응용

문제	연산
배열 구간 뒤집기	implicit reverse
구간 이동/삽입/삭제	서브트리 split/merge
동적 순열·로프(문자열)	위치 기반 split
구간 합/최댓값	lazy 합 + reverse

링크-컷 트리로의 연결

스플레이 트리는 링크-컷 트리(LCT)의 보조 트리로 그대로 재사용된다. 경로를 preferred path로 분해하고 각 path를 implicit 스플레이로 관리하는 것이 LCT다. 본 단원의 splay/push/pull/rotate가 LCT 구현의 토대가 된다.