Persistent Segment Tree

https://blog.myungwoo.kr/100

https://cubelover.tistory.com/14

 

PST는 N개의 세그먼트 트리를 만드는데, 전체 공간 복잡도가 $O(NlogN)$ 인 자료구조이다.

앞의 세그먼트 트리에서 하나의 값만 변화하는 새로운 세그먼트 트리를 만들기 위해서는 원래 세그먼트 트리의 대부분의 노드들을 재활용하고 새롭게 값이 바뀐 부분의 노드들만 변화시켜주면 된다.

 

이러한 이유로, 보통 2D 점 관리를 위한 자료구조로 Merge Sort Tree 와 함께 사용된다.

또한, Persistent 하게 구현되어, 수정이 불가능하다는 단점이 있다.

struct Node
{
    int val;
    Node *lc, *rc;
    Node() : val(0), lc(NULL), rc(NULL) {}
};
Node *tree[MAXN+10];

void maketree(Node *node, int tl, int tr)
{
    if(tl==tr) return;
    int mid=tl+tr>>1;
    node->lc=new Node();
    node->rc=new Node();
    maketree(node->lc, tl, mid);
    maketree(node->rc, mid+1, tr);
}

Node *addtree(Node *node, int tl, int tr, int pos)
{
    if(pos<tl || tr<pos) return node;
    Node *ret=new Node();
    if(tl==tr)
    {
        ret->val=node->val+1;
        return ret;
    }
    int mid=tl+tr>>1;
    ret->lc=addtree(node->lc, tl, mid, pos);
    ret->rc=addtree(node->rc, mid+1, tr, pos);
    ret->val=ret->lc->val+ret->rc->val;
    return ret;
}

int countpoint(Node *nodel, Node *noder, int tl, int tr, int k)
{
    if(tl==tr) return tl;
    int mid=tl+tr>>1;
    int cnt=noder->lc->val-nodel->lc->val;
    if(cnt>=k) return countpoint(nodel->lc, noder->lc, tl, mid, k);
    else return countpoint(nodel->rc, noder->rc, mid+1, tr, k-cnt);
}


tree[0]=new Node();
maketree(tree[0], 0, comp.size()-1);
for(i=1; i<=N; i++) tree[i]=addtree(tree[i-1], 0, comp.size()-1, getcomp(A[i]));

 

가장 먼저 첫번째로 빈 트리를 하나 만든다.

다음, 새롭게 노드를 하나씩 붙여주는데, 전에 만든 트리를 재활용할 수 있을 때는 재홀용하도록 구현한다.

만든 세그먼트 트리들은 누적합 세그먼트 트리들이기 때문에 오른쪽 - 왼쪽으로 세그먼트 트리에서의 이분탐색 등 여러가지를 일반적인 세그먼트 트리와 같이 활용할 수 있다.