Persistent Segment Tree

다음과 같은 문제를 생각해 보자.

"2차원 평면에 N개의 점이 있다. M개의 직사각형이 주어질 때, 각 직사각형 내부에 있는 점의 개수를 구하여라. 단 직사각형이 주어질 때마다 답을 구해야 한다."

모든 직사각형이 주어진 뒤에 답을 구하라고 한다면 점과 직사각형을 모두 정렬한 뒤 Segment Tree 등의 자료구조를 사용해서 O((N + M) log (N + M))으로 처리할 수 있지만, 이 문제에서는 직사각형이 주어질 때마다 답을 구해야 하기 때문에 쿼리를 정렬하는 방법은 사용할 수 없다.

한 가지 관찰할 수 있는 점은 (x1, y1)을 왼쪽 아래 꼭지점으로, (x2, y2)를 오른쪽 위 꼭지점으로 갖는 직사각형 내부의 점의 개수를 Q(x1, y1, x2, y2)라 하면, Q(x1, y1, x2, y2) = Q(x1, 0, x2, y2) - Q(x1, 0, x2, y1 - 1)라는 것이다. 따라서 Q(x1, 0, x2, y) 꼴의 쿼리를 효율적으로 처리할 수 있다면, 원래의 쿼리도 효율적으로 처리할 수 있다.

Segment Tree를 y좌표의 범위만큼 만들고, k번째 Segment Tree의 각 노드는 y좌표가 k 이하인 점들에 대하여 해당 구간에 포함되는 점의 개수를 들고 있으면 쿼리를 O(log N)으로 처리할 수 있다.

다만 이렇게 했을 경우의 문제점은 전처리에 O(N^2)의 시간이 필요하다는 것이다.

이를 위해 존재하는 자료구조가 Persistent Segment Tree이다.

k번째 Segment Tree가 다음처럼 생겼다고 해 보자.

y좌표가 k+1인 점들의 x좌표가 3과 5라고 해 보자. 그러면 k+1번째 Segment Tree는 다음처럼 생겼을 것이다.

이 때 관찰할 수 있는 점은, k+1번째 Segment Tree의 노드의 대부분은 k번째 Segment Tree의 노드와 같고, 바뀌는 노드 개수가 적다는 점이다.

이렇게 바뀌는 노드 개수는 추가되는 점마다 O(log N)개이므로 총 O(N log N)개이다.

따라서 모든 노드를 새로 만들지 말고 바뀌는 노드들만 새로 만든 뒤, 나머지 노드들은 포인터로 관리하여 이전 Segment Tree의 노드를 참조하도록 하면 O(N log N)의 시간 만에 똑같은 동작을 하는 자료구조를 만들 수 있다.

이를 Persistent Segment Tree라고 하며, 대부분의 자료구조가 갱신이 가능한 것과는 다르게 갱신이 불가능하다. 그러나 2차원 쿼리를 O(log N)에 처리할 수 있다는 장점이 있다.

이 자료구조는 예제를 보는 것이 좀 더 이해하기 좋으므로, 이 글을 참고하는 것을 권장한다. (스포일러 주의)