롤백 가능한 자료 구조

모든 자료구조의 상태는 어떤 식으로든 메모리에 저장되어 있습니다. 어떤 배열들에 저장되어 있거나, 더 일반적으로는 메모리의 어떤 특정 주소들에 저장되어 있습니다. 간단히 하기 위해, 크기가 $n$인 어떤 배열 $a$가 있고, 대입 쿼리와 읽기 쿼리를 처리해야 하며, 때때로 변경 사항을 되돌려야 한다고 합시다.

#변경 목록

상태를 간단히 되돌릴 수 있도록 유지하는 가장 간단하고 일반적인 방법 중 하나는 변경된 모든 원소의 변경 로그를 유지하는 것입니다.

어떤 과거 상태로 변경 사항을 되돌리기만 하면 되는 경우(“ctrl+z"처럼), 단순히 스택을 하나 만들어 «어떤 셀이 변경되었는지, 그곳에 이전에 어떤 값이 있었는지»의 쌍을 저장하고, 상태를 되돌릴 때는 이 스택을 역순으로 순회하며 원래 값을 복원하면 됩니다.

int a[N];

stack< pair<int, int> > s;

void change(int k, int x) {
    s.push({k, a[k]});
    a[k] = x;
}

void rollback() {
    while (!s.empty()) {
        auto [k, x] = s.top();
        a[k] = x;
        s.pop();
    }
}

이러한 방식은 모든 연산에 약간의 상수 오버헤드를 추가하지만, 구조를 되돌릴 수 있게 해 줍니다. 즉, 미리 지정된 초기 상태로 되돌리거나, 스택에 위치와 값 외에 어떤 타임스탬프까지 함께 저장한다면 과거의 특정 상태로 되돌릴 수 있습니다.

#버전 배열

문제를 조금 다르게 표현해 봅시다. 처음에 0으로 채워진 배열 $a$가 있고, 다음 두 연산을 지원해야 합니다:

원소 대입 $a[k] = x$를 수행합니다.
배열을 0으로 초기화합니다.

이 문제는 더 우아하게 해결할 수 있습니다. 전역 시간 카운터 $t$와, 처음에 0으로 채워진 $a$와 같은 크기의 버전 배열 $v$를 만듭시다. 이 배열에는 해당 원소가 마지막으로 변경된 시간이 저장됩니다.

int t = 1;
int a[N], v[N];

원소의 버전이 현재 시간 $t$와 같으면 그 원소는 올바른 값이고, 그렇지 않으면 원소는 0이라고 약속합시다:

int get(int k) {
    return (v[k] == t ? a[k] : 0);
}

이제 원소에 값을 대입할 때는 그 원소의 버전을 갱신합니다:

void change(int k, int x) {
    a[k] = x;
    v[k] = t;
}

배열을 0으로 초기화할 때는 카운터 $t$를 증가시키기만 하면 됩니다:

void rollback() {
    t++;
}

이러한 접근 방식은 구현하기가 더 쉽고 오버헤드도 더 적지만, 적용할 수 있는 범위는 조금 더 좁습니다.

#‘뚱뚱한’ 노드

이제 변경 사항을 되돌리는 것이 아니라, 단순히 과거 시점의 어떤 원소들을 읽어야 한다고 합시다. 변경 사항 목록은 적합하지 않습니다. 각 읽기마다 최악의 경우 최근 변경 사항 $O(n)$개를 살펴보아야 하기 때문입니다.

각 원소마다 버전 리스트를 만들어 두고, 변경이 일어날 때마다 새 버전과 그 변경 시각을 리스트 끝에 추가합시다.

int t = 0;
vector< pair<int, int> > versions[N];

void change(int k, int x) {
    versions[k].push_back({t++, x});
}

그러면 읽을 때 모든 변경 사항을 살펴볼 필요 없이, 해당 셀에 관련된 변경 사항만 살펴보면 됩니다. 하지만 더 빠르게 할 수도 있습니다. 리스트의 원소들은 시간순으로 정렬되어 있으므로, 이진 탐색으로 쿼리의 시간을 넘지 않는 마지막 변경 사항을 찾을 수 있습니다.

int get(int k, int v) {
    auto it = upper_bound(versions[k].begin(), versions[k].end(), v);
    return (--it)->second;
}

이러한 풀이는 변경 한 번에 $O(1)$, 쿼리 한 번에 $O(\log n)$의 시간으로 동작합니다.

#변경 트리

형식적으로는 앞의 방법들로 영속성을 달성했지만, 이는 매우 제한된 의미에서입니다. 우리는 임의의 버전으로 빠르게 되돌아가 그 버전에서 「포크」를 만들면서 동시에 「대안적 미래」의 모든 버전을 보존할 수는 없습니다.

이 문제는 각 변경 옆에 포크가 일어난 버전의 번호 $p$를 함께 저장하여 해결할 수 있습니다:

struct Node {
    int k, x, p;
};

vector<Node> versions;

void change(int k, int x, int v) {
    versions.push_back({k, x, v});
}

그러면 시점 $v$에서 칸 $k$의 값을 찾으려면 이 배열을 따라 되돌아가야 합니다

int get(int k, int v) {
    int res = 0;
    for (int u = v; u > v; u = u = versions[u].p)
        if (versions[u].k == k)
            res = versions[u].x;
    return res;
}

이러한 해법은 완전한 영속 배열을 구현하지만, 최악의 경우 $O(n)$의 시간이 걸립니다.

변경 트리는 시간과 메모리를 맞바꾸는 다양한 방법으로 가속할 수 있습니다. 예를 들어, 일부 노드에 체크포인트, 즉 해당 시점의 배열 상태에 대응하는 전체 배열을 저장할 수 있습니다.

이를 구현하는 대표적인 구체적 방법은 매 읽기 쿼리마다 체크포인트를 무작위로 저장하는 것입니다. 이때 저장 확률은 다음 체크포인트에서 배열을 얻기 위해 수행해야 하는 추가 작업량에 비례합니다.