Trong bài toán này, cho một mảng arr[] và một số truy vấn là khoảng L đến R trong mảng. Nhiệm vụ in ra XOR của con mảng từ L đến R.
Ví dụ:
Input – mảng = {1, 4, 5, 7, 2, 9}, L = 1, R = 5
Output** – 4^5^7^2^9
Giải pháp: tạo mảng 2D count lưu số bit 1. count[i][j] = số bit 1 tại vị trí bit i trong arr[0..j]. Số bit 1 cho subarray arr[L..R] = count[i][R] - count[i][L-1]. Nếu số bit 1 lẻ thì set bit i trong kết quả.
Ví dụ minh họa
#include <bits/stdc++.h>
using namespace std;
void preProcessArray(int arr[], int n, vector<vector<int>>& cnt) {
for (int i = 0; i < 32; i++) {
cnt[i][0] = 0;
for (int j = 0; j < n; j++) {
if (j > 0)
cnt[i][j] = cnt[i][j - 1];
if (arr[j] & (1 << i))
cnt[i][j]++;
}
}
}
int findXORofSubArray(int L, int R, const vector<vector<int>>& count) {
int result = 0;
for (int i = 0; i < 32; i++) {
int noOfOnes = count[i][R] - ((L > 0) ? count[i][L - 1] : 0);
if (noOfOnes & 1)
result += (1 << i);
}
return result;
}
int main() {
int arr[] = {1, 4, 5, 7, 2, 9};
int n = sizeof(arr) / sizeof(arr[0]);
vector<vector<int>> count(32, vector<int>(n));
preProcessArray(arr, n, count);
int L = 1, R = 5;
cout << "XOR của SubArray: " << findXORofSubArray(L, R, count);
return 0;
}Kết quả
XOR của SubArray: 13