Query Update Index และหา GCD ใน Range ด้วย Segment Tree ใน C++

โจทย์: Array ของจำนวนเต็ม รองรับ 2 operations: 1) Update index i ด้วยค่าใหม่ 2) Query GCD ใน range [l, r]

โครงสร้างข้อมูล: Segment Tree

• แต่ละ node เก็บ GCD ของ segment
• Build: O(N)
• Update: O(log N)
• Query: O(log N)

ตัวอย่างโค้ด 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] += 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);
    }
}

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) 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) 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, 2*si+1),
                   calcGCDIndex(arr, mid+1, se, st, 2*si+2));
    return st[si];
}

int* calculatingGCD(int arr[], int n) {
    int x = ceil(log2(n));
    int max_size = 2 * (1 << 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; // GCD(16,7,9,23) = 1
}

อินพุต

arr = [2,5,16,7,9,23], query GCD(2,5)

เอาต์พุท

1

Complexity

• Build: O(N)
• Update: O(log N)
• Query: O(log N)
• Space: O(N)