세그먼트 트리 (Segment Tree)

세그먼트 트리 (Segment Tree)

세그먼트 트리란?

구간에 대한 정보를 저장함.

특정 구간의 최적화된 답을 구하는 문제에 사용.

부분 구간의 최적 답들 중에서 최적 답을 구할 수 있음.

<시간 복잡도>

자료 저장: O(n log n)

특정 구간 최적해 검색: O(log n + k)

SUM TREE를 배열 기반으로 짜면, 노드마다 자식 노드의 TOTAL SUM 정보를 저장하게 됨.

구현

TREE 초기 자료 구성:

원본 데이터를 인자로 받아서 LEAF NODE를 찾아 하나씩 저장하는 프로세스.

배열의 크기 잡는 법:

예를 들어 데이터가 1000개라면, 1000 < 2^10 이므로, TREE LEVEL은 N = 11개가 만들어져야 함.

TREE[1<< N] 로 배열 크기를 잡아주자.

이렇게 넉넉하게 잡아주는 이유는, 배열에서 가장 작은 index의 부모 노드의 자식 노드가 생기면, TREE LEVEL이 한 개 더 늘어나기 때문임.

 

PARENT NODE = NODE

LEFT CHILD NODE = NODE * 2

RIGHT CHILD NODE = NODE * 2 + 1

Sample Code

//SEGMENT TREE
void Update_New_Data(int node, int s, int e, int idx, int data)
{
    int m;
    
    if (s == e)
    {
        tree[node] = data;
        return;
    }
 
    m = (s + e) / 2;
    if (idx <= m) Update_New_Data(node * 2, s, m, idx, data);
    else Update_New_Data(node * 2 + 1, m + 1, e, idx, data);
 
    tree[node] = tree[node * 2] * tree[node * 2 + 1];
}
 
int Query(int node, int s, int e, int qs, int qe)
{
    int m, left, right;
 
    if (qs <= s && e <= qe) return tree[node];
    else if (qs > e || s > qe)  return 0;
 
    m = (s + e);
    left = Query(node * 2, s, m, qs, qe);
    right = Query(node * 2 + 1, m + 1, e, qs, qe);
 
    return left * right;
}
 
void Update_Add(int node, int s, int e, int us, int ue, int add)
{
    int m;
 
    if (s == e)
    {
        if (us <= s && e <= ue) tree[node] += add;
        return;
    }
    else if (us > e || s > ue) return;
 
    m = (s + e) / 2;
    Update_Add(node * 2, s, m, us, ue, add);
    Update_Add(node * +1, m + 1, e, us, ue, add);
 
    tree[node] = tree[node * 2] * tree[node * 2 + 1];
 
}
 

Update_New_Data 함수에서 ( s == e ) 일 경우 데이터를 저장 하는 이유:

배열을 m으로 반으로 쪼개면서 검색하다가 마지막 LEAF NODE를 발견했을 때 데이터를 삽입한다는 것.

부모 노드의 정보를 업데이트 함수 마지막에 갱신해주는 과정 필수.

Query 함수로 부분( qs ~ qe )의 정보를 구할 수 있다. 

위 샘플 코드의 트리는 MULTIPLE TREE 라서 노드의 곱을 구하고 있다.

Update_Add 함수는 노드의 정보를 새로운 값으로 업데이트하는 함수.

LEAF NODE에 도달했을 때, 정보를 바꾸기 원하는 구간( us ~ ue )인지도 확인한 뒤에 업데이트해줘야 한다.

그리고 당연히 부모 노드도 새로운 정보를 바탕으로 업데이트해야 함.

Sample Code 2 (Lazy Propagation 추가)

void Propagate(int node, int s, int e)
{
    if (lazy[node] == 0) return;
 
    //자식 노드에 전달
    if (s != e)
    {
        lazy[node * 2] += lazy[node];
        if (node * 2 + 1 <= LASTNODE) lazy[node * 2 + 1] += lazy[node];
    }
 
 
    //자기 노드 업데이트
    tree[node] += (e - s + 1)*lazy[node];
    lazy[node] = 0;
}
 
 
void Update_Add_Lazy(int node, int s, int e, int us, int ue, int add)
{
    int m;
 
    Propagate(node, s, e);
 
    if (us <= s && ue >= e)
    {
        lazy[node] += add;
        Propagate(node, s, e);
        return;
    }
    else if (us > e || s > ue) return;
 
    m = (s + e) / 2;
    Update_Add_Lazy(node * 2, s, m, us, ue, add);
    Update_Add_Lazy(node * 2 + 1, m + 1, e, us, ue, add);
 
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
 

LAZY PROPAGATION

• 이건 자료를 업데이트할 때 최악의 경우 O(N log N) 복잡도가 될 수 있는데, 이를 방지하고 시간 복잡도를 O(log N) 으로 고정시키기 위한 알고리즘이다.

• UPDATE 를 할 때, 당장 필요한 변경만 진행하고 자식 노드에 대해서는 다음에 해당 노드를 재탐색시 변경하는 전략임.