Dynamic Segment Tree

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

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

 

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

따라서 최대 21 * Q 개의 공간만 있으면 가능하겠다는 아이디어에서 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 * 20 개의 배열만 만들어서 사용하면 되는 구조이다.

#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;
    updateDynamicTree(indexArr[cur].l,l,mid,pos,val);
    updateDynamicTree(indexArr[cur].r,mid+1,r,pos,val);
    int leftval = indexArr[indexArr[cur].l].value;
    int rigthval = indexArr[indexArr[cur].r].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;
}