指定インデックスの更新と区間GCDクエリを処理するC++プログラム(セグメント木による実装)

この記事では、サイズNの整数型配列arr[]とQ個のクエリが与えられ、各クエリは次の2種類のいずれかであるという問題を扱います。目標は、指定インデックスの値更新と区間GCD(最大公約数)の取得を効率的に行うプログラムをC++で作成することです。

クエリの種類

• タイプ1:{1, index, value} — 指定されたインデックスの要素をvalueに更新します。
• タイプ2:{2, L, R} — インデックス範囲[L, R]に含まれる要素のGCDを求めて返します。

入力例

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

出力例

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

実行結果の説明

最初のクエリ{2, 1, 4}では、インデックス1〜4の要素「1, 7, 3, 8」のGCDである1が出力されます。次のクエリ{1, 3, 6}では、インデックス3の値が6だけ増やされ、配列は{5, 1, 7, 9, 8}になります。最後のクエリ{2, 1, 4}では、更新後の要素「1, 7, 9, 8」のGCDである1が出力されます。

解法アプローチ:セグメント木

この問題を効率的に解くには、セグメント木(segment tree)を利用する方法が有効です。事前に各区間のGCDを木構造として構築しておくことで、更新クエリが混在しても、各クエリに対するGCD計算のコストを大幅に削減できます。

セグメント木の仕組み

ここで使用するセグメント木は、配列の各要素を葉ノードとして保持し、内部ノードにはその子ノードが担当する区間の要素のGCDを格納する木構造です。これにより、次のような計算量でクエリを処理できます。

• 木の構築:O(N)
• 区間GCDクエリ:O(log N)
• 点更新:O(log N)

素朴に毎回区間内の全要素からGCDを計算するとO(R−L)かかりますが、セグメント木ならQ個のクエリ全体でもO(Q 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 < Q; 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;
    }
    delete[] st;
    return 0;
}

プログラムの出力

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

出力の解説

初期配列は{1, 3, 6, 9, 9, 11}です。

• クエリ1:{2, 1, 3} — インデックス1〜3の要素は「3, 6, 9」なので、GCDは3となります。
• クエリ2:{1, 1, 10} — インデックス1の値が10に更新され、配列は{1, 10, 6, 9, 9, 11}になります。
• クエリ3:{2, 1, 3} — 更新後のインデックス1〜3の要素は「10, 6, 9」なので、GCDは1となります。

このように、セグメント木を使えば更新と区間GCD取得の両方を対数時間で処理でき、多数のクエリが発生する場面でも高いパフォーマンスを発揮します。