Persistent Segment Tree (영속 세그): 시점별 스냅샷

Persistent Segtree, Persistent Segment Tree, 영속 세그, PST

정의

Persistent Segment Tree 는 매 갱신마다 이전 버전을 그대로 유지하면서 새 버전을 만드는 세그먼트 트리입니다. 각 버전은 루트 포인터 로 식별됩니다.

핵심 트릭: path copying. 갱신 경로 (O(log N) 노드) 만 복사하고 나머지는 이전 버전과 공유.

공간: 갱신 1 회당 O(log N) 노드 추가. 시간: 조회/갱신 모두 O(log N).

응용

• K-th smallest in range: 정렬 후 mediating 없이 접두 세그로 O(log N)
• Persistent Trie: 문자열 접두어 관리
• Rollback: 오프라인 문제에서 이전 상태 복원

구조

struct Node { int l, r; long long sum; };
vector<Node> pool;
vector<int> root;   // root[v] = 버전 v의 루트

int build(int l, int r) {
    int id = pool.size();
    pool.push_back({0, 0, 0});
    if (l == r) return id;
    int m = (l + r) / 2;
    pool[id].l = build(l, m);
    pool[id].r = build(m + 1, r);
    return id;
}

int update(int prev, int l, int r, int pos, long long v) {
    int id = pool.size();
    pool.push_back(pool[prev]);
    if (l == r) { pool[id].sum += v; return id; }
    int m = (l + r) / 2;
    if (pos <= m) pool[id].l = update(pool[prev].l, l, m, pos, v);
    else pool[id].r = update(pool[prev].r, m + 1, r, pos, v);
    pool[id].sum = pool[pool[id].l].sum + pool[pool[id].r].sum;
    return id;
}

참고

• Segment Tree
• Wavelet Tree (k-th in range 대안)
• Dynamic Segtree