티스토리 뷰

공부

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  (6) 2016.06.23
Divide & Conquer Optimization  (2) 2016.06.23
Knuth Optimization - Dynamic Programming  (3) 2016.06.23
Majority Vote Algorithm  (1) 2016.06.23
댓글
  • 프로필사진 계절학교 학생 struct NODE에서
    NODE(): cnt(0), left(0), right(0) {} 이
    초기화 하는 건 가요?
    2017.02.25 16:53 신고
  • 프로필사진 전명우 NODE라는 structure의 생성자라고 보면 됩니다. 2017.03.21 20:02 신고
  • 프로필사진 계절학교 학생 2 make tree 함수에서 ret->v = now->v + v 라고 되어있는데 struct Node 에는 v라는 변수가 없는것 같은데 혹시 여기서 ret->v를 ret->cnt로 바꾸면 되나요 아니면 다른 문법이 있는건가요? 2017.03.07 23:04 신고
  • 프로필사진 전명우 관련된 오류들 수정했습니다. 지적 고맙습니다. 2017.03.21 20:01 신고
  • 프로필사진 degurii 게시글들 많은 도움이 되고 있습니다!
    다름이 아니라 now->left == 0 이거나 now->right == 0인 경우 런타임 에러가 뜹니다. 그래서 line 16 직전에 now의 left나 right가 없으면 새로운 node를 할당해주는 방식으로 해결했는데요. 본문의 코드가 잘못된건가 싶어 질문드립니당
    2018.07.23 05:32 신고
  • 프로필사진 전명우 좋은 지적 감사합니다. Line 18에서 null pointer에 대한 체크가 필요한데 누락됐었습니다. 수정하였습니다. 2018.07.27 16:10 신고
댓글쓰기 폼