퍼시스턴트 세그먼트 트리

버전을 보존하는 세그 트리 — 구간 k번째 수 온라인.

플래티넘 I

선수 지식: 세그먼트 트리

1강 버전을 보존하는 세그 트리 공식

영속성(persistence)이란

보통 자료 구조는 갱신하면 이전 상태가 사라진다. 퍼시스턴트 자료 구조는
갱신 후에도 과거 버전을 그대로 조회할 수 있다. 퍼시스턴트 세그먼트 트리(PST)
는 세그 트리의 모든 버전을 동시에 보관하면서, 메모리를 효율적으로 쓴다.

경로 복사(path copying)

세그 트리에서 한 점을 갱신하면 루트에서 그 리프까지의 경로상 노드들만 값이
바뀐다. 나머지 노드는 그대로다. 그래서 갱신 시 바뀌는 경로의 노드만 새로
복제하고, 바뀌지 않는 자식은 이전 버전의 노드를 그대로 가리키게 한다.

핵심: 한 번의 점 갱신은 $O(\log N)$ 개의 노드만 새로 만든다. 새 루트가 새
버전을 대표하며, 옛 버전의 루트도 그대로 살아 있다.

따라서 버전 하나 추가에 메모리·시간이 모두 $O(\log N)$ 이다. $$M$$ 번 갱신하면
총 $O(M \log N)$ 노드(메모리)와 $O(M \log N)$ 시간이다.

버전 0 루트 ──┐         버전 1 루트(일부만 새로)
              ├─ 공유 ──┤
   (안 바뀐 서브트리는 두 버전이 공유)

노드 구조

포인터 대신 인덱스 기반으로 노드 풀을 관리하는 것이 흔하다. 각 노드는
(left, right, value)를 들고, 갱신은 새 노드를 풀에 push하며 인덱스를 반환한다.

대표 응용: 구간 K번째 수 (온라인)

값을 좌표 압축해 1..M로 만든 뒤, 접두사 버전을 만든다.

버전 $$i$$ = 배열 앞 $$i$$ 개를 값 도메인에 카운트한 세그 트리(빈도 누적).
버전 $$i$$ 는 버전 $$i-1$$ 에서 $$a[i]$$ 위치를 $$+1$$ 갱신해 만든다(영속이라 $$i-1$$
보존).

구간 $$[l, r]$$ 의 값 빈도는 버전 $$r$$ − 버전 $$l-1$$ (두 트리를 동시에 내려가며
노드 값의 차)로 얻는다. 이 차이 위에서 세그 트리를 내려가며 "왼쪽 자식 카운트가
$$k$$ 이상이면 왼쪽, 아니면 $$k$$ 를 빼고 오른쪽"으로 하강하면 구간 $$k$$ 번째 수를
$O(\log N)$ 에 찾는다. 머지 소트 트리( $O(\log^2 N)$ )보다 빠르고 온라인이라는
장점이 있다.

왜 차로 구간이 되나

빈도는 가산적이라 $\text{freq}_{[l,r]} = \text{prefix}_r - \text{prefix}_{l-1}$ .
두 PST 버전을 동시에 내려가며 (오른쪽 노드 카운트) − (왼쪽 노드 카운트)를
보면 구간 빈도를 얻는다. 이것이 PST 구간 k번째의 핵심 트릭이다.

2강 구현과 활용 공식

구간 K번째 수 PST 구현

좌표 압축 후, 위치마다 새 버전을 만들고 두 버전의 차로 하강한다.

#include <bits/stdc++.h>
using namespace std;

const int MAXNODE = 20 * 100001;   // 약 M * logN 개
int lc[MAXNODE], rc[MAXNODE], cnt[MAXNODE], node_cnt = 0;
int roots[100001];                 // 각 버전(접두사)의 루트

// pos에 +1 한 새 버전을 만든다. prev는 이전 버전 노드.
int update(int prev, int l, int r, int pos) {
    int cur = ++node_cnt;
    lc[cur] = lc[prev]; rc[cur] = rc[prev]; cnt[cur] = cnt[prev] + 1;
    if (l == r) return cur;
    int m = (l + r) / 2;
    if (pos <= m) lc[cur] = update(lc[prev], l, m, pos);   // 왼쪽만 새로
    else          rc[cur] = update(rc[prev], m + 1, r, pos);
    return cur;
}
// 버전 u(=r), v(=l-1)의 차에서 k번째 작은 값
int query(int u, int v, int l, int r, int k) {
    if (l == r) return l;
    int m = (l + r) / 2;
    int left_cnt = cnt[lc[u]] - cnt[lc[v]];   // 구간 내 왼쪽 절반 빈도
    if (k <= left_cnt) return query(lc[u], lc[v], l, m, k);
    else return query(rc[u], rc[v], m + 1, r, k - left_cnt);
}

int main() {
    int n, q; scanf("%d %d", &n, &q);
    vector<int> a(n + 1), comp;
    for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); comp.push_back(a[i]); }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    int M = comp.size();
    auto idx = [&](int x){
        return lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1;
    };
    roots[0] = 0;                               // 빈 버전
    for (int i = 1; i <= n; i++)
        roots[i] = update(roots[i - 1], 1, M, idx(a[i]));
    while (q--) {
        int l, r, k; scanf("%d %d %d", &l, &r, &k);
        int v = query(roots[r], roots[l - 1], 1, M, k);
        printf("%d\n", comp[v - 1]);            // 압축 해제
    }
    return 0;
}

흔한 실수

노드 풀 크기 — 버전당 $O(\log N)$ 노드가 새로 생기므로 약 $$20N$$ 노드를
잡아야 한다. 부족하면 인덱스가 넘쳐 오답/런타임 에러가 난다.
이전 버전 공유 — update에서 바뀌지 않는 자식은 이전 노드 인덱스를
복사해야 한다. 0(빈 노드)으로 잘못 두면 카운트가 사라진다.
차이 계산 방향 — 구간 $$[l, r]$$ 은 버전 $$r$$ 에서 버전 $$l-1$$ 을 뺀다. 인덱스
off-by-one에 주의.
좌표 압축 해제 — 답은 압축 인덱스이므로 원래 값으로 되돌려 출력한다.

활용

문제	버전의 의미
구간 k번째 수(온라인)	접두사 빈도 트리
구간 내 $\le x$ 개수	두 버전 차의 접두 합
배열 과거 상태 조회	시간축 버전
2D 점 카운트(한 축 정렬)	x 좌표 순 버전

PST는 "과거를 보존하면서 효율적으로 갱신"이라는 발상으로, 온라인 구간 통계와
시간 여행 질의를 우아하게 해결한다. 같은 경로 복사 아이디어는 퍼시스턴트
배열·트라이·균형 트리로도 확장된다.