[자료구조] Persistent Segment Tree (PST)

Persistent 의 의미는 보존 된다는 의미인데 이 알고리즘의 핵심은 서로 다른 세그먼트 끼리 값을 보존 하며 공유하는 것이 핵심입니다.

예제 문제로 다음의 문제를 예로 들어 봅시다.

https://www.acmicpc.net/problem/11012

11012번: Egg

2차원상에서 영역이 주어지면 해당 영역 안에 달걀이 몇개 존재하는지 찾는 문제입니다.

 

먼저 x좌표가 모두 동일하다고 가정해 봅시다.

그렇다면 y좌표로 [b,t] 구간의 점을 구할 때 query(b,t)로 구할 수 있습니다.

 

다음으로 x좌표가 여러개라고 생각하면 다음과 같이 생각 할 수 있습니다.

각각의 x 좌표 마다 세그먼트 트리를 한개씩 만들어서 x좌표로 진행하면서 부분합 갯수 만큼의 갯수를 누적한 후

x좌표가 [l,r] 이라면 query(r,b,t) - query(l-1,b,t) 형태로 구할 수 있습니다.

하지만 x좌표의 범위만큼 세그먼트 트리가 필요한데요~

이때 x좌표는 100000 개가 들어 오기 때문에 이 크기 만큼의 세그먼트 트리의 갯수를 만들 수가 없습니다.

 

이러한 문제를 해결하기 위해서 PST 알고리즘을 사용하는데요~ PST알고리즘이 무엇인지 살펴 봅시다.

 

편의상 l,r,t,b 가 1,4,1,4 라고 가정해 봅니다.

그리고 (1,1) 구간에 달걀이 있다는 첫번째 정보가 들어오면 세그먼트 트리의 x가 1이므로 1번째 세그먼트 트리를 다음과 같이 생성합니다.

이때 1번째 세그먼트 트리를 head[1]이라고 합니다.

다음으로 (1,2) 구간에 달걀이 있다는 두번째 정보가 들어 오면 head[1]을 가지고 다음과 같이 변경을 합니다.

 

그 다음 (2,3) 이 입력 된다면 x축이 1에서 2로 변경이 되었으므로 1번째 x축은 더 이상 입력이 없다면 head[1]의 변한 노드의 갯수는 7개가 아니라 4개만 변한 것을 알수 있습니다.

즉 head[1] 의 위치에서 전체갯수 7개를 가지고 있는 것이 아니라 변한 노드의 갯수만 가지고 가면 메모리를 줄일 수 있겠네요~

이렇게 변경된 정점만 새로 만들어 주는 알고리즘에는 Dynamic Segment Tree(https://thinkmath2020.tistory.com/3810) 가 있습니다.

 

PST 는 Dynamic Segment Tree 를 이용해서 여러개의 세그먼트 트리를 적은 메모리 공간(log(n)*100000)으로 해결 할 수 있는 알고리즘입니다. 

 

 

즉 위의 문제에서 q개의 세그먼트 트리를 저장 할 수 있는 포인터 배열을 미리 만들어 놓은 후 각각에서 Dynamic Segment Tree 를 만들어서 값을 가지고 있으면서 x1~x2 사이의 누적 값을 연산 해 주면 된다.

 

https://www.acmicpc.net/problem/11012 의 풀이

 

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define ll long long

struct Node{
    int n;
    vector<ll> t;
    void init(int k){
        t.clear();
        n=k;
        t.resize(n+1);
    }
    void update(int i,int num){
        while (i <= n) {
            t[i] += num;
            i += (i & -i); //이진수에서 마지막 위치의 1을
        }
    }
    ll query(int i){
        ll ans = 0;
        while (i > 0) {
            ans += t[i];
            i -= (i & -i);  //이진수에서 마지막 위치의 1을 뺀다.
        }
        return ans;
    }
}tree;
struct Data{
    int val,y1,y2;
};

vector<vector<int>> country;

vector<vector<struct Data>> v;
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int testcase;
    cin>> testcase;
    while(testcase--){
        int n,m;
        cin>>n>>m;
        tree.init(MAXN);
        country.clear();
        country.resize(MAXN);
        v.clear();
        v.resize(MAXN);
        int x,y;
        for(int i=0;i<n;i++){
            cin>>x>>y;
            country[++x].push_back(++y); ///x축위치에 y축 값을 입력 하자. 이때 누적 합을 찾기 위해서는 0 -> 1번지로 바꿔 줘야 0~4 사이의 누적 합을 구할 수가 있다. 
        }
        for(int i=1;i<=m;i++){
            int l,r,b,t;
            cin>>l>>r>>b>>t;
            ++r; ///r 이전까지는 합해야 한다.
            ++t; ///t 이전까지는 합해야 한다.
            v[l].push_back( {-1,b,t} ); ///현재 위치에서 시작 하는 것이므로 빼주어야 한다. 
            v[r].push_back( {1,b,t} );   
            
        }
        ll ans = 0;
        for(int i=0;i<MAXN;i++){
            for(int y:country[i])
                tree.update(y,1);
            for(auto temp:v[i]){
                ll res = tree.query(temp.y2) - tree.query(temp.y1);
                if(temp.val>0) ans += res;
                else ans -= res;
            }
        }
        cout<<ans<<'\n';
    }
}