[트리] 세그먼트 트리 (인덱스 트리)

✔ 세그먼트 트리

세그먼트 트리란?

• 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태
• 더 큰 범위는 인덱스 트리라고 불림
• 코딩 테스트에서
  구간 합만 수행할 경우 합 배열과 구간 합 사용,
  구간 합과 데이터 업데이트를 둘 다 수행할 경우 세그먼트 트리 사용
• 세그먼트 트리의 종류는 구간 합, 최대 구하기, 최소 구하기로 나누어짐
• 구현 단계는 트리 초기화하기, 질의값 구하기 (구간 합, 최대, 최소), 데이터 업데이트하기로 나누어짐

세그먼트 트리 과정

• 트리 초기화하기

1. 리프 노드의 개수가 데이터의 개수 이상이 되도록 트리 배열을 만듦
   • 2^k ≥ N을 만족하는 k의 최솟값을 구한 후 2^k * 2를 트리 배열의 크기로 정의
2.  리프 노드에 원본 데이터를 입력
   • 리프 노드의 시작 위치를 트리 배열의 인덱스인 2^k로 정의
3.  리프 노드를 제외한 나머지 노드의 값을 자신의 자식 노드를 이용해 채움 (2^k - 1부터 1번 쪽으로 채움)
   • 자식 노드의 인덱스는 2N, 2N + 1
   • 각 케이스별로 적절하게 계산함
   • 구간 합 : A[N] = A[2N] + A[2N + 1]
   • 최대 : Math.max(A[2], A[2N + 1])
   • 최소 : Math.min(A[2], A[2N + 1])

• 질의값 구하기

1. 주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경
   • 세그먼트 트리 index = 주어진 질의 index * 2^k - 1
2. 질의에서의 시작 인덱스와 종료 인덱스에 관해 부모 노드로 이동하면서 주어진 질의에 해당하는 노드를 구함
   • start_index % 2 == 1일 때 해당 노드를 선택함
     
   • end_index % 2 == 0일 때 해당 노드를 선택함
   • start_index = (start_index + 1) / 2 연산을 실행함 (부모 노드로 이동)
   • end_index = (end_index - 1) / 2 연산을 실행함 (부모 노드로 이동)
   • 위를 반복하다가 end_index < start_index가 되면 종료함
   • 위 과정을 통해 해당 노드의 부모가 나타내는 범위가 질의 범위를 넘어갈 때
     해당 노드를 질의값에 영향을 미치는 독립 노드로 선택하고, 해당 노드의 부모 노드는 대상 범위에서 제외할 수 있음
3. 선택된 노드들에 관해 질의값을 구함
   • 구간 합 : 선택된 노드들을 모두 구함
   • 최대 : 선택된 노드들 중 MAX 값을 선택해 출력
   • 최소 : 선택된 노드들 중 MIN 값을 선택해 출력

• 데이터 업데이트하기

1. 자신의 부모 노드로 이동하면서 업데이트함
2. 어떤 값으로 업데이트할 것인지에 관해서는 트리 타입별로 다름
   • 구간 합 : 원래 데이터와 변경 데이터의 차이만큼 부모 노드로 올라가면서 변경
   • 최대 : 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 더 큰 값으로 업데이트
     이때 업데이트가 일어나지 않으면 종료
   • 최소 : 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 더 작은 값으로 업데이트
     이때 업데이트가 일어나지 않으면 종료

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn