【C++】指定インデックスの更新と範囲内GCD取得クエリをセグメント木で効率化する方法

このチュートリアルでは、指定されたインデックスの値を更新しながら、任意の範囲内のGCD（最大公約数）を効率的に求めるプログラムについて解説します。

ここでは、整数を要素とする配列とQ個のクエリが与えられます。各クエリに対して、次のいずれかの処理を実行する必要があります。

• 指定されたインデックスの値を新しい値Xに更新する
• 指定された2つのインデックス間の要素のGCDを求める

アプローチ：セグメント木による高速化

素朴な実装では、更新やGCD計算のたびに範囲内の全要素を走査する必要があり、1回のクエリにO(n)の計算量がかかります。そこで本記事では、セグメント木（Segment Tree）を用いて、両方のクエリをO(log n)で処理する方法を紹介します。

セグメント木の各ノードは、担当する区間のGCDを保持します。葉ノードは配列の各要素に対応し、内部ノードは2つの子ノードの値のGCDを持ちます。なお、範囲外のノードに対しては0を返すことで、GCDの単位元（gcd(0, x) = x）として機能させています。

C++での実装例

#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;
}

出力

1

コードの解説

このプログラムは、以下の関数で構成されています。

• findMiddle：区間の中間インデックスを計算します。
• calcGCDIndex / calculatingGCD：配列をもとにセグメント木を再帰的に構築します。
• findGCDRange / findingGCD：指定範囲のGCDを取得します。クエリ範囲の妥当性チェックも行います。
• updateIndexValue / updatingAllValues：指定インデックスの値を更新し、その差分をセグメント木の各ノードへ伝播させます。

実行結果の説明

サンプルでは、配列 {2, 5, 16, 7, 9, 23} に対して、インデックス2〜5の範囲（16, 7, 9, 23）のGCDを求めています。gcd(16, 7) = 1 となるため、結果として 1 が出力されます。

計算量

• セグメント木の構築：O(n)
• 範囲GCDクエリ：O(log n)
• 点更新：O(log n)

このようにセグメント木を活用することで、更新と範囲クエリの両方を対数時間で処理でき、クエリが大量に発生する場面で大きな効果を発揮します。