Segment Tree

Segment Tree

세그먼트 트리란?

• 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조
  • 기존 구간합은 데이터가 자주 업데이트 되는 경우 성능이 좋지 않음
• 인덱스 트리의 하나

언제 쓸까?

• 구간합 구하는데, 업데이트가 발생할 때
• 업데이트 발생하지 않으면 굳이 세그먼트 트리로 풀 필요가 없음

구현

• 이진트리로 만듦
  • 이진트리 : 자식이 두 개
• 리프노드만 원본 데이터가 들어갈 것

1. 트리 초기화

• 트리의 크기 구하기
  • 인덱스 트리를 1차원 배열로 만들고 끝에서부터 채워넣기 위해
  • ⭐️ 트리의 크기 : 2^k * 2
    • 데이터의 개수가 N일 때, k는 2^k >= N을 만족하는 k의 최솟값
    • 0번째 인덱스는 사용하지 않음 (0번째를 포함한 크기를 구한 것)
• 리프 노드에 값들을 채워줌
  • 시작 노드 : 2^k
• 리프 노드 외의 값 채워주기
  • 채워야 하는 인덱스 N일 때, 자식 노드는 2N, 2N + 1 임을 이용

  ex. 구간합을 구할 때 tree[N] = tree[2N] + tree[2N + 1]

예제

• 샘플 : {5, 8, 4, 3, 7, 2, 1, 6}
• 트리의 크기 : k = 3 이므로 2^3 * 2 = 16
• 리프 노드에 값 채우기
  • 시작 인덱스 : 8 (= 2^3)

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

• 리프 노드 외의 노드 값 채우기

  ex. 구간합

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

2. 질의값 구하기

1) 질의 인덱스를 세그먼트 트리 인덱스로 변경

• 세그먼트 트리 index = 질의 index + 2^k - 1

2) 질의값 구하기

(1) mod 연산으로 노드 선택 여부 결정

• start_index % 2 == 1 일 때 해당 노드를 선택
• end_index % 2 == 0 일 때 해당 노드를 선택

(2) start_index, end_index가 부모를 타고 올라가며 depth 변경

• start_index depth 변경 : start_index = (start_index + 1) / 2
• end_index depth 변경 : end_index = (end_index - 1) / 2

(3) end_index < start_index 일 때까지 (1) ~ (2)를 반복

💡 start_index, end_index depth 이동

• start_index % 2 == 1 : start_index가 부모 노드의 오른쪽 노드

  -> 이 부모노드는 사용하면 안됨! (왼쪽 노드까지 포함되어 있으므로)

  start_index 노드는 따로 저장했다가 사용

• start_index 노드를 따로 저장한 경우 start_index의 부모 노드의 다음 노드로 이동하기 위해 (start_index + 1) / 2 번째로 이동
• end_index도 마찬가지

예제

• 2 ~ 6번째의 구간합 (1번째가 시작)

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

1) 세그먼트 트리의 인덱스로 변경

• start_index = 2 + 7 = 9
• end_index = 6 + 7 = 13

2) 부모 노드로 이동

• 1회 이동

    start_index % 2 = 9 % 2 = 1 // 노드 선택
    end_index % 2 = 13 % 2 = 1 // 노드 미선택
    start_index = (start_index + 1) / 2 = 10 / 2 = 5
    end_index = (end_index - 1) / 2 = 12 / 2 = 6
  

• 2회 이동

    start_index % 2 = 5 % 2 = 1 // 노드 선택
    end_index % 2 = 6 % 2 = 0 // 노드 선택
    start_index = (start_index + 1) / 2 = 6 / 2 = 3
    end_index = (end_index - 1) / 2 = 5 / 2 = 2
    // end_index < start_index 이므로 종료
  

• 선택된 노드의 합을 구함

    sum = tree[9] + tree[5] + tree[6]
  

3. 데이터 업데이트

• 부모로 올라가면서 값을 업데이트

관련 문제

• BOJ 구간 합 구하기

---

참고 자료

• 알고리즘 코딩테스트 핵심이론 강의 - 세그먼트트리(인덱스 트리)