2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/알고리즘

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

원당컴1 2022. 12. 27. 09:11

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

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

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

 

11012번: Egg

You are a president deeply loved by many folks in your country. Every time you go on a parade (which is your main job, what else should a president do), the folks would throw eggs at you — because you love eggs! The folks passionately send their eggs to

www.acmicpc.net

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';
    }
}

 

 

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기

'강의자료 > 알고리즘' 카테고리의 다른 글

[알고리즘] 분할정복  (12) 2023.01.11
[자료구조] Suffix Array(접미사 배열)  (11) 2023.01.04
[자료구조]Dynamic Segment Tree  (6) 2022.10.04
[알고리즘]A*(a스타) 알고리즘  (8) 2022.07.14
[알고리즘]Union Find  (12) 2022.06.09