Segment Tree (구간 트리) ---- (작성중,,,,,)

Segment Tree (구간 트리)는 일차원 배열에서 각각의 구간을 특정 기준으로 질의를 던지고 빠르게 답을 구할 수 있는 알고리즘이다.

# Segment Tree

- 이진 트리를 통해 표현 (대부분 full binary tree)

- 각 노드에는 구간에 대한 정보가 저장이 되어있는 트리

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

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

# Segment Tree 유형 문제

- 하나의 (또는 연속된 구간) 값이 매번 변경되는 데이터의 구간합

- 하나의 값이 매번 변경되는 데이터의 최소값

- 하나의 값이 매번 변경되는 데이터의 최대값

- 하나의 값이 빈번히 변경되는 데이터의, 구간 정렬 값

# Segment Tree를 사용하는 이유?

배열 arr에 1,2,3,4,5가 있다고 하자.

arr[1]+arr[2]+arr[3]=9를 구하려면 O(N)이 걸린다.

arr[2]를 10으로 바꾸고 다시 arr[1]+arr[2]+arr[3]를 구해야한다면,

값을 바꾸는데 O(1), 구간의 합을 구하는데 O(N)이 걸린다.

M번 실행하게 되면 O(MN+M)의 시간이 걸린다.

Segment Tree를 사용하면,

값을 바꾸는 과정: O(lgN)

구간의 합을 구하는 과정: O(lgN)

M번 실행 O(MlgN + MlgN) -> O(MlgN)의 시간이 걸린다.

M = 100, N = 2^20이라고 가정하면

O(MN)에서는 100*2^20 = 10,000,000(대략)

O(MlgN)에서는 100*20 = 2,000으로 데이터와 반복수행이 잦아질수록 시간 복잡도 차이가 기하급수적으로 커진다.

※ 그림 추가 (세그먼트 트리 모양)

# Segment Tree의 전체 크기 구하기

N = 12일 때의 세그먼트 트리의 전체 크기(배열 사이즈 정하기)를 구하기 위해서는 

2^k로 12보다 바로 큰 값을 만들 수 있는 k를 찾아야한다. 

즉, k는 4이다.

그리고 난 뒤 2^k를 하면 16이 되고 16에 *2를 하면 우리가 원하는 세그먼트 트리의 크기를 구할 수 있다. 

이 과정이 귀찮다면 그냥 N * 4를하면(여기서는 48이 세그먼트 트리 크기가 될 것이다.)

메모리는 조금 더 먹지만, 편리하게 이용할 수 있다.

포인터로 동적할당을 통한 트리가 아닌 배열로 트리를 만들고 있다.

그 이유는 세그먼트 트리는 full binary tree에 가깝기에 배열에 모든 값들이 꽉꽉차서 올 가능성이 매우 높기때문에 포인터보다는 배열을 이용하게 된다.

# 초기화

구간의 합 또는 최대 그리고 최소값이든 특정 기준에 따라 구간의 값을 지정해주기 위해 트리를 만드는 과정이다.

# 질의처리

주어진 구간 트리에서 원하는 구간의 값을 물어볼때 답을 얻는 과정이다.

# 업데이트

일차원 배열의 값이 변경되는 경우이다.

배열의 특정 index의 값이 변경되면 구간 트리의 값도 변경된다.

하지만 변화의 차이 값을 가지고 루트부터 탐색하면 O(logN)으로 갱신이 가능하다.

# 관련 문제

[BOJ]2042번 구간 합 구하기

[BOJ]2357번 최대값,최소값

# 유투브 영상

https://www.youtube.com/watch?v=e6xnetirNN0&list=PLQ9c2GXvqNKyqrihVgiDJ0upU0pGyqUJy&index=5

# 참고 사이트

https://www.acmicpc.net/blog/view/9

https://www.crocus.co.kr/648

https://meylady.tistory.com/38

https://wondy1128.tistory.com/150

https://jin1ib.tistory.com/116