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;
}
'강의자료 > 알고리즘' 카테고리의 다른 글
[자료구조] Suffix Array(접미사 배열) (11) | 2023.01.04 |
---|---|
[자료구조] Persistent Segment Tree (PST) (12) | 2022.12.27 |
[알고리즘]A*(a스타) 알고리즘 (8) | 2022.07.14 |
[알고리즘]Union Find (12) | 2022.06.09 |
[자료구조]스택(Stack) (8) | 2022.04.05 |