C++-এ সাবঅ্যারে XOR-এর XOR কোয়েরি সমাধান

একটি অ্যারে এবং একাধিক রেঞ্জ কোয়েরি দেওয়া আছে। প্রতিটি কোয়েরি [L, R]-র জন্য, সেই রেঞ্জের সব সাবঅ্যারেক্স XOR করুন, তারপর সেই ফলাফলগুলোর XOR বের করুন।

উদাহরণ

ইনপুট: arr = {4,1,2,3,5}, Q = 3

• Query ১: {1,2} → আউটপুট: 0
• Query ২: {2,4} → আউটপুট: 2
• Query ৩: {1,4} → আউটপুট: 0

Query ২ ব্যাখ্যা: রেঞ্জ {1,2,3}। সাবঅ্যারে: {1},{2},{3},{1,2},{2,3},{1,2,3}। প্রতিটি এলিমেন্টের فراিকোয়েন্সি: ১→৩, ২→৪, ৩→৩। জোড় বার আসা এলিমেন্ট XOR-এ ক্যাঞ্সেল হয় (২ ক্যাঞ্সেল)। বাকি ১ XOR ৩ = ২।

প্যাটার্ন ও অ্যালগরিদম

1. রেঞ্জ সাইজ (R-L+1) জোড় হলে → আউটপুট ০ (সব এলিমেন্ট জোড় বার আসে)।
2. রেঞ্জ সাইজ বিজোড় হলে → শুধু ইভেন পজিশন (০-বেসড) वाली এলিমেন্টগুলোর XORই ফলাফল।
3. দুই প্রিফিক্স XOR অ্যারে বানান: prefEven (ইভেন ইনডেক্সের XOR), prefOdd (অড ইনডেক্সের XOR)।
4. কোয়েরি সমাধান:
   • L ইভেন হলে: prefEven[R] ^ prefEven[L-1]
   • L অড হলে: prefOdd[R] ^ prefOdd[L-1]

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

void ansQueries(int prefeven[], int prefodd[], int l, int r) {
    if ((r - l + 1) % 2 == 0) {
        cout << "0\n";
    } else {
        if (l % 2 == 0)
            cout << (prefeven[r] ^ prefeven[l-1]) << "\n";
        else
            cout << (prefodd[r] ^ prefodd[l-1]) << "\n";
    }
}

int main() {
    int arr[] = {4,1,2,3,5};
    int n = sizeof(arr)/sizeof(int);
    int l[] = {1,2,1};
    int r[] = {2,4,4};
    int q = sizeof(l)/sizeof(int);
    int prefodd[n+1] = {0}, prefeven[n+1] = {0};
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) {
            prefeven[i] = arr[i-1] ^ prefeven[i-1];
            prefodd[i] = prefodd[i-1];
        } else {
            prefeven[i] = prefeven[i-1];
            prefodd[i] = prefodd[i-1] ^ arr[i-1];
        }
    }
    for (int i = 0; i < q; i++)
        ansQueries(prefeven, prefodd, l[i], r[i]);
    return 0;
}

আউটপুট

0
2
0

ব্যাখ্যা

• প্রিফিক্স অ্যারে ১-বেসড (সুবিধার জন্য)।
• prefeven[i] = ১ থেকে i পর্যন্ত ইভেন পজিশনের XOR।
• prefodd[i] = ১ থেকে i পর্যন্ত অড পজিশনের XOR।
• রেঞ্জ সাইজ জোড় হলে সব ক্যাঞ্সেল → ০।
• বিজোড় হলে শুধু ইভেন পজিশন (রিলেটিভ টু L) sobrevive করে।

কমপ্লেক্সিটি

• প্রিপ্রসেস: O(n)
• প্রতি কোয়েরি: O(1)
• স্পেস: O(n)