โจทย์
ได้รับอาร์เรย์และ queries หลายช่วง [L, R] ต้องการหา XOR ของ subarray ในช่วงนั้น
ตัวอย่าง
Input: array = {1, 4, 5, 7, 2, 9}, L = 1, R = 5
Output: 4 ^ 5 ^ 7 ^ 2 ^ 9 = 13
วิธีแก้ปัญหา: Prefix XOR Array (Optimal)
สร้าง prefix XOR array โดยที่ prefix[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]
แล้ว XOR ของช่วง [L, R] = prefix[R] ^ prefix[L-1] (ถ้า L > 0) หรือ prefix[R] (ถ้า L = 0)
เหตุผล: prefix[R] = arr[0] ^ ... ^ arr[L-1] ^ arr[L] ^ ... ^ arr[R]
prefix[L-1] = arr[0] ^ ... ^ arr[L-1]
XOR ทั้งคู่: ส่วน arr[0]...arr[L-1] จะ cancel ออก (XOR ตัวเอง = 0) เหลือ arr[L]...arr[R]
โค้ดตัวอย่าง (Prefix XOR - Simple & Fast)
#include <iostream>
#include <vector>
using namespace std;
class RangeXORQuery {
vector<int> prefixXOR;
public:
RangeXORQuery(const vector<int>& arr) {
int n = arr.size();
prefixXOR.resize(n);
if (n > 0) prefixXOR[0] = arr[0];
for (int i = 1; i < n; i++) {
prefixXOR[i] = prefixXOR[i-1] ^ arr[i];
}
}
int query(int L, int R) {
if (L == 0) return prefixXOR[R];
return prefixXOR[R] ^ prefixXOR[L-1];
}
};
int main() {
vector<int> arr = {1, 4, 5, 7, 2, 9};
RangeXORQuery rxq(arr);
cout << "XOR[1,5] = " << rxq.query(1, 5) << endl; // 4^5^7^2^9 = 13
cout << "XOR[0,2] = " << rxq.query(0, 2) << endl; // 1^4^5 = 0
cout << "XOR[2,4] = " << rxq.query(2, 4) << endl; // 5^7^2 = 0
return 0;
}
ผลลัพธ์
XOR[1,5] = 13 XOR[0,2] = 0 XOR[2,4] = 0
วิธีในบทความต้นฉบับ: Bit Counting + BIT (Complex)
บทความต้นฉบับใช้วิธีนับบิต 1 ในแต่ละตำแหน่ง (32 bits) ร่วมกับ Binary Indexed Tree (Fenwick Tree) ซึ่งซับซ้อนกว่าและช้ากว่าวิธี Prefix XOR อย่างมาก
Complexity Comparison
| วิธี | Preprocess | Query | Space |
|---|---|---|---|
| Prefix XOR | O(N) | O(1) | O(N) |
| Bit Counting + BIT | O(N log N) | O(log N) | O(N log MAX) |
สรุป
สำหรับ Range XOR Query แบบ static array (ไม่มี update) Prefix XOR เป็นวิธีที่ดีที่สุด O(N) preprocess, O(1) per query หากมี update ให้ใช้ Fenwick Tree หรือ Segment Tree ที่รองรับ XOR operation
