C++ 세그먼트 트리로 인덱스 값 갱신 및 구간 GCD 쿼리 처리하기

문제 개요

이 문제에서는 크기가 N인 배열 arr[]와 두 가지 유형으로 나뉘는 Q개의 쿼리가 주어집니다. 우리가 작성해야 할 프로그램은 주어진 인덱스의 값을 갱신하거나 특정 범위 내 요소들의 최대공약수(GCD)를 구하는 쿼리를 처리해야 합니다.

쿼리는 다음과 같은 형식으로 구성됩니다.

유형 1 − {1, index, value} : 주어진 인덱스에 있는 요소의 값을 value만큼 증가시킵니다.

유형 2 − {2, L, R} : 인덱스 범위 [L, R]에 포함된 요소들의 GCD를 구합니다.

문제 설명 − 범위 [L, R]에 속한 요소들의 최대공약수를 계산하여 그 값을 반환해야 합니다.

입력 예시

arr[] = {5, 1, 7, 3, 8}, Q = 3
Queries: {{2, 2, 5}, {1, 3, 6}, {2, 2, 5}}

출력 예시

1
1

설명

첫 번째 쿼리 {2, 2, 5}는 인덱스 2부터 5까지의 요소, 즉 7, 3, 8의 GCD를 묻습니다. gcd(7, 3, 8) = 1이므로 1을 반환합니다.

두 번째 쿼리 {1, 3, 6}은 인덱스 3의 값을 6만큼 증가시킵니다. 이후 배열은 {5, 1, 7, 9, 8}로 갱신됩니다.

세 번째 쿼리 {2, 2, 5}는 갱신된 배열에서 인덱스 2부터 5까지의 요소 7, 9, 8의 GCD를 구합니다. gcd(7, 9, 8) = 1이므로 역시 1을 반환합니다.

풀이 접근 방식

이 문제를 효율적으로 해결하는 대표적인 방법은 세그먼트 트리(Segment Tree)를 활용하는 것입니다. 세그먼트 트리를 사용하면 배열의 구간별 GCD를 미리 전처리해 둘 수 있으므로, 매 쿼리마다 해당 범위의 요소를 처음부터 다시 살펴보며 GCD를 계산하는 비용을 크게 줄일 수 있습니다.

세그먼트 트리의 구조와 동작 원리

여기서 사용하는 세그먼트 트리는 배열의 개별 요소들을 리프 노드에 저장하고, 내부 노드에는 자식 노드들이 담당하는 구간 요소들의 GCD 값을 저장하는 트리입니다. 트리를 한 번 구성하는 데 O(N)의 시간이 걸리며, 이후 각 쿼리(값 갱신 또는 범위 GCD 조회)는 O(log N) 시간 안에 처리할 수 있습니다.

아래는 위 접근 방식의 동작을 보여주는 C++ 프로그램입니다.

구현 예제 코드

#include <bits/stdc++.h>
using namespace std;
int calcGcdRangeRec(int* st, int segL, int segR, int L, int R, int currNode) {
    if (L <= segL && R >= segR)
        return st[currNode];
    if (segR < L || segL > R)
        return 0;
    int mid = (segL + (segR - segL)/2);
    int GcdL = calcGcdRangeRec(st, segL, mid, L, R, 2 * currNode + 1);
    int GcdR = calcGcdRangeRec(st, mid + 1, segR, L, R, 2 * currNode + 2);
    return __gcd(GcdL, GcdR);
}
void updateArrayValueRec(int* st, int L, int R, int index, int diff, int currNode) {
    if (index < L || index > R)
        return;
    st[currNode] = st[currNode] + diff;
    if (R != L) {
        int mid = (L + (R - L)/ 2);
        updateArrayValueRec(st, L, mid, index, diff, 2 * currNode + 1);
        updateArrayValueRec(st, mid + 1, R, index, diff, 2 * currNode + 2);
    }
}
void updateArrayValue(int arr[], int* st, int n, int index, int newVal) {
    if (index < 0 || index > n - 1)
        cout << "Invalid Input";
    else{
        int diff = newVal - arr[index];
        arr[index] = newVal;
        updateArrayValueRec(st, 0, n - 1, index, diff, 0);
    }
}
int calcGcdRange(int* st, int n, int L, int R) {
    if (L < 0 || R > n - 1 || L > R) {
        cout << "Invalid Input";
        return -1;
    }
    return calcGcdRangeRec(st, 0, n - 1, L, R, 0);
}
int constructGcdST(int arr[], int L, int R, int* st, int currNode) {
    if (L == R) {
        st[currNode] = arr[L];
        return arr[L];
    }
    int mid = (L + (R - L)/2);
    int GcdL = constructGcdST(arr, L, mid, st, currNode * 2 + 1);
    int GcdR = constructGcdST(arr, mid + 1, R, st, currNode * 2 + 2);
    st[currNode] = __gcd(GcdL, GcdR);
    return st[currNode];
}
int main() {
    int arr[] = { 1, 3, 6, 9, 9, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int Q = 3;
    int query[3][3] = {{2, 1, 3}, {1, 1 , 10}, {2, 1, 3}};
    int value = (int)(ceil(log2(n)));
    int size = 2 * (int)pow(2, value) - 1;
    int* st = new int[size];
    constructGcdST(arr, 0, n - 1, st, 0);
    for(int i = 0; i < n; i++){
        if(query[i][0] == 1){
            cout<<"Query "<<(i + 1)<<": Updating Values!\n";
            updateArrayValue(arr, st, n, query[i][1], query[i][2]);
        }
        if(query[i][0] == 2)
        cout<<"Query "<<(i + 1)<<": GCD is "<<calcGcdRange(st, n, query[i][1], query[i][2])<<endl;
    }
    return 0;
}

출력 결과

Query 1: GCD is 3
Query 2: Updating Values!
Query 3: GCD is 1

결과 해석

배열 {1, 3, 6, 9, 9, 11}에 대해 첫 번째 쿼리 {2, 1, 3}은 인덱스 1부터 3까지의 요소 3, 6, 9의 GCD를 구합니다. 그 값은 3입니다.

두 번째 쿼리 {1, 1, 10}은 인덱스 1의 값을 10으로 갱신하며, 이후 배열은 {1, 10, 6, 9, 9, 11}이 됩니다.

세 번째 쿼리 {2, 1, 3}은 갱신된 배열에서 인덱스 1부터 3까지의 요소 10, 6, 9의 GCD를 구하며, 그 값은 1입니다.