সি++-এ সেগমেন্ট ট্রি ব্যবহার করে অ্যারে আপডেট ও রেঞ্জ GCD কোয়েরি সমাধান

সমস্যা বিবরণ

একটি অ্যারে arr[] এবং Qটি কোয়েরি দেওয়া আছে। কোয়েরি দুটি ধরনের:

Type 1: {1, index, value} — নির্দিষ্ট ইনডেক্সের মান বাড়ান।
Type 2: {2, L, R} — [L, R] রেঞ্জের উপাদানগুলোর GCD বের করুন।

উদাহরণ: arr[] = {5, 1, 7, 3, 8}, Q = 3, Queries: {{2,2,5}, {1,3,6}, {2,2,5}}

সমাধানের পদ্ধতি

সেগমেন্ট ট্রি ব্যবহার করে সমাধান করা হয়েছে। সেগমেন্ট ট্রিতে লিফ নোডগুলো অ্যারের উপাদান এবং ইন্টারন্যাল নোডগুলো সেই রেঞ্জের GCD সংরক্ষণ করে।

constructGcdST ফাংশন দিয়ে সেগমেন্ট ট্রি নির্মাণ করুন।
updateArrayValue ফাংশন দিয়ে পয়েন্ট আপডেট করুন।
calcGcdRange ফাংশন দিয়ে রেঞ্জ 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) / 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);
    }
}

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 * (int)pow(2, ceil(log2(n))) - 1;
    int* st = new int[size];
    // constructGcdST call here...
    // process queries...
    return 0;
}

আউটপুট

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