개요

이 자료구조는 여러모로 유용하지만, 코드를 작성하는 것은 다소 복잡합니다. 특히 길이가 매우 길어질 수 있습니다.

기본 지식: 세그먼트 트리

본론

지속성 세그먼트 트리—문자 그대로 해석하면 '주석이 달린 트리'입니다.

지속성 세그먼트 트리는 여러 개의 세그먼트 트리로 구성됩니다(개인적인 이해, 아래 그림 참조).

처음에는 단 한 그루의 세그먼트 트리만 존재합니다(파란색).

특정 노드를 수정하려면 해당 노드에서 루트까지의 경로 상태가 변경되며, 다른 노드들은 변하지 않습니다. 이를 위해 새로운 세그먼트 트리를 만드는 것은 시간과 공간을 많이 차지합니다.

하지만 변경되는 부분은 하나의 경로뿐이므로 나머지 부분은 이전 세그먼트 트리의 값을 그대로 사용할 수 있습니다(빨간색 부분). 마찬가지로 왼쪽 노드도 동일하게 처리됩니다(녹색 부분).

이제 지속성 세그먼트 트리에 대해 이해했으니, 연습 문제로 실력을 테스트해봅시다:

연습 문제 1

USOJ3041

구체적인 구현은 코드를 참고하세요.

아래는 코드 예제입니다:

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;
const int MAXN = 10005;
const int MAXQ = 100005;

int n, Q, tot, version;
int queryL, queryR;
int modifyPos, newValue;
int root[MAXQ];
struct Node {
    int left, right, maxVal;
} nodes[(MAXN << 2) + MAXQ * 17];

int Read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void Build(int idx, int l, int r) {
    if (l == r) {
        nodes[idx].maxVal = Read();
        return;
    }
    nodes[idx].left = ++tot;
    nodes[idx].right = ++tot;
    int mid = (l + r) >> 1;
    Build(nodes[idx].left, l, mid);
    Build(nodes[idx].right, mid + 1, r);
    nodes[idx].maxVal = max(nodes[nodes[idx].left].maxVal, nodes[nodes[idx].right].maxVal);
}

int Query(int idx, int l, int r) {
    if (queryL > r || queryR < l) return -0x3f3f3f3f;
    if (queryL <= l && r <= queryR) return nodes[idx].maxVal;
    int mid = (l + r) >> 1;
    return max(Query(nodes[idx].left, l, mid), Query(nodes[idx].right, mid + 1, r));
}

void Modify(int idx, int l, int r, int prevIdx) {
    if (l == r) {
        nodes[idx].maxVal = newValue;
        return;
    }
    int mid = (l + r) >> 1;
    if (modifyPos <= mid) {
        nodes[idx].left = ++tot;
        nodes[idx].right = nodes[prevIdx].right;
        Modify(nodes[idx].left, l, mid, nodes[prevIdx].left);
    } else {
        nodes[idx].left = nodes[prevIdx].left;
        nodes[idx].right = ++tot;
        Modify(nodes[idx].right, mid + 1, r, nodes[prevIdx].right);
    }
    nodes[idx].maxVal = max(nodes[nodes[idx].left].maxVal, nodes[nodes[idx].right].maxVal);
}

int main() {
    n = Read();
    Q = Read();
    root[++version] = ++tot;
    Build(root[1], 1, n);
    for (; Q; --Q) {
        int operation = Read();
        int k = Read();
        if (!operation) {
            queryL = Read();
            queryR = Read();
            printf("%d\n", Query(root[k], 1, n));
        } else {
            modifyPos = Read();
            newValue = Read();
            root[++version] = ++tot;
            Modify(tot, 1, n, root[k]);
        }
    }
    return 0;
}

연습 문제 2

지속성 세그먼트 트리 1 (LOJ)

주의: 문제에서 제공된 배열 (ppl)을 이용하여 데이터를 이산화해야 합니다.

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;
const int MAXN = 200005;

int n, Q, tot, version;
int k, modifyPos;
int queryL, queryR;
int root[MAXN], ppl[MAXN];
struct Item {
    int value, id;
    bool operator<(const Item &b) const {
        return value < b.value;
    }
} items[MAXN];

struct Node {
    int leftChild, rightChild, count;
} nodes[(MAXN << 2) + MAXN * 18];

int Read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int Query(int idx1, int idx2, int l, int r) {
    if (l == r) return l;
    int diff = nodes[nodes[idx2].leftChild].count - nodes[nodes[idx1].leftChild].count;
    int mid = (l + r) >> 1;
    if (k <= diff)
        return Query(nodes[idx1].leftChild, nodes[idx2].leftChild, l, mid);
    k -= diff;
    return Query(nodes[idx1].rightChild, nodes[idx2].rightChild, mid + 1, r);
}

void Add(int idx, int l, int r, int prevIdx) {
    if (l == r) {
        nodes[idx].count = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if (modifyPos <= mid) {
        nodes[idx].leftChild = ++tot;
        nodes[idx].rightChild = nodes[prevIdx].rightChild;
        Add(nodes[idx].leftChild, l, mid, nodes[prevIdx].leftChild);
    } else {
        nodes[idx].leftChild = nodes[prevIdx].leftChild;
        nodes[idx].rightChild = ++tot;
        Add(nodes[idx].rightChild, mid + 1, r, nodes[prevIdx].rightChild);
    }
    nodes[idx].count = nodes[nodes[idx].leftChild].count + nodes[nodes[idx].rightChild].count;
}

int main() {
    n = Read();
    Q = Read();
    Build(root[0], 1, n);
    for (int i = 1; i <= n; ++i) {
        items[i].value = Read();
        items[i].id = i;
    }
    sort(items + 1, items + n + 1);
    for (int i = 1; i <= n; ++i)
        ppl[items[i].id] = i;
    for (int i = 1; i <= n; ++i) {
        root[++version] = ++tot;
        modifyPos = ppl[i];
        Add(tot, 1, n, root[version - 1]);
    }
    for (; Q; --Q) {
        queryL = Read();
        queryR = Read();
        k = Read();
        printf("%d\n", items[Query(root[queryL - 1], root[queryR], 1, n)].value);
    }
    return 0;
}