โปรแกรมจัดการคำถามอัปเดตค่าและหา GCD ในช่วงด้วย Segment Tree ใน C++

ให้อาร์เรย์ arr[] ขนาด N และ Q คำถาม 2 ประเภท:

• Type 1: {1, index, value} — เพิ่มค่าที่ index ด้วย value
• Type 2: {2, L, R} — หา GCD ขององค์ประกอบในช่วง [L, R]

ตัวอย่าง:

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

วิธีแก้ปัญหา

ใช้ Segment Tree เก็บค่า GCD ของช่วงต่างๆ ใบเป็นค่าอาร์เรย์ โหนดภายในเป็น GCD ของลูก ทำให้ query และ update ใช้เวลา 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) / 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] += diff;
    if (L != R) {
        int mid = (L + R) / 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"; return; }
    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) / 2;
    int GcdL = constructGcdST(arr, L, mid, st, 2*currNode+1);
    int GcdR = constructGcdST(arr, mid+1, R, st, 2*currNode+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 size = 2 * pow(2, ceil(log2(n))) - 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]);
        } else {
            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