[자료구조] 세그먼트 트리, 쉽게 이해하기

분류    자료구조 > 트리 > 세그먼트 트리

 

개요

배열에 우리가 원하는 데이터들이 저장했다고 가정해보자.

이때 특정 배열 구간 (1~n)에 대해서, 합을 알고 싶다면,

직관적으로 생각해보면, 특정 구간에 대해서, 반복문으로 (1~n)까지 합해서, 결과를 보여줘야할 것이다.

 

하지만, 특정 구간 연산결과 값을 빈번하게 알아내야 한다면?? 

예를 들어, 1~n까지, 2~n까지, 4~(n-4)까지 합 3가지를 알고 싶다. 그럼 3번 반복문이나 돌려야한다..

 

더 효율적인 방법은 없을까?, 일종의 구간의 연산 결과를 저장하는 자료구조를 이용하면 어떨까?

예를 들어, 1~n/2 까지 구간 합이 이미 배열에 계산되어 있다면,

그냥 거기서 꺼내서 쓰면 된다.  이것을 가능하게 하는 것이 세그먼트 트리이다.

 

목적

세그먼트 트리의 목적은, 특정 구간에 대해서, 원하는 연산(통계 처리)를 할 때 쓰인다. (예, 구간 합을 구할때 쓰인다.)

의미

- 특정 구간에 대해서, 원하는 연산(통계 처리)를 할 때 쓰인다. (예, 구간 합을 구할때 쓰인다.)

- 세그먼트 트리는, 트리 자료구조의 일종으로, 통계 트리(statistic tree)에 해당한다.

- 또한, 세그먼트 트리는 Leaf 노드를 제외한 노드는 각 노드 구간 혹은, 세그먼트에 대한 연산 결과를 가지고 있다.

 

- 특이한 점은, (1) 원래 데이터를 저장하는 배열이 있고, 그거에 파생된 (2) 세그먼트 트리가 따로 있다는 점.

 

- 세그먼트 트리의 간단한 특징

1) Leaf 노드 : 한 개의 데이터를 갖고 있음.

2) Leaf 노드를 제외한 노드 : 구간의 연산을 가지고 있음.

구간은 아래와 같음.

 

 길이가 7인 A라는 배열에 대해 세그먼트리를 만들어보면,

세그먼트 트리들의 각 노드에 대한 설명 A[x:y]는 x부터 y까지의 합을 말한다.    

 

 

 

 

 

 

 

장점

장점 1. 더빠르다. (시간복잡도 내려감)

반복문 방법:

만약, 길이가 N인 배열에 대해서, 모든 구간 (1~M)의 구간합을 반복문으로 구한다고 해보자.

O(M*N) 의 복잡도를 가진다. 왜냐하면 -> 길이 N인 배열에 대해서, M번을 돌아야하기 때문이다.

 

세그먼트 트리 방법:

하지만, 세그먼트 트리를 이용할 시,

O(M*logN) 의 복잡도를 가진다. 왜냐하면 -> 적어도, 구간 합을 찾으려면, 트리의 깊이 * 상수(횟수) 만큼의 연산이 필요하다. 즉, 트리 깊이는 logN이기 때문에, O(M*logN) 이다

 

단점

단점 1. 메모리를 많이 쓴다. (공간복잡도 올라감)

위의 예제를 보더라도, 데이터의 갯수는 6개 밖에 안되지만, 트리의 길이는 13개인 걸 볼 수 있다.

즉, 구간 합을 저장하기 위한, 추가적인 데이터 저장소가 필요하다.

 

단점 2. 데이터를 교체할 때, 트리도 다 바꾸어주어야함.

 

관련 코드

백준 11659번 예시

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class main {
	static int[] tree = new int[100001 * 4];
	static int[] input = new int[100001];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine()," ");

		int n = Integer.parseInt(stk.nextToken());
		int out = Integer.parseInt(stk.nextToken());
		
		stk = new StringTokenizer(br.readLine()," ");
		for (int i = 1; i <= n; i++) {
			input[i] = Integer.parseInt(stk.nextToken());
		}
		
		build(1, 1, n);
		for (int i = 0; i < 20; i++) {
		}
		
		// << 출력부 >> (테스트하기)
		for (int i = 0; i < out; i++) {
			stk = new StringTokenizer(br.readLine()," ");
			int interval1 = Integer.parseInt(stk.nextToken());
			int interval2 = Integer.parseInt(stk.nextToken());
			System.out.println(query(1, 1, n, interval1, interval2));
		}
	}
	
	public static void build(int node, int start, int end) {
		if (start == end) {
			tree[node] = input[start];
		}
		else {
			int mid = (start + end) / 2;
			// 왼족 child 노드에 대해서 재귀함수 호출
			build(2 * node, start, mid);
			// 오른쪽 child 노드에 대해서 재귀함수 호출
			build(2 * node + 1, mid + 1, end);
			// 내부 노드는 두 개의 child노드의 합
			tree[node] = tree[2*node] + tree[2*node + 1];
		}
	}
	
	// r : interval1
	// l : interval2
	public static int query(int node, int start, int end, int l, int r) {
	    if (r < start || l > end) {
	    	// 범위가 주어진 범위의 밖임. 
	        return 0;
	    }
	    if (l <= start && r >= end) {
	    	// 구하려는 범위가 범위가 주어진 범위 안임, 그렇다면 바로 그값을 리턴해야함.
	        return tree[node];
	    }
	    // 범위가 주어진 범위 내이고, 아직 밑에 자식 노드들이 남았으면, 재귀 수행
	    int mid = (start + end) / 2;
	    int p1 = query(2 * node, start, mid, l, r);
	    int p2 = query(2 * node + 1, mid + 1, end, l, r);
	    return (p1 + p2); // 합의 연산 실행
	}

	// 트리가 업데이트 될 때
	public static void update(int node, int start, int end, int idx, int val) {
	    if(start == end) {
	        // Leaf 노드
	        input[idx] += val;
	        tree[node] += val;
	    }
	    else {
	        int mid = (start + end) / 2;
	        if(start <= idx && idx <= mid) {
	        	// 인덱스가 왼쪽 child일 때, 왼쪽 자식에 대해 재귀 호출
	            update(2 * node, start, mid, idx, val);
	        }
	        else {
	        	// 인덱스가 오른쪽 child일 때, 오른쪽 자식에 대해 재귀 호출
	            update(2 * node+1, mid+1, end, idx, val);
	        }
	        // 내부적인 노드는 자식들의 합을 가짐. 
	        tree[node] = tree[2 * node] + tree[2 * node + 1];
	    }
	}
}

 

입력

5 3
5 4 3 2 1
1 3
2 4
5 5

배열길이 5,  구간합 시도횟수 3

배열 데이터 5, 4, 3, 2, 1

1-3 합은?

2-4 합은?

5-5 합은?

출력

12
9
1

 

관련문제

1. 구간 합 구하기 4 (11659번)

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

11659번: 구간 합 구하기 4

2. 구간 합 구하기 (2042번) https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

 

관련자료/참고자료

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/tutorial/