C++-এ সেগমেন্ট ট্রি দিয়ে আপডেট ও রেঞ্জ GCD কুয়েরি

সমস্যা

একটি অ্যারে এবং Q কুয়েরি। দুটি ধরণের কুয়েরি: (১) একটি ইনডেক্স আপডেট, (২) রেঞ্জ [L,R]-এ GCD বের করা।

সমাধান: সেগমেন্ট ট্রি (Segment Tree)

প্রতিটি নোডে সে সেগমেন্টের GCD সংরক্ষণ।
মার্জ: gcd(left, right)।
আপডেট: O(log n)।
রেঞ্জ কুয়েরি: O(log n)।

C++ কোড (মূল ফাংশনগুলো)

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 (ise) 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 (seqe) 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));
}

// বিল্ড, আপডেট, কুয়েরি র‍্যাপার ফাংশনগুলো সাধারণ সেগমেন্ট ট্রি টেমপ্লেট।

উদাহরণ আউটপুট

(অ্যারে {2,5,16,7,9,23}-এ রেঞ্জ [2,5]-এর GCD = 1)