n개의 원소로 이루어진 배열과, 배열의 시작 지점(L)부터 끝 지점(R)까지를 가리키는 여러 개의 범위 쿼리가 주어집니다. 이 문제의 목표는 각 쿼리 범위 안에서 짝수 번 등장한 원소들의 XOR 값을 구하는 것입니다.
문제 이해하기
먼저 예시를 통해 문제를 살펴보겠습니다.
입력 −
array = {1, 2, 3, 1, 1, 2, 2, 3}
queries = 2
L = 2, R = 5
L = 2, R = 7
출력 −
0 1 0
접근 방법
이 문제는 생각보다 간단하게 해결할 수 있습니다. 각 쿼리마다 주어진 범위 내 원소들의 XOR 합을 구하면 되는데, 이때 프리픽스 XOR(prefix XOR) 기법을 활용하면 매우 효율적입니다.
핵심 아이디어
- 전체 XOR(allXOR): 범위 [L, R]의 모든 원소를 XOR한 값입니다. 어떤 값이 홀수 번 등장하면 그대로 남고, 짝수 번 등장하면 서로 상쇄되어 사라집니다.
- 고유 값 XOR(distinctXOR): 범위 내에 등장하는 서로 다른 값들을 각각 한 번씩만 XOR한 값입니다. 펜윅 트리(BIT)에 각 값의 가장 최근 등장 위치만 기록하는 방식으로 구할 수 있습니다.
- 두 값을 다시 XOR하면(
allXOR ^ distinctXOR) 홀수 번 등장한 값은 상쇄되고, 짝수 번 등장한 값만 남습니다.
쿼리가 여러 개인 경우에는 쿼리를 오른쪽 끝(R) 값 기준으로 정렬해 오프라인으로 처리하고, lastOcc 배열로 각 값의 마지막 등장 위치를 추적하면서 펜윅 트리를 갱신합니다. 이렇게 하면 중복 계산 없이 모든 쿼리를 효율적으로 처리할 수 있습니다.
C++ 구현 예제
위 접근 방식을 C++로 구현한 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
struct que {
int L, R, idx;
};
bool cmp(que a, que b){
if (a.R != b.R)
return a.R < b.R;
else
return a.L < b.L;
}
int findXORSum(int BIT[], int index){
int xorSum = 0;
index = index + 1;
while (index > 0){
xorSum ^= BIT[index];
index -= index & (-index);
}
return xorSum;
}
void updateBIT(int BIT[], int N, int index, int val){
index = index + 1;
while (index <= N){
BIT[index] ^= val;
index += index & (-index);
}
}
int* createBitTree(int arr[], int N){
int* BIT = new int[N + 1];
for (int i = 1; i <= N; i++)
BIT[i] = 0;
return BIT;
}
void findXORSolution(int arr[], int N, que queries[], int Q, int BIT[]){
int* prefixXOR = new int[N + 1];
map<int, int> XORval;
for (int i = 0; i < N; i++) {
if (!XORval[arr[i]])
XORval[arr[i]] = i;
if (i == 0)
prefixXOR[i] = arr[i];
else
prefixXOR[i] = prefixXOR[i - 1] ^ arr[i];
}
int lastOcc[1000001];
memset(lastOcc, -1, sizeof(lastOcc));
sort(queries, queries + Q, cmp);
int res[Q];
int j = 0;
for (int i = 0; i < Q; i++){
while (j <= queries[i].R){
if (lastOcc[XORval[arr[j]]] != -1)
updateBIT(BIT, N, lastOcc[XORval[arr[j]]], arr[j]);
updateBIT(BIT, N, j, arr[j]);
lastOcc[XORval[arr[j]]] = j;
j++;
}
int allXOR = prefixXOR[queries[i].R] ^ prefixXOR[queries[i].L - 1];
int distinctXOR = findXORSum(BIT, queries[i].R) ^ findXORSum(BIT, queries[i].L - 1);
res[queries[i].idx] = allXOR ^ distinctXOR;
}
for (int i = 0; i < Q; i++)
cout << res[i] << endl;
}
int main() {
int arr[] = {1, 2, 1, 1, 2, 2, 3, 1, 3};
int N = sizeof(arr) / sizeof(arr[0]);
int* BIT = createBitTree(arr, N);
que queries[4];
queries[0].L = 1;
queries[0].R = 4; queries[0].idx = 0;
queries[1].L = 2;
queries[1].R = 7, queries[1].idx = 1;
queries[2].L = 0;
queries[2].R = 3, queries[2].idx = 2;
queries[3].L = 3;
queries[3].R = 6, queries[3].idx = 3;
int Q = sizeof(queries) / sizeof(queries[0]);
cout<<"Xor sum for all queries is \n";
findXORSolution(arr, N, queries, Q, BIT);
return 0;
}
실행 결과
Xor sum for all queries is 3 2 0 2
정리
프리픽스 XOR과 펜윅 트리(BIT)를 함께 활용하면 각 쿼리를 로그 시간 안에 처리할 수 있어, 쿼리 개수가 많은 상황에서도 효율적으로 동작합니다. 범위 쿼리 문제에서 자주 등장하는 패턴이므로 원리를 잘 익혀두면 다양한 알고리즘 문제에 응용할 수 있습니다.