Truy vấn XOR của XOR tất cả mảng con trong khoảng bằng C++

Cho mảng, truy vấn [L,R]: tính XOR của XOR tất cả mảng con nằm hoàn toàn trong [L,R]. Quan sát: nếu độ dài khoảng chẵn → kết quả 0 (mỗi phần tử xuất hiện số lần chẵn). Nếu lẻ → kết quả = XOR các phần tử ở vị trí chẵn trong khoảng (0-based trong khoảng).

Giải pháp: Prefix XOR cho chỉ số chẵn/lẻ

Xây dựng 2 mảng prefix XOR:

• prefEven[i] = XOR các arr[j] với j chẵn (1-based) từ 1 đến i.
• prefOdd[i] = XOR các arr[j] với j lẻ từ 1 đến i.

• Nếu (R-L+1) % 2 == 0 → 0.
• Nếu L chẵn → prefEven[R] ^ prefEven[L-1].
• Nếu L lẻ → prefOdd[R] ^ prefOdd[L-1].

Ví dụ

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

Kết quả

0 2 0

Kết luận

Truy vấn XOR của XOR tất cả mảng con trong khoảng: O(1) mỗi truy vấn nhờ prefix XOR chẵn/lẻ. Code C++.