🌲 Segment Tree 1 - Segment Tree란?

원본은 링크를 통해 확인하실 수 있습니다 😃

 

Intro 🚀

스마트폰을 켜서 SNS를 들어가봅시다. 지난 한 달 동안 여러분이 받은 좋아요👍 의 합을 구하고 싶으면 어떻게 하면 될까요?

아마 여러분이 저와 비슷하다면 가장 먼저 '모든 게시물 중 지난 한 달 동안의 게시물에서 받은 좋아요 수를 일일이 더하면 되지 않을까요?' 라고 말씀하실지도 모릅니다.

이 방법을 사용했을 때 게시물의 수가 $n$개이고 특정 기간 동안 받은 좋아요 수의 합을 묻는 query를 $m$개 처리해야 한다면 시간 복잡도는 $O(mn)$입니다. 이 방법도 나쁘지 않지만 더 효율적인 방법은 없을까요?

 

그래서 오늘 우리가 배울 것은 바로 구간의 합/ 차/ 최대값/ 최소값 등을 효율적으로 구하기 위해 쓰이는 자료 구조인

🌴Segment Tree🌴입니다.

 

Segment Tree 🌴

Segment Tree는 각 노드가 구간을 나타내는 binary tree입니다. 각 노드는 나중에 query에서 요구하는 값 즉, 대표값을 저장합니다.

 

그렇다면 segment tree는 어떻게 만들 수 있을까요? 🤔

데이터를 저장하고 있는 길이가 $n$인 배열 arr이 있다고 가정할 때 arr로부터 segment tree를 만드는 방법은 다음과 같습니다.

 

1. Segment tree의 root는 모든 구간 즉, $arr[0 : n - 1]$에서 우리가 관심을 가지는 data를 나타냅니다.

2. Segment tree의 각 leaf node는 하나의 element가 가지는 범위를 나타냅니다. 다시 말해 $arr[0]$부터 $arr[n - 1]$ 까지 모두 leaf node에 위치합니다.

3. internal node는 자식 노드 결과들을 종합한 결과를 나타냅니다. 다시 말해 노드의 대표값이 최대값이라면 internal node는 자식 노드들 중 최대값을 자신의 값으로 가집니다.

4. 각 자녀 노드들은 부모 노드가 나타내는 범위의 대략적으로 절반을 나타냅니다.

5. $n$개의 element를 나타내기 위한 segment tree는 편하게 $4n$의 크기로 나타낼 수 있습니다. (자세한 설명은 링크 걸린 Stack overflow를 확인해주세요.)

6. Segment tree의 root의 index가 1일 때 한 노드의 index가 $i$ 라면 자식 노드들의 index는 왼쪽, 오른쪽 각각 $(2i), (2i + 1)$입니다. (root의 index가 0일때는 어떻게 될까요? 여러분께서 한 번 해결해보세요! 👨‍🏫)

지금부터는 본격적으로 segment tree를 build하고 update하는 방법, query를 구하는 방법에 대해 알려드릴 건데 이해를 돕기 위해 다음과 같은 대표값이 구간에서의 합인 segment tree를 예로 들겠습니다.

 

Build

segment tree는 앞서 언급한 몇 가지 성질과 recursion만 이용하면 직관적이고 쉽게 만들 수 있습니다. segment tree를 recursive하게 만들 때는 bottom up 방식으로 만들어집니다. 다음은 segment tree를 build하는 코드입니다.

 

 

	public void build(long[] tree, long[] arr, int lo, int hi, int idx) {
	if(lo == hi) { // leaf node에 값을 저장합니다.
	tree[idx] = arr[lo];
	return;
	}
	int mid = lo + (hi - lo) / 2;
	build(tree, arr, lo, mid, 2 * idx); // left child
	build(tree, arr, mid + 1, hi, 2 * idx + 1); // right child
	tree[idx] = tree[2 * idx] + tree[2 * idx + 1]; // merge 합니다.
	}

view raw build.java hosted with ❤ by GitHub

 

 

Update

만약 배열 arr의 2번째 index값을 5로 바꾸면 어떻게 segment tree는 어떻게 바뀔까요?

segment tree의 노드들 중 2번째 index라는 구간을 포함하는 모든 노드들은 수정되어야 할 것입니다.

다음은 arr의 2번째 index값을 5로 바꾸었을때 영향을 받는 노드들을 빨간색 테두리로 표시한 것입니다.

 

 

leaf node가 수정되면 그 노드를 자식으로 갖는 부모 노드, 그리고 그 부모의 부모 노드들 모두 영향을 받습니다.

이걸 보니 Bottom up 방식이 생각나고 Bottom up 방식을 생각하니 우리가 방금 살펴본 build 과정이 생각나지 않으시나요?

만약 그러시다면 여러분께 박수를 보내드리고 싶습니다! 정말 대단하십니다! 👏👏👏

실제로 update를 하는 과정은 build하는 과정과 매우 유사합니다! 다음은 관련 코드입니다.

 

 

	public void update(long[] tree, long target, long value, int lo, int hi, int idx) {
	if(lo == hi) { // leaf node의 값을 update합니다.
	tree[idx] = value;
	return;
	}
	int mid = lo + (hi - lo) / 2;
	if(mid >= target) { // 왼쪽, 오른쪽 자식 중 어디로 가야 target이 있는지 찾습니다.
	update(tree, target, value, lo, mid, 2 * idx);
	}
	else {
	update(tree, target, value, mid + 1, hi, 2 * idx + 1);
	}
	tree[idx] = tree[2 * idx] + tree[2 * idx + 1]; // merge합니다.
	}

view raw Update.java hosted with ❤ by GitHub

 

 

Query

만약 segment tree를 이용해 arr의 2번째부터 4번째 index 값의 합을 구하려면 어떻게 하면 될까요?

segment tree의 노드가 나타내는 범위가 2번째부터 4번째 인덱스에 속하면 그 값을 return해서 더하면 어떨까요?

즉, 다음과 같이 보라색으로 칠한 노드들이 2번째부터 4번째 인덱스에 속하기 때문에 이 값들을 return해서 더하는 겁니다! 😀

 

Divide & Conquer 를 기반으로 한 방식이 정말 아름답지 않나요? ✨✨✨

개인적으로 segment tree의 아름다움은 여기에 있다고 생각합니다!

관련 코드는 다음과 같습니다!

 

 

	public long query(long[] tree, int from, int to, int lo, int hi, int idx) {
	// [from..to] 까지 합을 구하는 query
	if(from > hi || to < lo) return 0; // 구간을 완전히 벗어나는 경우
	if(from <= lo && hi <= to) return tree[idx]; // 구간 안에 정확히 들어오는 경우
	int mid = lo + (hi - lo) / 2;
	return query(tree, from, to, lo, mid, 2 * idx) + query(tree, from, to, mid + 1, hi, 2 * idx + 1); // merge한다.
	}

view raw Query.java hosted with ❤ by GitHub

 

 

Complexity Analysis

맨 처음 segment tree는 구간의 합/ 차/ 최대값/ 최소값 등을 효율적으로 구하기 위해 쓰이는 자료 구조라고 했는데 과연 얼마나 효율적일까요? 시간 복잡도를 통해 알아봅시다!

 

Build

segment tree를 build하는 과정을 살펴봅시다. 원래 데이터의 길이가 $n$이라면 segment tree의 노드는 대략적으로 $2n$개 입니다.

왜냐하면 setment tree의 leaf node에는 원래 데이터의 element들이 들어가기 때문에 leaf node의 개수가 $n$개이고 leaf node의 부모 노드는 $\frac{n}{2}$개 이기 때문에 $n + \frac{n}{2} + \frac{n}{4} + ... + 1 \approx 2n$ 이기 때문입니다.

그래서 segment tree를 build하기 위해서는 약 $2n$개의 노드를 모두 방문해야 하기 때문에 시간 복잡도는 $O(n)$입니다!

 

Update

update하는 과정은 보시면 아시다시피 왼쪽, 오른쪽 자식 노드 중 update할 노드가 있는 쪽으로 이동합니다.

잘 생각해보면 우린 이것이 binary search와 유사하다는 것을 알 수 있습니다. 그래서 binary search와 마찬가지로 update 과정도 시간 복잡도가 $O(\log{N})$ 입니다.

 

Query

query를 구하는 과정은 얼마나 걸릴까요?

미리 말씀드리면 query를 구하는 과정의 시간 복잡도가 $O(log{N})$ 입니다. 그 이유는 다음과 같습니다.

query를 구하기 위해서는 query에서 요구하는 구간에 정확히 일치하는 노드들을 DFS를 통해 찾아야 합니다.

최악의 경우 segment tree의 leaf node까지 방문해야 하는데 이는 segment tree의 높이인 $log{N}$ 과 동일합니다. 따라서 query를 구하는 과정의 시간 복잡도는 $O(log{N})$ 입니다!

 

Let's do PS 😆

Segment Tree가 잘 이해되셨나요?

그렇다면 함께 BOJ 2042번 구간 합 구하기 1을 풀어봅시다!

 

도움이 필요하실 때 참고해주세요!

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_2042 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inputs = br.readLine().split(" ");
		int N = Integer.parseInt(inputs[0]);
		int M = Integer.parseInt(inputs[1]);
		int K = Integer.parseInt(inputs[2]);
		
		long[] arr = new long[N + 1];
		long[] tree = new long[4 * N];
		
		for(int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		// build
		build(tree, arr, 1, N, 1);
		
		for(int i = 0; i < M + K; i++) {
			inputs = br.readLine().split(" ");
			int a = Integer.parseInt(inputs[0]);
			long b = (long) Double.parseDouble(inputs[1]);
			long c = (long) Double.parseDouble(inputs[2]);
			
			switch(a) {
			case 1 :
				//update
				update(tree, b, c, 1, N, 1);
				break;
				
			case 2 : 
				// query
				System.out.println(query(tree, (int) b, (int) c, 1, N, 1));
				break;
			}
		}
	}
	
	public static void build(long[] tree, long[] arr, int lo, int hi, int idx) {
		if(lo == hi) {
			tree[idx] = arr[lo];
			return;
		}
		int mid = lo + (hi - lo) / 2;
		build(tree, arr, lo, mid, 2 * idx);
		build(tree, arr, mid + 1, hi, 2 * idx + 1);
		tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
	}
	
	public static void update(long[] tree, long target, long value, int lo, int hi, int idx) {
		if(lo == hi) {
			tree[idx] = value;
			return;
		}
		
		int mid = lo + (hi - lo) / 2;
		
		if(mid >= target) {
			update(tree, target, value, lo, mid, 2 * idx);
		}
		else {
			update(tree, target, value, mid + 1, hi, 2 * idx + 1);
		}
		
		tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
	}
	
	public static long query(long[] tree, int from, int to, int lo, int hi, int idx) {
		if(from > hi || to < lo) return 0;
		
		if(from <= lo && hi <= to) return tree[idx];
		
		int mid = lo + (hi - lo) / 2;
		
		return query(tree, from, to, lo, mid, 2 * idx) + query(tree, from, to, mid + 1, hi, 2 * idx + 1);
	}

}

 

Further Thinking 🤔

만약 특정 인덱스가 아니라 특정 구간을 update한다면 어떻게 될까요?

물론 우리가 앞서 작성한 코드를 이용해도 됩니다. 하지만 그럴 경우 반복적으로 방문하는 노드가 생길 수 있습니다.

 

arr의 1번째부터 2번째 인덱스의 값을 1씩 증가한다고 가정해봅시다.

1번째 인덱스를 update할 때는 1 → 2 → 4 → 9 순서로 노드를 방문해야 합니다.

 

 

 

2번째 인덱스를 update할 때는 1 → 2→ 5 순서로 방문해야 합니다.

 

 

이때 우리는 1, 2번 노드는 두 번 방문한다는 것을 확인할 수 있습니다. 이것은 어떤 레벨에서는 다른 leaf nodef로 '전달'되는 변화들이 서로 만나기 때문입니다. update되는 query가 정말 많은 경우 우리는 update하기 위해 많은 시간을 허비할 수 있습니다.

 

그렇다면 어떻게 하면 이 문제를 해결할 수 있을까요? 답은 다음 시간에 배울 'Lazy propagation'에 있습니다.

그럼 다음 시간에 뵙겠습니다. 감사합니다 🤓

 

참고

https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/

https://bowbowbow.tistory.com/4

https://medium.com/@sivagiri/dissecting-into-segment-trees-ee603a4740d3

https://stackoverflow.com/questions/28470692/how-is-the-memory-of-the-array-of-segment-tree-2-2-ceillogn-1

https://en.wikipedia.org/wiki/Segment_tree