영속 트립

세그먼트 트리와 마찬가지로, 트립의 영속 버전으로 흥미로운 문제들을 풀 수 있으며, 특히 문자열과 관련된 문제가 많습니다. 먼저 몇 가지 예시를 살펴본 다음 구현으로 넘어가겠습니다.

#예제 문제

문제. 문자열이 주어집니다. 이 문자열에서 임의의 위치에 대한 복사, 삭제, 삽입을 수행해야 합니다.

문자 위에 영속 트립을 만듭시다. 그러면 split을 두 번 호출하는 것만으로 임의의 부분 문자열의 복사본(정점을 가리키는 포인터)을 얻을 수 있으며, 이를 원하는 곳 어디에든 삽입할 수 있습니다. 이때 원래 부분 문자열은 변경되지 않습니다.

문제. 문자열이 주어집니다. 이 문자열에 대해 임의의 위치에서의 복사, 삭제, 삽입 및 임의의 부분 문자열 비교를 수행해야 합니다.

각 노드에 해당 부분 문자열의 다항식 해시를 저장할 수 있습니다. 그러면 같은 두 번의 분할(split)로 얻은 노드들의 해시를 비교하여 부분 문자열이 서로 같은지 확인할 수 있습니다.

문자열을 같은지뿐만 아니라 대소까지 비교하려면 이진 탐색을 이용한 표준적인 트릭을 쓸 수 있습니다. 일치하는 접미사의 길이를 탐색하고, 그 길이를 찾으면 다음 문자를 비교하면 됩니다.

문제. 믿기 어렵겠지만, 문자열이 주어집니다. 이 문자열에 대해 같은 변경 연산을 수행하고, 각 쿼리 후에 문자열의 최소 주기, 즉 길이 $k$인 접두사를 $\frac{n}{k}$번 반복하면 전체 문자열이 되는 최소의 수 $k$를 구해야 합니다.

먼저 구축한 트리를 이용해 $k$가 주기(최소일 필요는 없는, 어떤 주기든)인지 확인하는 방법을 알아봅시다. 처음 $k$개의 문자를 분리하여 그로부터 다항식 해시 $h_k$를 계산하고, 문자열 전체의 해시 $h$도 계산합니다. 문자열 전체가 단순히 길이 $k$인 접두사의 복사본 $\frac{n}{k}$개를 이어 붙인 것이라면, 그 해시는 다음과 같아야 합니다:

따라서 길이 $k$인 접두사의 해시를 구간 분리 또는 트리 하강으로 계산하면 $O(\log n)$ 시간에 검사를 수행할 수 있습니다.

이제 $n$의 약수 중에서 여러 후보 $k$를 순회하며 각각을 로그 시간에 확인할 수 있습니다. 어떤 주기의 약수 $p$에 대해 $\frac{n}{p}$ 역시 주기가 된다는 점을 이용하면 더 빠르게 할 수도 있습니다. $n$의 소인수분해를 살펴보고 이러한 확인을 통해 소인수를 한 번에 하나씩 제거해 나가면, 최소 주기의 소인수분해만 남게 됩니다.

$n$의 소인수분해에는 인수가 $O(\log n)$개 이하이므로, 해법은 쿼리당 $O(\log^2 n)$에 동작합니다(소인수분해는 제외한 것이지만, 문자열 길이에 합리적인 제한이 있다면 소인수분해는 미리 계산해 둘 수 있습니다).

#구현

구현은 포인터 기반의 모든 영속 자료구조와 거의 같습니다. 어떤 정점으로 이동하기 전에 그 정점의 복사본을 만들고, 그 복사본으로 이동해야 합니다. 이를 위해 보조 함수 copy를 만듭시다:

Node* copy(Node *v) { return new Node(*v); }

모든 메서드에서 우리는 그 안에서 언급되는 모든 정점을 복사하는 것으로 시작하겠습니다. 예를 들어, 영속 split은 다음과 같이 시작합니다:

Pair split(Node *p, int x) {
    p = copy(p);
    // ...
}

세그먼트 트리에서는 단순히 정점의 복사본을 만드는 것으로 충분했습니다. 이는 보통 모든 결정적 자료 구조에서 충분하지만, 트립에서는 상황이 더 복잡합니다.

우선순위를 ‘무너뜨리는’ 테스트가 존재합니다. 한 정점의 버전을 여러 개 복사해 두고 나머지 정점을 모두 삭제하면 됩니다. 그러면 모든 정점의 우선순위가 같아지고, 트리는 ‘대나무’ 형태로 변하여 모든 연산이 $O(n)$에 동작하게 됩니다.

이 문제에는 매우 우아한 해결책이 있습니다. 우선순위를 없애고 다음과 같이 다시 매다는 것입니다. 왼쪽 트리의 크기가 $L$이고 오른쪽 트리의 크기가 $R$이라면, $\frac{L}{L+R}$의 확률로 왼쪽 트리를 루트로 삼아 매달고, 그렇지 않으면 오른쪽 트리를 루트로 삼아 매답니다.

정리. 이러한 재연결은 우선순위를 사용하는 것과 동치입니다.

증명. 모든 정점이 여전히 루트가 될 확률이 동일함을 보이겠습니다. 귀납법으로 증명합시다:

• 리프가 자기 자신의 루트일 확률은 1입니다 (귀납의 기저)
• 귀납 단계는 merge 연산입니다. 왼쪽 트리의 임의의 정점은 (귀납 가정에 의해) $\frac{1}{L}$의 확률로 루트였으며, 병합 후에는 $\frac{1}{L} \cdot \frac{L}{L+R} = \frac{1}{L+R}$의 확률로 전체 트리의 루트가 됩니다. 오른쪽 트리의 정점들도 마찬가지입니다.

결국 이렇게 다시 매달더라도 여전히 임의의 서브트리의 각 정점은 같은 확률로 그 서브트리의 루트가 될 수 있었으며, 트립의 점근적 복잡도에 대한 우리의 증명은 바로 이 사실에 기반하고 있었습니다.

Node* merge(Node *l, Node *r) {
    if (!l) return r;
    if (!r) return l;
    l = copy(l), r = copy(r);
    if (rand() % (size(l) + size(r)) < size(l)) {
        // ...
    }
    else {
        // ...
    }
}

철학적 질문입니다: 트립에서 $x$와 $y$를 모두 제거해도 그것을 여전히 데카르트 트리라고 부를 수 있습니까?