섹션 3. 코딩테스트 [실전편] - 09. 트리 - (3) 세그먼트 트리

⬛ 09-4. 세그먼트 트리

🟦 세그먼트 트리

• 주어진 데이터들의 **‘구간 합’과 ‘데이터 업데이트’**를 빠르게 수행하기 위해 고안해낸 자료구조
• 세그먼트 트리의 종류 : 1) 구간합, 2) 최대/최소 구하기
• 구현 단계 : (1) 트리 초기화 하기 (2) 질의값(요구사항) 구하기 (3) 데이터 업데이트

🟧 세그먼트 트리의 구현 단계

1) 트리 초기화 하기

(1) 리프 노드의 개수가 데이터 개수 N 이상이 되도록 2^k ≥ N을 만족하는 k의 최솟값 구한 뒤

2^k * 2를 트리 배열의 크기로 정의

ex) 샘플 데이터 = {5, 8, 4, 3, 7, 2, 1, 6} : N = 8
2^3 = 8
따라서 배열크기는  2^3 X 2 = 16 크기로 정의 

(2) 리프 노드에 원본 데이터를 입력한다.

• 이때 리프 노드가 시작하는 인덱스는 2^k 인덱스부터 취하면 된다.

위의 샘플예시에서 k=3 이었다. 단말노드 시작 인덱스는 2^k = 2^3 = 8 이 된다.
그러므로 전체 크기가 int[] =new int[16] 으로 정의한 상태에서 
인덱스8부터 단말노드라고 생각하고 원본 샘플 데이터 N개를 차례로 저장해준다. 

(3) 이제 리프 노드 제외한 나머지 노드값을 채울 건데,

트리의 특성상 자식 노드들을 이용해서 부모노드를 유추할 수 있기 때문에

각각의 트리 케이스별로 적절하게 계산해준다.

(→ 이렇게 미리 트리 구현해두면 빠른 시간복잡도로 원하는 질의 데이터를 구할 수 있다.)

ex) 부모노드를 N이라고 했을 때, 자식 노드는 2N, 2N+1이다.
1) 구간 합 : A[N] = A[2N] + A[2N+1] 
2) 최대 : A[N] = Math.max(A[2N], A[2N+1])
3) 최소 : A[N] = Math.min(A[2N], A[2N+1])

2) 질의값 구하기

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

세그먼트 트리 인덱스 = 주어진 질의 인덱스 + 2^k -1;

예를 들어, 여기서 k=3 이었기 때문에 주어진 질의 인덱스 + 2^3 -1 이 된다. 

• 질의에서의 시작, 종료 인덱스에 관해서는 부모 노드로 이동하면서 주어진 질의에 해당하는 값을 다음의 과정과 같이 구한다.

⬛ 질의값 구하는 과정

(1) start_idx % 2 == 1일 때 해당 노드 선택

(2) end_idx 2 == 0 일 때 해당 노드 선택

(3) (1~2) 에서 노드 선택 X ⇒ start_idx = (start_idx+1) /2 연산 수행

(4) (1~1) 에서 노드 선택 X ⇒ end_idx = (end_idx-1)/2 연산 수행

(5) 앞의 과정들을 반복하다가 end_idx < start_idx 되면 종료

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

• 1. 구간 합 : 선택된 노드들 모두 더함
• 1. 최댓값 : 선택된 노드들 중 Max값 선택
• 1. 최솟값 : 선택된 노드들 중 Min값 선택

3) 데이터 업데이트

• 자신의 부모 노드로 이동하면서 업데이트한다는 것은 동일하지만 ‘어떤 값’으로 업데이트할 것인지는 트리의 타입별로 다르다.

⬛ 트리 종류별 데이터 업데이트

1. 구간 합 : 기존 데이터와 변경 데이터의 차이만큼 부모노드로 올라가면서 변경
2. 최댓값 찾기 : 변경 데이터와 자신과 같은 부모 갖는 다른 자식 노드 비교하여 더 큰 값으로 변경
3. 최솟값 찾기 : 변경 데이터와 자신과 같은 부모 갖는 다른 자식 노드 비교하여 더 작은 값으로 변경