C++ 세그먼트 트리로 특정 인덱스 값 갱신과 범위별 GCD 조회 쿼리 구현하기

이 튜토리얼에서는 배열의 특정 인덱스 값을 갱신하고, 주어진 범위 내 요소들의 최대 공약수(GCD)를 구하는 쿼리를 처리하는 프로그램을 다룹니다.

정수로 이루어진 배열과 Q개의 쿼리가 제공되며, 각 쿼리는 다음 두 가지 작업 중 하나를 수행해야 합니다:

값 갱신(Update): 특정 인덱스의 값을 새로운 값으로 변경
범위 조회(Query): 지정된 두 인덱스 구간 사이의 최대 공약수(GCD) 계산

접근 방법: 세그먼트 트리(Segment Tree)

매번 배열 전체를 순회하며 GCD를 계산하면 O(n)의 비용이 들어 잦은 조회에 비효율적입니다. 이 문제는 세그먼트 트리 자료구조를 활용하면 효율적으로 해결할 수 있습니다.

세그먼트 트리는 배열을 여러 구간으로 나누어 각 구간의 GCD를 미리 저장해 두는 이진 트리로, 범위 조회와 값 갱신 모두 O(log n) 시간 안에 처리할 수 있다는 장점이 있습니다.

주요 함수 구성

findMiddle(): 현재 구간의 중간 인덱스를 계산합니다.
updateIndexValue(): 특정 인덱스의 값이 변경되면 해당 노드부터 상위 노드까지 변화량(diff)만큼 재귀적으로 갱신합니다.
findGCDRange(): 주어진 구간과 겹치는 노드들을 재귀적으로 탐색하며 GCD를 병합합니다. 범위를 벗어난 구간은 0을 반환하는데, __gcd(a, 0) = a이므로 결과에 영향을 주지 않습니다.
calcGCDIndex(): 원본 배열을 기반으로 초기 세그먼트 트리를 구축합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 중간 인덱스 계산
int findMiddle(int s, int e) {
   return (s + (e - s) / 2);
}
// 특정 인덱스의 값 갱신
void updateIndexValue(int* st, int ss, int se, int i, int diff, int si) {
   if (i < ss || i > se)
      return;
   st[si] = st[si] + diff;
   if (se != ss) {
      int mid = findMiddle(ss, se);
      updateIndexValue(st, ss, mid, i, diff, 2 * si + 1);
      updateIndexValue(st, mid + 1, se, i, diff, 2 * si + 2);
   }
}
// 주어진 범위 내 GCD 탐색
int findGCDRange(int* st, int ss, int se, int qs, int qe, int si) {
   if (qs <= ss && qe >= se)
      return st[si];
   if (se < qs || ss > qe)
      return 0;
   int mid = findMiddle(ss, se);
   return __gcd(findGCDRange(st, ss, mid, qs, qe, 2 * si + 1),
   findGCDRange(st, mid + 1, se, qs, qe, 2 * si + 2));
}
int findingGCD(int* st, int n, int qs, int qe) {
   if (qs < 0 || qe > n - 1 || qs > qe) {
      cout << "Not valid input";
      return -1;
   }
   return findGCDRange(st, 0, n - 1, qs, qe, 0);
}
// 모든 값 갱신 처리
void updatingAllValues(int arr[], int* st, int n, int i, int new_val) {
   if (i < 0 || i > n - 1) {
      cout << "Not valid input";
      return;
   }
   int diff = new_val - arr[i];
   arr[i] = new_val;
   updateIndexValue(st, 0, n - 1, i, diff, 0);
}
// 세그먼트 트리 노드 구축
int calcGCDIndex(int arr[], int ss, int se, int* st, int si) {
   if (ss == se) {
      st[si] = arr[ss];
      return arr[ss];
   }
   int mid = findMiddle(ss, se);
   st[si] = __gcd(calcGCDIndex(arr, ss, mid, st, si * 2 +1),
   calcGCDIndex(arr, mid + 1, se, st, si * 2 + 2));
   return st[si];
}
// 세그먼트 트리 생성
int* calculatingGCD(int arr[], int n) {
   int x = (int)(ceil(log2(n)));
   int max_size = 2 * (int)pow(2, x) - 1;
   int* st = new int[max_size];
   calcGCDIndex(arr, 0, n - 1, st, 0);
   return st;
}
int main() {
   int arr[] = { 2, 5, 16, 7, 9, 23 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int* st = calculatingGCD(arr, n);
   cout << findingGCD(st, n, 2, 5) << endl;
   return 0;
}

실행 결과

동작 원리 살펴보기

위 코드에서 배열 { 2, 5, 16, 7, 9, 23 }에 대해 인덱스 2~5 구간의 GCD를 조회하면, gcd(16, 7, 9, 23) = 1이므로 결과로 1이 출력됩니다.

시간 복잡도 분석

트리 구축: O(n)
값 갱신: O(log n)
범위 GCD 조회: O(log n)

이처럼 세그먼트 트리를 활용하면 값 변경과 범위 조회가 빈번하게 발생하는 환경에서도 선형 시간 순회 없이 로그 시간 복잡도로 효율적인 처리가 가능합니다.