Truy vấn cập nhật chỉ số và tìm GCD trên đoạn trong C++

Mô tả bài toán

Cho mảng arr[] kích thước N và Q truy vấn hai loại:

• Loại 1: {1, index, value} - tăng arr[index] thêm value.
• Loại 2: {2, L, R} - tìm GCD của các phần tử trong đoạn [L, R].

Giải pháp

Sử dụng cây đoạn (segment tree) lưu GCD tại các nút. Cập nhật và truy vấn đều O(log N).

Ví dụ minh họa (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, 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 sz = 2 * (int)pow(2, ceil(log2(n))) - 1;
    int* st = new int[sz];
    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;
    }
    return 0;
}

Đầu vào/Đầu ra mẫu

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