[자료구조]Dynamic Segment Tree

Dynamic Segment Tree 는 다음과 같은 경우에 사용됩니다.

0으로 초기화 된 10억개의 수열이 있을 때 Q(10만)개의 질의에 대해 실시간으로 업데이트와 그에 대한 답을 구하는 경우 일반적인 세그먼트 트리로는 10억개의 공간을 모두 할당 할 수 없기 때문에 불가능 합니다.

 

하지만 이때 잘 생각해 보면 1번의 쿼리에 변경되는 노드의 갯수는 log2(10억) =(약)21의 갯수만 변경 되는 것을 알 수 있습니다.

따라서 최대 21 * Q(10만) 개의 공간만 있으면 가능하겠다는 아이디어에서 Dynamic Segment Tree 는 출발 합니다.

 

즉 다음과 같은 트리에서  

2번 위치의 값이 변경이 된다면 노드의 갯수를 회색으로 색칠 된 3개만 만들어 놓겠다는 것이 Dynamic Segment Tree 입니다.

이렇게 만드는 것은 링크드리스트를 이용하여 만드는 방법과 인덱스 기반으로 만드는 방법 두가지를 살펴 볼 수가 있습니다.

 

다음은 q개의 쿼리문에서 a 가 1일때 b의 위치에 c의 값을 업데이트 하고 a가 그 외의 값일때 b와 c 구간의 합을 구하는 프로그램의 예이다.

 

1. 링크드리스트를 이용한 구현 방법

링크드리스트를 이해한다면 이해하기 쉬운 구조로 자식이 없으면 생성하면서 왼쪽 오른쪽으로 진행하는 구조이다.

#include <iostream>

using namespace std;

struct Node{
    Node *l,*r; //왼쪽 자식,오른쪽 자식
    int value;  //자신의 값
    Node(){l=nullptr;r=nullptr;value=0;} ///초기값 설정
}*root;

void updateDynamicTree(Node* &cur,int l,int r,int pos,int val){
    if(cur==nullptr) cur=new Node(); ///현재 객체가 생성 되어 있지 않다면 생성
    if(l>pos||r<pos) return; ///범위를 벗어나면 리턴
    if(l==r){
        ///자신의 위치라면
        cur->value = val;
        return;
    }
    int mid = (l+r)/2; //중간 위치
    updateDynamicTree(cur->l,l,mid,pos,val);
    updateDynamicTree(cur->r,mid+1,r,pos,val);
    int leftval = cur->l->value;
    int rigthval = cur->r->value;    
    
    cur->value = leftval + rigthval;
}

int queryDynamicTree(Node *cur,int l,int r,int s,int e){
    if(cur==nullptr) return 0; ///현재 위치에 객체가 없다면 0 리턴
    if(l>e || r < s) return 0; /// 범위를 벗어난 경우 0 리턴
    if(l>=s && r <= e) return cur->value; ///범위 안이라면 해당 노드의 값 리턴
    int mid = (l+r)/2;
    int leftval = queryDynamicTree(cur->l,l,mid,s,e);
    int rigthval = queryDynamicTree(cur->r,mid+1,r,s,e);
    return leftval + rigthval;
}

int main()
{
    int q;
    cin >> q;

    while(q--){
        int a,b,c;
        cin >> a;
        if(a==1){
            cin >> b >> c;
            updateDynamicTree(root,1,1000000000,b,c);
        }
        else{
            cin >> b >> c;
            cout << queryDynamicTree(root,1,1000000000,b,c) << "\n";
        }
    }
    return 0;
}

2. 인덱스를 이용한 구현 방법

인덱스 배열을 만들어서 해당 노드를 연결 시켜 놓은 후에 각 객체의 왼쪽자식과 오른쪽 자식은 인덱스 배열의 위치를 가르키게 해 놓으면 인덱스배열은 q * 21 개의 배열만 만들어서 사용하면 되는 구조이다.

#include <iostream>

using namespace std;

struct Node{
    int l,r; //왼쪽 자식,오른쪽 자식이 생성되어 있는 객체의 위치
    int value;  //자신의 값
    Node(){l=-1;r=-1;value=0;} ///초기값 설정
};

Node indexArr[ 21 * 100000]; //21 * q 개의 배열을 생성
int indexPos = 1; ///루트는 1번지 위치부터 시작

void updateDynamicTree(int cur,int l,int r,int pos,int val){
    if(l>pos||r<pos) return; ///범위를 벗어나면 리턴
    if(l==r){
        ///자신의 위치라면
        indexArr[cur].value = val;
        return;
    }
    int mid = (l+r)/2; //중간 위치
    if(indexArr[cur].l==-1) indexArr[cur].l = ++indexPos; ///할당 되어 있지 않으면 왼쪽과 오른쪽 자식을 할당해주자
    if(indexArr[cur].r==-1) indexArr[cur].r = ++indexPos;
    int left = indexArr[cur].l;
    int right = indexArr[cur].r;
    updateDynamicTree(left,l,mid,pos,val);
    updateDynamicTree(right,mid+1,r,pos,val);
    int leftval = indexArr[left].value;
    int rigthval = indexArr[right].value;

    indexArr[cur].value = leftval + rigthval;
}

int queryDynamicTree(int cur,int l,int r,int s,int e){
    if(cur==-1) return 0; ///현재 위치에 객체가 없다면 0 리턴
    if(l>e || r < s) return 0; /// 범위를 벗어난 경우 0 리턴
    if(l>=s && r <= e) return indexArr[cur].value; ///범위 안이라면 해당 노드의 값 리턴
    int mid = (l+r)/2;
    int leftval = queryDynamicTree(indexArr[cur].l,l,mid,s,e);
    int rigthval = queryDynamicTree(indexArr[cur].r,mid+1,r,s,e);
    return leftval + rigthval;
}

int main()
{
    int q;
    cin >> q;

    while(q--){
        int a,b,c;
        cin >> a;
        if(a==1){
            cin >> b >> c;
            updateDynamicTree(1,1,1000000000,b,c);
        }
        else{
            cin >> b >> c;
            cout << queryDynamicTree(1,1,1000000000,b,c) << "\n";
        }
    }
    return 0;
}