[자료 구조] 세그먼트 트리

 

2357번: 최솟값과 최댓값

백준 2357번 최솟값과 최대값 문제를 풀면서 세그먼트 트리에 대해 접하게 되었다. 

처음에는 DP로 풀어보려고 끙끙대고 있다가 안되길래 분류표를 보니 세그먼트 트리라는 걸 알 수 있었다..

 

새로운 자료구조를 한번 정리해보기로 했당...

 

 

 

세그먼트 트리 (인덱스 트리)?

주어진 데이터의 `구간 합`과 `데이터 업데이트`를 빠르게 수행하기 위해 고안해낸 자료구조 형태

*구간 합과 다른 점은 데이터 업데이트가 빈번하게 일어나도 속력을 유지할 수 있다는 것.

 

세그먼트 트리의 핵심 이론

구간 합, 최대/최소 구하기, 구간 곱으로 종류를 나눌 수 있다... 모든건 구간합에서 도출 가능

 

1. 트리 초기화하기

 세그먼트 트리는 '이진 트리'로 이루어 진다. 세그먼트 트리는 맨 아래 노드(리프 노드)만 원본 데이터 배열이다. 

 

리프 노드의 개수가 데이터의 개수(N)이상이 되도록 트리 배열을 만든다. 즉, 트리 배열의 크기를 구하는 방법은 

2^k >= N을 만족하는 k의 최솟값을 구한 후 2^k*2를 트리 배열의 크기로 정의하면 된다.

*0번 idx는 쓰지 않는다.

8(2^k)번 인덱스 부터 배열의 값을 채운다. 

 

 

 어떤 노드의 번호가 N일 때, 왼쪽 자식의 번호는 2N, 오른쪽 자식 번호는 2N+1이다. 

 

ex)

15/2 = 7
14/2 = 7

A[7] = A[14] + A[15] = 1 + 6

 

=> 구간합이 구해진다. 최댓값, 최솟값도 같은 방식으로 가능하다. 곱도 마찬가지! 

 

 

 

위에서 구한 구간값은 2의 배수 기준으로 구해진다. 그럼 어떻게 홀수 개의 구간 합을 구할 수 있을까?

 

2. 질의값 구하기 

주어진 질의 인덱스를 세그먼트 트리의 리프노드에 해당하는 인덱스로 변경한다.

ex) 1~3의 구간합 = 8~10의 구간합.

질의 인덱스를 세그먼트 트리 인덱스로 변경하는 방법
세그 먼트 트리 index = 주어진 질의 인덱스 + 2^k - 1

질의값 구하는 과정
1. start_idx%2 == 1 일 때, 해당 노드를 선택한다.
2. end_idx %2 == 0 일 때, 해당 노드를 선택한다.
3. start_index depth 변경 : start_index = (start_index + 1)/2 연산을 실행한다.
4. end_index depth 변경 : end _index = (end_index -1) / 2 연산을 실행한다.
5. 1~4를 반복하다 end_index < start_index가 되면 종료한다.

 

1~2 : 해당 노드를 선택한다는 것은 부모가 나타내는 범위가 질의 범위와 어긋난다는 것이다. 해당 노드는 독립노드로 따로 선택한다. 즉, 해당 노드의 부모 노드는 대상 범위에서 제외한다. 

*1의 경우는 이진 트리 리프 노드 중에 오른쪽을 뜻한다 => 해당 부모 노드는 사용할 수 없다. 

*2의 경우는 왼쪽 => 동일

3~4 : 질의 범위에 해당하는 부모 노드로 이동하기 위해 인덱스 연산을 index/2가 아닌, (index+1)/2, (index-1)/2로 수행한다.

 

start_index %2 = 1 이기 때문에, 9%2 == 1, 해당 노드는 독립 노드로 따로 빼준다. [9] : 8

start_index = (start_index + 1)/2의 계산 방식을 사용하면, 자연스럽게 오른쪽 자식일 경우는 제하고, 왼쪽 자식일 경우에는 (8+1/2 = 4)로 원하는 부모노드를 선택할 수 있다.

end_index = (end_index - 1)/2 = 12/2 = 6도 마찬가지.

 

end_index < start_index이므로 종료하고 값을 구한다. 2~6번 구간 합의 값은 선택된 노드의 합인 8 + 9 + 7 = 24가 됨.

 

3. 데이터 업데이트하기

변경되는 상위 노드만 바꿔주면됨. 

 

 

---

세그먼트트리 단계
1. 트리 초기화 하기 >
    1) 트리의 크기 정하기 : 2^k >= N
    2) 부모 노드값 채우기 : (i+2^k-1)
2. 질의값 구하기 >
    1) 질의 index를 트리에 맞게 변경
    2) start % 2 = 1 선택,
        end % 2 = 0 선택
    3) start > end 일 때 그만
3. 업데이트 > 트리 특성을 살려서 이진트리가 부모 노드로 갈 때 n/2
    1) 부모노드만 계속.. 업데이트......    

 

구간 합을 구하는 문제다.

1) 합만 구한다 => 인덱스 트리 없이 pre_fix로 가능

2) 변경이 있다. => 세그먼트 트리(인덱스 트리)

 

 

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

세그먼트 트리

https://www.youtube.com/watch?v=1d9sqmuLy-o&t=38