Persistent Segment Tree

Persistent Segment Tree는 가상으로 $N$개의 Segment Tree를 두는데 공간복잡도는 $O(N \lg N)$인 Segment Tree 구축 기법이다.

Persistent Segment Tree는 주로 update 질의가 없는 2D range query에서 쓰인다. 예를 들어, 2차원 좌표상에 $N$개의 점이 있고, x, y 좌표가 모두 1이상 $N$이하이면서, x 좌표가 $N$개의 점에 대해 서로 다르다고 하자.

이 때, 특정 영역에 대해 영역 안의 점의 수를 세는 질의를 $O(\lg N)$ 시간안에 해결할 수 있다.

다음과 같이 $N$개의 Segment Tree와 그 트리에서 함수 count(y1, y2)를 정의하자.

1) Tree[i] = x 좌표가 1이상 i이하인 점들만 있다고 했을 때, y 좌표 기준으로 점의 개수를 세는 Segment Tree.

2) Tree[i].count(y1, y2) = Tree[i]에서 y 좌표가 y1이상 y2이하인 점의 개수를 세는 함수

*** Tree[i].count는 일반적인 Segment Tree에서의 연산이므로 시간복잡도가 당연히 $O(\lg N)$이다.

왼쪽 아래 점이 (x1, y1)이고 오른쪽 위 점이 (x2, y2)인 직사각형 영역에 포함되어 있는 점의 개수는 Tree[x2].count(y1, y2) - Tree[x1-1].count(y1, y2)가 된다. 시간복잡도는 당연히 $O(\lg N)$ 이다.

그렇다면 $N$개의 Segment Tree는 어떻게 구축할까?

처음 가정에서 편의를 위해 점들의 x 좌표는 1부터 $N$ 사이이며 서로 다르다고 했었다.

Tree[1]은 일반적인 방법으로 만들면 된다. Tree[1] 부터 Tree[i-1]까지 구현이 다 되어있을 때 Tree[i]를 만드는 방법은 다음과 같다.

struct NODE{ NODE(): v(0), left(0), right(0) {} int v; NODE *left, *right; } *Tree[MAXN]; NODE *make_tree(NODE *now, int s, int e, int y, int v) { if (y < s || e < y) return now; NODE *ret = new NODE(); if (s == e){ ret->v = now->v + v; return ret; } int m = (s+e) >> 1; ret->left = make_tree(now->left, s, m, y, v); ret->right = make_tree(now->right, m+1, e, y, v); ret->v = (ret->left ? ret->left->v : 0) + (ret->right ? ret->right->v : 0); return ret; } // Y[i] = x 좌표가 i인 점의 y 좌표 (1이상 N이하) Tree[i] = make_tree(Tree[i-1], 1, N, Y[i], 1);

make_tree(Tree[i-1], 1, N, Y[i], 1); 의 시간복잡도는 $O(\lg N)$ 이고, 호출마다 새로 만드는 공간복잡도 또한 $O(\lg N)$ 이다.

그래서 $N$개의 Segment Tree를 구현하는 시간복잡도와 공간복잡도 모두 $O(N \lg N)$이 된다.

Persistent Segment Tree를 통해 $O(\lg^2 N)$의 시간복잡도를 갖는 쿼리를 $O(\lg N)$에 해결할 수 있게 되었다.

이 뿐만 아니라 Persistent Segment Tree의 특이한 구조가 있어야만 해결할 수 있는 문제도 존재한다. 대표적으로 BOI 2015 - Editor 문제가 있다.