segment tree

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

큰 범위에선 인덱스 트리라고 불린다.

구간 합은 합 배열을 이용해서 쉽게 구할 수 있다. 그런데도 세그먼트 트리를 사용하게 된 이유는, 데이터의 업데이트때문이다. 합 배열을 사용할 경우, 일부 데이터가 수정되었을 때 합 배열을 수정하는 시간이 오래 걸린다. 

데이터의 업데이트가 빈번하게 이뤄질 경우, 합배열보단 세그먼트 트리를 사용한다. 최대 log_2(N)만큼만 업데이트가 일어난다.

🔰구현

세그먼트 트리 종류는 구간 합, 최대 및 최소 구하기로 나눌 수 있다.

1. 트리 초기화: 리프 노드가 원본 데이터인 이진 트리(1차원 배열)로 초기화한다.
   1. 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다. 트리 배열의 크기는 2^k ≥ N을 만족하는 k의 최솟값을 구하고, 2^(k + 1)을 트리 배열의 크기로 정의하면 된다.
   2. 리프 노드에 원본 데이터를 입력한다. 이진 트리의 2^k 인덱스부터 차례로 채운다.
   3. 리프 노드를 제외한 나머지 노드의 값을 채운다. 즉, 2^k - 1 인덱스부터 1 인덱스 방향으로 채운다. 부모 노드의 인덱스를 K라 했을 때, 자식 노드의 인덱스(2K, 2K + 1)에 저장된 값을 사용한다.
      • 구간합인 경우, 자식 노드에 저장된 값의 합을 부모 노드에 저장한다.
      • 최대 및 최소 구하기인 경우, 자식 노드에 저장된 값을 비교해서 최대 및 최소 값을 부모 노드에 저장한다.
2. 질의값 구하기: 구하고자 하는 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경한다.
   • 세그먼트 트리에서의 인덱스 = 구하고자 하는 인덱스 + 2^k - 1
   • 시작 인덱스와 끝 인덱스를 변환했다면, 질의값을 구하는 과정은 다음과 같다.
     1. 부모 노드가 필요 없는 노드인 경우만 선택하고, 부모 레벨로 이동한다.
        1. (시작 인덱스) % 2 == 1이면(오른쪽 자식 노드라는 의미) 노드를 선택한다.
        2. (끝 인덱스) % 2 == 0이면(왼쪽 자식 노드라는 의미) 노드를 선택한다.
        3. 시작 인덱스의 depth를 변경한다. (시작 인덱스) = (시작 인덱스 + 1) / 2 -> 시작 노드의 오른쪽 노드의 부모 노드의 인덱스를 의미한다.
        4. 끝 인덱스의 depth를 변경한다. (끝 인덱스) = (시작 인덱스 - 1) / 2 -> 끝 노드의 왼쪽 노드의 부모 노드의 인덱스를 의미한다.
     2. 위 과정을 반복하다가 (끝 인덱스) < (시작 인덱스)가 되면 종료한다.
   • 질의에 해당하는 노드 선택 방법
     • 구간 합: 선택한 노드의 값을 모두 더한다.
     • 최댓값 구하기: 선택된 노드 중 최댓값을 선택해 출력한다.
     • 최솟값 구하기: 선택된 노드 중 최솟값을 선택해 출력한다.
3. 데이터 업데이트하기: 부모 노드로 이동하면서 업데이트한다는 것은 동일하지만, 어떤 값으로 업데이트할 것인지는 트리 타입별로 조금 다르다.
   • (자식 노드 인덱스) // 2를 이용해 부모 노드로 이동한다.
   • 구간 합: 원래 데이터와 변경 데이터의 차이만큼 부모 노드에 반영한다.
   • 최대 및 최소 구하기: 변경 데이터와 또 다른 자식 노드의 값을 비교해 적절한 값으로 업데이트한다. 부모 노드 인덱스를 따라 가며, 업데이트가 일어나지 않으면 종료한다.