C++로 구현하는 부분 배열의 XOR 계산 방법

이 문제에서는 배열 arr[]과 배열 내 L부터 R까지의 범위를 나타내는 여러 쿼리가 주어집니다. 우리의 목표는 L부터 R 사이에 해당하는 부분 배열의 XOR 값을 출력하는 것입니다.

문제 이해하기

예시를 통해 문제를 살펴보겠습니다.

• 입력: array = {1, 4, 5, 7, 2, 9}, L = 1, R = 5
• 출력: 13
• 설명: 4 ^ 5 ^ 7 ^ 2 ^ 9 = 13

해결 접근 방법

다음과 같은 핵심 관찰을 바탕으로 문제를 효율적으로 해결할 수 있습니다.

• XOR 연산에서 특정 비트 자리에 1이 홀수 개 존재하면 그 비트의 결과는 1이 되고, 짝수 개라면 0이 됩니다.

이 성질을 활용하여 각 비트별 1의 개수를 저장하는 2차원 배열 count를 생성합니다. 여기서 count[i][j]는 부분 배열 arr[0..j]에서 i번째 비트 위치에 있는 1의 개수를 의미합니다.

부분 배열 arr[L..R]의 특정 비트에 대한 1의 개수는 다음 공식으로 구할 수 있습니다.

count[i][R] - count[i][L-1]

계산된 1의 개수가 홀수라면, 최종 결과값에서 해당 i번째 비트가 설정됩니다. 최종 XOR 값은 설정된 각 비트에 대응하는 2의 거듭제곱 값을 모두 더하여 얻을 수 있습니다.

이 방식은 전처리 단계에서 O(32 × n)의 시간이 소요되며, 이후 각 쿼리는 O(32) 만에 처리할 수 있어 여러 쿼리를 반복적으로 수행해야 하는 상황에서 매우 효율적입니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
void preProcessArray(int arr[], int n, vector<vector<int> >& cnt) {
    int i, j;
    for (i = 0; i < 32; i++) {
        cnt[i][0] = 0;
        for (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;
    int noOfOnes;
    int i, j;
    for (i = 0; i < 32; i++) {
        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;
    int R = 5;
    cout<<"The XOR of SubArray: "<<findXORofSubArray(L, R, count);
    return 0;
}

출력 결과

The XOR of SubArray: 13