거의 모든 참조 기반 자료 구조를 영속으로 만드는 일반적인 방법은, 무엇이든 하나라도 바뀌는 모든 정점의 복사본을 만들고 그 변경을 복사본에서 수행하며, 이미 존재하는 정점은 결코 수정하지 않는 것입니다.
영속 세그먼트 트리도 여기서 예외가 아닙니다. 내려가는 과정에서 정점 자체나 그 자손을 무언가 변경하기 전에 그 정점의 복사본을 만들기만 하면 됩니다. 이렇게 해도 연산의 점근적 복잡도는 바뀌지 않으며, 다만 전체 메모리 사용량이 $O(m \log n)$까지 늘어날 뿐입니다.
가장 편리한 방법은 지연 연산의 push와 비슷하게 현재 정점의 자식들을 복사하는 함수 copy를 정의하고, 무언가 바뀔 수 있는 모든 정점에서 가리지 않고 이 함수를 호출하는 것입니다.
struct Segtree {
int lb, rb;
int s = 0;
Segtree *l = 0, *r = 0;
Segtree(int lb, int rb) : lb(lb), rb(rb) {
if (lb != rb) {
int t = (lb + rb) / 2;
l = new Segtree(lb, t);
r = new Segtree(t, rb);
}
}
void copy() {
if (l) {
l = new Segtree(*l);
r = new Segtree(*r);
}
}
void add(int k, int x) {
copy();
s += x;
if (l) {
if (k < l->rb)
l->add(k, x);
else
r->add(k, x);
}
}
int sum(int lq, int rq) {
// этот метод ничего не меняет -- он и так хороший
if (lq <= lb && rb <= rq)
return s;
if (max(lb, lq) >= min(rb, rq))
return 0;
return l->sum(lq, rq) + r->sum(lq, rq);
}
};
이제 남은 것은 버전 목록을 만들고, 각 연산이 끝날 때마다 새 루트를 그 목록에 복사하는 것뿐입니다:
vector<Segtree*> roots;
roots.push_back(new Segtree(0, n));
void add(int k, int x, int v) {
Segtree *root = new Segtree(*roots[v]);
root->add(k, x);
roots.push_back(root);
}
대안적인 접근 방식으로, 자식 노드 대신 현재 노드를 복사하고 이를 재귀에서 반환하여 부모에 다시 연결할 수도 있습니다. 이 방식은 계산상 더 효율적이지만, 구현을 크게 변경해야 합니다.
#응용
자료 구조 문제에서 영속 세그먼트 트리는 특히 쿼리를 미리 알 수 있었다면 스위프 라인 기법을 적용했을 문제에서 자주 사용됩니다.
#직사각형 위의 합
문제. 평면 위에 $n$개의 점이 주어집니다. 직사각형 안에 있는 점의 개수를 묻는 $q$개의 쿼리에 온라인으로 답해야 합니다.
오프라인으로 답할 수 있다면, 쿼리를 두 개의 접두사 쿼리로 나누고 왼쪽에서 오른쪽으로 스위프 라인을 진행하면서 점들의 $y$좌표를 세그먼트 트리에 추가하고 부분 구간 합 쿼리에 답하면 됩니다. 하지만 그렇게 할 수는 없습니다.
하지만 점들은 오프라인으로 미리 알 수 있습니다. 이 점들을 같은 순서로 일반 세그먼트 트리가 아닌 영속 세그먼트 트리에 추가하고, 서로 다른 $x$좌표에 해당하는 트리들의 루트를 증가하는 순서로 저장합시다.
이제 쿼리를 마찬가지로 두 개로 분해하여 더 큰 $x$-좌표와 더 작은 $x$-좌표에 해당하는 세그먼트 트리의 서로 다른 두 버전으로 보냄으로써 쿼리에 답할 수 있습니다. 이렇게 하면 쿼리에 온라인으로 $O(q \log n)$의 시간과 메모리로 답할 수 있습니다.
#순서 통계량
문제. $n$개의 정수로 이루어진 구간과 부분 구간에서의 $k$번째 순서 통계량을 구하는 $q$개의 쿼리가 주어집니다.
먼저, 모든 수를 1부터 $n$까지의 값이 되도록 압축합시다.
그다음, 합을 위한 퍼시스턴트 세그먼트 트리를 가지고 배열을 왼쪽에서 오른쪽으로 훑어 나가면서, 원소 $a_k$를 처리할 때 세그먼트 트리의 $a_k$번째 원소에 1을 더합니다. 이러한 트리에서 $l$부터 $r$까지의 합은 현재 접두사에서 $l$과 $r$ 사이에 있는 원소의 개수와 같다는 점에 주목하십시오.
다음으로 트리의 차를 해당 배열들의 차 위에 구축했을 때 얻어지는 세그먼트 트리로 정의합니다.
$r$번째 트리와 $l$번째 트리의 차($r > l$)에는 무엇이 들어 있겠습니까? 그곳에는 배열의 $l$부터 $r$까지의 구간에서 각 수가 등장한 횟수, 즉 음이 아닌 정수로 이루어진 어떤 배열이 들어 있습니다. 이러한 차 트리에서 접두사 합이 $k$를 넘지 않는 마지막 위치를 찾는 하강을 수행하면, 그 위치가 바로 쿼리의 답이 됩니다.
차분 트리에서 하강하기 위해 그 트리를 명시적으로 만들 필요는 없습니다. 두 트리에서 동시에 하강하면서 모든 곳에서 합 $s$ 대신 $(s_r - s_l)$를 사용하면 됩니다:
int kth(Segtree *l, Segtree *r, int k) {
if (k == 0)
return l->lb;
int s = r->l->s - l->l->s;
if (s <= k)
return kth(l->l, r->l, k);
else
return kth(l->r, r->l, k - s);
}
이 문제와 앞의 문제는 mergesort tree를 이용해 $O(n \log^2 n)$에 풀 수도 있고, 2차원 자료구조를 이용해 같은 점근적 복잡도로 풀 수도 있다는 점에 주목하십시오.
#지배 원소
문제. $n$개의 원소로 이루어진 배열이 주어집니다. 구간 $[l, r)$에 지배적인 원소, 즉 그 구간에서 적어도 $\frac{r-l}{2}$번 등장하는 원소가 있는지 묻는 $m$개의 쿼리에 답해야 합니다.
이 문제에는 놀라울 정도로 간단한 해법이 있습니다. 무작위 원소를 약 100개 뽑아 각각이 지배적인지 확인하는 것입니다. 각 값마다 그 값이 등장하는 위치들의 정렬된 목록을 미리 계산해 두고 그 목록에서 이진 탐색을 두 번 수행하면, 확인을 $O(\log n)$에 할 수 있습니다. 최악의 경우 오류 확률은 $\frac{1}{2^{100}}$이며, 실제로는 이를 무시해도 됩니다.
하지만 100개의 샘플을 검사하는 것은 오래 걸립니다. 이전 문제와 같은 세그먼트 트리를 구성하고, 차분 트리에 대해 “합이 $n$ 이하인 $n$개의 음이 아닌 정수로 이루어진 배열에서 $\frac{n}{2}$보다 큰 수를 찾는” 문제를 풉시다. 이것 역시 트리를 따라 내려가는 방식이 됩니다. 매번 합이 더 큰 자식으로 내려갑니다(합이 더 작은 자식은 확실히 지배적이지 않기 때문입니다). 도달한 리프의 값이 필요한 값보다 크면 true를, 그렇지 않으면 false를 반환합니다.
연습 문제. 작은 $k$(2부터 5까지)에 대해 적어도 $\frac{r-l}{k}$번 등장하는 원소를 지배적인 원소로 보는 문제에서 내려가기를 어떻게 수정할 수 있을지 생각해 보십시오.
#영속 배열로서
완전 영속 배열은 보통 세그먼트 트리로 구현합니다. 일반적인 경우 쿼리당 $O(\log n)$보다 빠르게 만들 수는 없습니다. 영속 배열은 다시 참조 기반이 아닌 자료구조를 영속 자료구조로 만드는 데 사용할 수 있습니다. 예를 들어 서로소 집합이 그렇습니다.
DSU에서는 모든 상태를 배열에 저장하는데, 이 배열들은 세그먼트 트리를 통해 간단히 영속으로 만들 수 있습니다. 이러한 구조의 점근적 복잡도는 시간과 메모리 모두 $O(n \log n)$이 됩니다. 여기서 로그는 DSU 자체에서도 나오고(경로 압축 휴리스틱을 사용할 수 없으므로 $O(\log n)$개의 조상을 거쳐야 합니다), 영속 세그먼트 트리에서도 나옵니다(어떤 $p_v$와 $s_v$ / $h_v$의 값을 갱신해야 합니다).