구간트리
구간트리는 일차원 배열이 주어질 때 각각의 구간을 특정 기준으로 질의를 던졌을 때 빠르게 답을 구할 수 있는 알고리즘이다.
일반적으로 구현을 한다면 매번 모든 데이터를 읽어서 원는 답을 얻어야하는데 시간면에서는 효율적이지 못하다. 구간트리를 이용한다면 모든 질의를 O(logN) 시간복잡도가 걸리게 되며, 굉장히 빠른 시간 내에 답을 구할 수 있다
대표적으로 목적에 따라서 전처리 과정과 그리고 질의 처리, 구간의 정보 갱신이 대표적인 구현이 있다. 구간 트리는 이진트리를 통해 표현하며, 전처리 과정과 질의처리, 갱신이 거의 비슷한 과정이고 목적에 따라 조금의 차이가 있다.
즉, 구간트리는 이진트리로 구성된 트리로
먼저 int형 데이터가 N개 있다고 할 떄, 데이터들 중 최소값을 찾으려면 모든 값을 비교하여 찾을 때, O(N)번 연산을 해야 최소값을 찾을 수 있다.
하지만 세그트리는 이러한 연산을 O(1)만에 해결할 수 있다. 이러한 이유는 각 트리의 노드에 구간정보를 저장하고 있기 때문이다.
또한, 특정 구간을 찾으려면 O(log N)만에 찾을 수 있다.
자식이 있는 "부모노드"는 구간에 대한 정보를 갖고 있다.
자식이 없는 "리프노드"는 하나의 정보만 가지고 있다.
위 그림은 배열을 이용해 이진트리를 구성할 때, 인덱스의 점화식을 보여준다.
왼쪽 노드는 부모 노드 인덱스에서 두배를 해준 값이고, 오른쪽 노드는 두배에서 +1을 해준 값이 된다.
합을 구현할 때 root index를 1로 했던 것 처럼, 구간 트리에서도 root index를 1로 하는 것이 편하다. 물론 0으로 해도 되지만, 왼쪽 노드와 오른쪽 노드의 점화식을 다르게 줘야한다.
구간트리는 이진트리를 이용한 표현으로 서브트리에 세부 구간으로 들어가서 값을 지정해주는 것이 구간트리다. 대표적인 예로 구간 합을 예로 둬서 설명을 하겠다.
처음 주어지는 일차원 배열 10개의 정수형 정보다. 이 정보를 이진트리고 구간의 합을 표현한 그림을 아래와 같이 그려봤다.
구간의 길이가 1인 노드는 리프가 되는 것이 특징이며, 처음 주어진 1차원 배열의 각각의 값이 된다.
루트는 모든 구간의 정보를 담고있고, 왼쪽 노드는 구간의 1부터 절반(mid)값 까지의 정보를 담고있고, 오른쪽 노드는 절반(mid+1)에서 N번째 까지의 정보를 담는다.
구간이 겹치지 않도록 구현해야 한다.
구간트리 구성에 필요한 크기
세그트리의 노드 수는 데이터가 N일때, N <= 리프노드의 수 로 만들어 주면 된다.
예를들어 8개의 데이터가 필요하면 리프노드는 2^3 개가 필요하다.
총 필요한 노드의 수는 리프노드의 수 + 부모노드의 수 이다.
= 2^3 + 2^2 + 2^1 + 2^0
즉 총 15 개가 필요하다. 그러므로 만들어야 하는 배열의 크기는 2^(높이+1)-1 만큼의 공간이 필요하다.
#include <cstdio>
#include <cmath>
typedef int type;
vector<type> input; // 입력으로 데이터 정보를 담고있는 vector
vector<type> seg; // 구간트리를 만들 vector
const INF = 987654321;
int main(){
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &input[i]);
int h = ceil(log2(n));
seg = vector<type>(1 << (h+1)); //구간트리
return 0;
}
구간트리 노드의 정보
각 노드의 위에 위치한 번호는 배열의 인덱스이다.
그리고 노드 안에 속한 값은 [a,b] : a,b,를 포함한 a,b사이의 구간 정보를 갖고있는다.
배열 인덱스 0을 사용하지 않고,
배열 인덱스 1부터 사용하는 이유는 부모노드가 자식노드로 가기 위해서 이다.
P : 부모노드 인덱스
C1, C2 : 자식노드 인덱스라 하면,
C1 = 2 P
C2 = 2 P +1
으로 배열에 위치한 자식노드로 갈 수 있다.
처음에 구간트리에 정보를 올리기 위해서는 데이터를 모두 다 받아야한다.
위 트리에는 8개의 정보를 가지고 있는 배열을 입력 받아 구간트리의 정보를 업데이트 할 수 있다.
구간트리 초기화
구간의 합 또는 최대 그리고 최소값이든 특정 기준에 따라 구간의 값을 지정해주는 과정을 말한다.
트리를 그리는 과정은 재귀호출을 이용한다.
전역으로 선언한 배열
input : 입력으로 데이터 정보를 담고있는 vector
seg : 구간트리를 만들 vector
를 이용한다.
-
left == right
left와 right가 같은 경우는 구간이 1인 구간이다.
재귀함수에서 기저사례가 되는 부분이다.
그 때의 트리 node(index)에 arr배열 값을 대입해 준 후에 리턴하면 된다. -
left!=right
구간이 1이 아닌 경우는 왼쪽 노드와 오른쪽 노드의 합이 내 노드의 값이 된다.
때문에 mid 구간의 절반 값을 구한 후 트리 node (index)에 왼쪽과 오른쪽을 갔을 때의 값을 더해서 리턴시켜 주면 된다.
int makeTree(int left, int right, int node){
if (left == right) { // 구간이 1인 경우
return tree[node] = arr[left];
}
int mid = (left+right) / 2;
tree[node] += makeTree(left,mid,node*2); //왼쪽 노드 합
tree[node] += makeTree(mid+1, right, node*2+1); //오른쪽5 노드 합
return tree[node];
}
구간트리 질의 처리 (정보 얻기)
구간 정보를 얻기 위해서 query를 작성한다.
질의 처리는, 주어진 구간 트리를 가지고, 내가 원하는 구간의 값을 물어 볼 때 답을 수 있는 것을 말한다.
이떄 구간 정보를 얻기 위해 구간들이 생기는 경우는 총 4가지 이다.
1) 찾아내야 할 구간과 노드가 가진 정보 구간이 겹치지 않는 경우
- 더이상 탐색한느 것이 무의미 query와 상관 없는 값을 return
2) 찾아내야 할 구간 안에 노드가 가진 구간이 포함되는 경우
- 더이상 탐색하는 것이 무의미. 현재 가진 정보 구간의 값을 return
3) 찾아내야 할 구간과 노드가 가진 정보 구간이 부분적으로 겹치는 경우
4) 찾아내야 할 구간이 노드가 가진 정보 구간 안에 포함되는 경우
- 3)4) 경우는 탐색 계속 진행
typedef int type;
vector<type> input;
vecotr<type> seg;
const INF = 987654321;
type mn2(type a, type b){
return (a > b)? b : a;
} //최소값을 return
// s-e : 노드 정보 구간
// l-r : 찾을 정보 구간
type query(int node, int start, int end, int left, int right){
if(end < left || right < start) return INF; // 경우 1)
if(left <= s && e <= r) return seg[node]; //경우 2)
int mid = (start+end)/2;
return mn2(query(2*node, start,mid,l,r), query(2*node+1,mid+1,end,l,r));
구간트리 노드정보 업데이트(갱신)
갱신은 일차원 배열의 값이 변화하는 경우를 말한다. 본래의 값이 변화하면 구간트리의 값도 크게 변동이 생긴다. 하지만 변화의 차이의 값을 가지고 루트부터 탐색을 한다면 이 또한 O(logN)으로 갱신이 가능하다.
수를 변경할 떄는 아래의 정보를 이용하여 업데이트 할 수 있다.
- 노드가 담당하는 정보구간(start-end)
- 바뀌는 노드의 위치(index)
- 바뀌는 노드의 값(value)
이때 세그트리를 탐색하며 나타나는 경우는
1. start와 end를 포함하여 start-end 사이에 노드가 위치한 경우
- 바로 리턴
2. 1이외의 경우, 포함하지 않는 경우
- 노드에게 차이만큼 더해줌
void upDate(int left, int right, int node, int change_node,int diff){
if(!(left <= change_node && change_node <= right)) return; //구간 밖
tree[node]+=diff;
if(left != right){ // 경우 1)
int mid = (left+right)/2;
upDate(left,mid,node*2,change_node, diff);
upDate(mid+1, right,node*2+1,change_node,diff);
}
}[left,right] : 현재 구간
node : 현재 노드
change_node : 값을 바꾸려는 노드
diff : 원래 값에서 변화한 값 차이
