C++ प्रोग्राम में दिए गए इंडेक्स को अपडेट करने और रेंज में GCD ढूंढने के लिए क्वेरीज

समस्या विवरण

इस समस्या में, हमें आकार N का एक ऐरे arr[] और Q क्वेरीज दी गई हैं जो दो प्रकार की हो सकती हैं। हमारा कार्य दिए गए इंडेक्स को अपडेट करने और रेंज में GCD ढूंढने के लिए क्वेरीज को हल करने का प्रोग्राम बनाना है।

क्वेरीज हैं:

टाइप 1 - {1, इंडेक्स, मान} - दिए गए इंडेक्स पर मान से तत्व बढ़ाएं।

टाइप 2 - {2, L, R} - इंडेक्स रेंज [L, R] में तत्वों का GCD ढूंढें।

समस्या विवरण - हमें उन तत्वों का GCD ढूंढना है जो रेंज [L, R] में हैं और मान वापस करना है।

उदाहरण

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

हल करने का दृष्टिकोण

समस्या को हल करने का एक दृष्टिकोण सेगमेंट ट्री का उपयोग करना है जिसका उपयोग ऐरे के लिए GCD को प्रीप्रोसेस करने के लिए किया जाता है। यह प्रत्येक क्वेरी के लिए GCD की गणना करने का समय कम कर देगा।

सेगमेंट ट्री बनाना और उसके साथ काम करना

हम यहां जिस सेगमेंट ट्री का उपयोग कर रहे हैं वह एक ट्री है जो ऐरे के तत्वों को लीफ नोड्स के रूप में संग्रहीत करता है और तत्वों के GCD को इंटरनल नोड्स के रूप में।

उदाहरण

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

आउटपुट

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