구간트리(세그먼트트리;Segment tree)

세그먼트 트리에 대해 정리.

1) 세그트리 구성에 필요한 크기

2) 세그트리 노드정보

3) 세그트리 초기화

4) 세그트리의 정보얻기

5) 세그트리 노드정보 업데이트

이진트리로 구성된 트리로

먼저, int형 데이터가 N개가 있다고 할 때, 데이터들 중 최소값을 찾으려면 모든 값을 비교하여 찾을 때, O(N) 번 연산을 해야 최소값을 찾을 수 있다.

하지만 세그트리는 이러한 연산을 O(1) 만에 해결할 수 있다. 이러한 이유는 각 트리의 노드에 구간정보를 저장하고 있기 때문이다. 

또한, 특정 구간을 찾으려면 O(logN) 만에 찾을 수 있다.

자식이 있는 "부모노드"는 구간에 대한 정보를 가지고 있는다.

자식이 없는 "리프노드"는 하나의 정보만 가지고 있는다.

1) 세그트리 구성에 필요한 크기

세그트리의 노드 수는 데이터가 N개 일 때,

N <= 리프노드의 수 로 만들어 주면 된다. 

8개의 데이터가 필요하므로 리프노드는 2^3개가 필요하다.

총 필요한 노드의 수는 리프노드의 수 + 부모노드의 수 이다.

= 2^3 + 2^2 + 2^1 + 2^0

즉 총 15개가 필요하다. 그러므로 만들어야 하는 배열의 크기는 2^(높이+1) - 1 만큼의 공간이 필요하다.

배열인덱스 0은 사용하지 않으므로 -1

#include<cstdio>
#include<cmath>
 
typedef int type;
vector<type> input;
vector<type> seg;
const INF = 987654321;
 
int main(){
    scanf("%d", &n);
    for(int i = 0 ; i < n ; i++) scanf("%d", &input[i]); // input
   
    int h = ceil(log2(n));
    seg = vector<type>(1 << (h+1) ); // seg tree 
 
    return 0;
}

8개의 데이터를 가지고 있다고 하자.  이때 세그트리의 모양은 아래와 같다.

2) 세그트리 노드의 정보

각 노드의 위에 위치한 번호는 배열의 인덱스이다. 

그리고 노드안에 속한 값은 [a,b] : a, b를 포함한 a와 b 사이 구간정보를 갖고있는다.

배열 인덱스 0을 사용하지 않고,

배열 인덱스를 1부터 사용하는 이유는 부모노드가 자식노드로 가기 위해서 이다.

P ; 부모노드 인덱스 

C1 , C2 ; 자식노드 인덱스라 하면,

C1 = 2*P 

C2 = 2*P + 1 

으로 배열에 위치한 자식노드로 갈 수 있다.

처음에 구간트리에 정보를 올리기 위해서는 데이터를 모두 다 받아야 한다. 

위 트리에서는 8개의 정보를 가지고 있는 배열을 입력받아 구간트리의 정보를 업데이트 할 수 있다.

3) 세그트리 초기화

input ; 입력으로 데이터 정보를 담고 있는 vector

seg ; 구간트리를 만들 vector

1 2 3 4 5 6 7 8 9 10 11 12 13 14

// 세그트리 초기화   typedef int type; vector<type> input; vector<type> seg;   type mn2(type a, type b){     return (a > b)? b : a; } // 최소값을 return   type init(int node, int s, int e){     if(s == e) return seg[node] = input[start]; // start 와 end 의 위치가 일치하면 input[start] 값을 넣어준다.     return seg[node] = mn2(init(2*node, s, (s+e)/2) , init(2*node+1, (s+e)/2 + 1, e) ); // 다른 노드들의 정보를  } Colored by Color Scripter

cs

리프노드의 경우에는 값을 가져야 하므로 input이 가진 값을 가지게 되고, 

나머지 부모노드들은 구간정보를 가지고 있게 합니다.

4) 세그트리의 정보얻기

구간정보를 얻기위해서 query를 작성합니다.

이때 구간정보를 얻기위해 구간들이 생기는 경우는 총 4개입니다.

위 그림과 같이 

    1) 찾아내야 할 구간과 노드가 가진 정보구간이 겹치지 않는 경우.

    2) 찾아내야 할 구간안에 노드가 가진 정보구간이 포함되는 경우.

    3) 찾아내야 할 구간과 노드가 가진 정보구간이 부분적으로 겹치는 경우.

    4) 찾아내야 할 구간이 노드가 가진 정보구간 안에 포함되는 경우.

이 경우들을 보면

    1) 찾아내야 할 구간과 노드가 가진 정보구간이 겹치지 않는 경우.

        더이상 탐색하는 것이 무의미. query와 상관없는 값을 return 해주면 된다.

    2) 찾아내야 할 구간안에 노드가 가진 정보구간이 포함되는 경우.

        더이상 탐색하는 것이 무의미. 현재 가진 정보 구간의 값을 return 해주면 된다.

    3) 찾아내야 할 구간과 노드가 가진 정보구간이 부분적으로 겹치는 경우.        

    4) 찾아내야 할 구간이 노드가 가진 정보구간 안에 포함되는 경우.

        이 두 경우는 탐색을 계속 진행한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

typedef int type; vector<type> input; vector<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 s, int e, int l, int r){     if(e < l || r < s) return INF; // 1     if(l <= s && e <= r) return seg[node]; // 2     return mn2(query(2*node, s, (s+e)/2 + 1, l, r), query(2*node + 1, (s+e)/2 + 1, e, l, r) ); // 3, 4 } Colored by Color Scripter

cs

위와 같이 코드를 작성할 수 있습니다.

5) 세그트리 노드정보 업데이트

수를 변경할 때는 아래 정보를 이용하여 업데이트 할 수 있다.

• 노드가 담당하는 정보구간 (s-e)
  
• 바뀌는 노드의 위치(index)
• 바뀌는 노드의 값(value)

이때 세그트리를 탐색하며 나타나는 경우는 

1. s와 e를 포함하여 s-e 사이에 노드가 위치한 경우.
2. 1이외에 경우, 포함하지 않는 경우.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

typedef int type; vector<type> input; vector<type> seg; const INF = 987654321;   type mn2(type a, type b){     return (a > b)? b : a; } // 최소값을 return   // s-e : 노드정보구간 // l-r : 찾을정보구간 void update(int node, int s, int e, int index, int value){     if(index < s || e < index) return ; // 2     seg[node] = mn2(seg[node], value); // update     if(s != e){ // 1         update(2*node, s, (s+e)/2, index, value);         update(2*node + 1, (s+e)/2 + 1, e, index, value);             } } Colored by Color Scripter

cs

위와 같이 작성할 수 있다.