티스토리 뷰

공부

Persistent Segment Tree

전명우 2016.06.23 17:38

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]를 만드는 방법은 다음과 같다.

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 문제가 있다.

저작자 표시
신고

'공부' 카테고리의 다른 글

Building Heap in Linear Time  (2) 2016.07.01
String Matching Algorithm  (4) 2016.06.24
Persistent Segment Tree  (4) 2016.06.23
Divide & Conquer Optimization  (0) 2016.06.23
Knuth Optimization - Dynamic Programming  (2) 2016.06.23
Majority Vote Algorithm  (1) 2016.06.23
댓글
댓글쓰기 폼