세그먼트 트리

주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해 낸 자료구조의 형태가 바로 세그먼트 트리이다.

 

세그먼트 트리의 핵심 이론

세그먼트 트리의 종류는 구간 합 / 최대 & 최소 구하기로 나눌 수 있고,

구현 단계는 (1) 트리 초기화하기, (2) 질의값 구하기 (구간합 또는 최대 & 최소), (3) 데이터 업데이트하기로 나눌 수 있습니다.

 

 

구현 단계

1. 트리 초기화하기

리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다. 트리 배열의 크기를 구하는 방법은 2^k >= N 을 만족하는 k의 최솟값을 구한 후 2^k * 2 를 트리 배열의 크기로 정의하면 된다.

 

예를 들어, N = 8일 때 2^3 >= 8 이므로 k 는 3이 되고 트리 배열의 크기는 2^3 * 2 이므로 16이 된다.

 

리프노드에 원본 데이터를 입력한다. 이 때 리프 노드의 시작 위치를 트리 배열의 인덱스로 구해야 하는데, 구하는 방식은 2^k를 시작 인덱스로 취하면 된다. 예를 들어 k 의 값이 3 이면 start_index = 8 이 된다.

 

예시 데이터 {5, 8, 4, 3, 7, 2, 1, 6}

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
								5	8	4	3	7	2	1	6

 

리프 노드를 제외한 나머지 노드의 값을 채웁니다 (2^k  - 1 부터 1번 쪽으로 채운다). 채워야 하는 인덱스가 x 라고 가정하면 자신의 자식 노드를 이용하여 해당 값을 채울 수 있다. 자식 노드의 인덱스는 이진 트리 형식이기 때문에 2x, 2x + 1 이 된다.

 

[구간 합]

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	36	20	16	13	7	9	7	5	8	4	3	7	2	1	6

• A[n] = A[2n] + A[2n+1]
• 예를 들어, A[7] = A[14] + A[15] = 1 + 6 = 7

 

[최대]

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	8	8	7	8	4	7	6	5	8	4	3	7	2	1	6

• A[n] = Math.max(A[2n] , A[2n+1])
• 예를 들어, A[7] = Math.max(A[14], A[15]) = Math.max(1, 6) = 6

[최소]

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	1	3	1	5	3	2	1	5	8	4	3	7	2	1	6

• A[n] = Math.min(A[2n] , A[2n+1])
• 예를 들어, A[7] = Math.min(A[14], A[15]) = Math.min(1, 6) = 1

 

2. 질의값 구하기

주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경한다. 기존 예제를 기준으로 한 인덱스값과 세그먼트 트리 배열에서의 인덱스값이 다르기 때문에 인덱스를 변경해야 한다.

인덱스 변경 방법은 다음과 같다.

세그먼트 트리 index = 주어진 질의 index + 2^k - 1

 

[질의값 구하는 과정]

1. start_index % 2 == 1 일 때 해당 노드를 선택한다.
2. end_index % 2 == 0일 때 해당 노드를 선택한다.
3. start_index depth 변경 : start_index = ( start_index + 1 ) / 2 연산을 수행한다.
4. end_index depth 변경 : end_index = ( end_index - 1 ) / 2 연산을 수행한다.
5. 위 과정을 반복하다가 end_index < start_index 가 되면 종료한다.

1번, 2번 과정에서 해당 노드를 선택했다는 것은 해당 노드의 부모가 나타내는 범위가 질의 범위를 넘어가기 때문에 해당 노드를 질의값에 영향을 미치는 독립 노드로 선택하고, 해당 노드의 부모 노드는 대상 범위에서 제외한다는 뜻이다.

부모 노드를 대상 범위에서 제거하는 방법은 3번, 4번 과정에서 질의 범위에 해당하는 부모 노드로 이동하기 위해 인덱스 연산을 index / 2 가 아닌 (index + 1) /2, (index - 1) / 2 로 수행하는 것이다.

 

[질의에 해당하는 노드 선택 방법]

• 구간 합 : 선택된 노드를 모두 더한다.
• 최댓값 구하기 : 선택된 노드 중 MAX 값을 선택해 출력한다.
• 최솟값 구하기 : 선택된 노드 중 MIN 값을 선택해 출력한다.