[자료구조] 세그먼트 트리(Segment Tree)

특정 구간에 있는 N개의 수들의 합을 구하는 경우 O(N)의 시간 복잡도가 생긴다.

얼핏 보면 여기서 더 좋은 방법이 있을까? 싶지만, 있다. (이번에 알게 되었음..)

 

시간을 절약하기 위해서는 특정 구간을 미리 알고 있으면 좋은데, 이때 세그먼트 트리를 사용한다.

 

※예를들어 0~4번째 수의 합과 5~9번째 수의 합을 알고 있다고 가정하자.

 

4~9의 합을 구하려면 원래는 6개의 숫자를 모두 꺼내서 더하는 6번의 작업을 거쳐야 하는데,

6개 더하기

 

해당 방법을 사용하면 4번째 숫자와 5~8번째 합을 꺼내서 더하는 작업 2번만 수행하면 된다.

2개 더하기

 

 

세그먼트 트리 (Segment Tree)

• 일정 간격에 대한 정보를 저장하는데 사용하는 트리 데이터 구조
• 특정 구간의 합을 구하는 작업시 유용하게 사용됨

 

세그먼트 트리 형태

1. Full Binary Tree(정 이진 트리) - Leaf 노드 제외 모든 트리가 2개의 자식 노드 가짐

※ 정 이진 트리 : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

2. Leaf 노드는 해당 위치의 수 (단독 값O 구간 합X) - start == end 인 경우

3. 노드의 왼쪽 자식은 node * 2이며, 오른쪽 자식은 node * 2 + 1임

4. 구간 [start, end]의 왼쪽은 [start, (start+end)/2]이며 오른쪽은 [(start+end)/2+1, end]임

 

구현 1. 트리에 값 등록

void init(long[] a, long[] tree, int node, int start, int end) {
    if (start == end) {
        tree[node] = a[start];
    } else {
        init(a, tree, node*2, start, (start+end)/2);
        init(a, tree, node*2+1, (start+end)/2+1, end);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
}

- a[] : 값이 들어있는 배열

- tree[] : 트리 구조로 만든 배열

 

구현 2. 트리 값 변경

    static void update(long[] a, long[] tree, int node, int start, int end, int index, long val) {
        if (index < start || index > end) {
            return;
        }
        if (start == end) {
            a[index] = val;
            tree[node] = val;
            return;
        }
        update(a, tree,node*2, start, (start+end)/2, index, val);
        update(a, tree,node*2+1, (start+end)/2+1, end, index, val);
        tree[node] = tree[node*2] + tree[node*2+1];
    }

- 해당 node가 속해있는 구간 모두 갱신

 

구현 3. 구간 합 구하기

    static long query(long[] tree, int node, int start, int end, int left, int right) {
        if (left > end || right < start) {
            return 0;
        }
        if (left <= start && end <= right) {
            return tree[node];
        }
        long lsum = query(tree, node*2, start, (start+end)/2, left, right);
        long rsum = query(tree, node*2+1, (start+end)/2+1, end, left, right);
        return lsum+rsum;
    }

- 구간 쪼개서 합 구하기

 

백준 자료구조 설명을 보면 더 자세히 알 수 있음

https://book.acmicpc.net/ds/segment-tree

세그먼트 트리

 

 

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

 

문제도 풀기.!