C++로 배열의 인덱스 범위 [L, R]에서 비트 AND 쿼리 처리하기

이 글에서는 정수 배열이 주어졌을 때, 특정 인덱스 범위 [L, R] 내 원소들의 비트 AND 연산 결과를 구하는 문제를 다룹니다. 예를 들어 배열 {1, 3, 1, 2, 32, 3, 3, 4, 4}에서 쿼리 {0, 1}과 {3, 5}에 대한 답을 구하는 식입니다.

무식한 접근 (Brute Force)

가장 직관적인 방법은 각 쿼리마다 범위 내의 모든 원소를 순회하며 비트 AND를 누적하는 것입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    int ARR[] = { 10, 10, 12, 16, 8 };
    int n = sizeof(ARR) / sizeof(int);
    int queries[][2] = { {0, 2}, {3, 4} };
    int q = sizeof(queries) / sizeof(queries[0]);

    for (int i = 0; i < q; i++) {
        long ans = 1LL << 32;
        ans -= 1; // 모든 비트를 1로 초기화 (0xFFFFFFFF)
        for (int j = queries[i][0]; j <= queries[i][1]; j++) {
            ans &= ARR[j];
        }
        cout << ans << "\n";
    }
    return 0;
}

출력

8
0

이 방식은 쿼리당 O(N) 시간이 걸려, 전체 시간 복잡도가 O(N × Q)가 됩니다. N과 Q가 큰 제약 조건에서는 시간 초과가 발생할 수 있습니다.

효율적인 접근: 비트별 프리픽스 합 (Prefix Bit Count)

비트 AND 연산의 성질을 이용합니다. 어떤 비트가 결과에서 1이 되려면, 범위 내 모든 숫자에서 그 비트가 1이어야 합니다. 따라서 각 비트 위치별로 "해당 비트가 1인 원소의 개수"를 프리픽스 합으로 미리 계산해두면, 쿼리 시 O(1)에 판별할 수 있습니다.

알고리즘

32비트 정수 기준, 각 비트(0~31)마다 프리픽스 합 배열을 만듭니다.
prefix[bit][i] = arr[0..i] 중 bit번째 비트가 1인 원소의 개수
쿼리 [L, R]에서 특정 비트 b의 1의 개수는 prefix[b][R] - prefix[b][L-1] (L>0일 때)입니다.
이 개수가 범위 길이 (R - L + 1)과 같으면, 그 비트는 결과에서 1입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

const int MAX_BITS = 32;
const int MAX_N = 100000;
int prefixBits[MAX_BITS][MAX_N];

// 프리픽스 비트 카운트 계산
void buildPrefixBits(const int* arr, int n) {
    for (int bit = 0; bit < MAX_BITS; ++bit) {
        prefixBits[bit][0] = (arr[0] >> bit) & 1;
        for (int i = 1; i < n; ++i) {
            prefixBits[bit][i] = prefixBits[bit][i-1] + ((arr[i] >> bit) & 1);
        }
    }
}

// 쿼리 [l, r]에 대한 비트 AND 결과 계산
int rangeBitwiseAnd(int l, int r) {
    long ans = 0;
    int len = r - l + 1;
    for (int bit = 0; bit < MAX_BITS; ++bit) {
        int cnt = prefixBits[bit][r] - (l > 0 ? prefixBits[bit][l-1] : 0);
        if (cnt == len) {
            ans |= (1LL << bit);
        }
    }
    return (int)ans;
}

int main() {
    int ARR[] = { 10, 10, 12, 16, 8 };
    int n = sizeof(ARR) / sizeof(int);
    memset(prefixBits, 0, sizeof(prefixBits));
    buildPrefixBits(ARR, n);

    int queries[][2] = { {0, 2}, {3, 4} };
    int q = sizeof(queries) / sizeof(queries[0]);
    for (int i = 0; i < q; ++i) {
        cout << rangeBitwiseAnd(queries[i][0], queries[i][1]) << "\n";
    }
    return 0;
}

출력

2
0

복잡도 분석

전처리: O(32 × N) ≈ O(N)
쿼리당: O(32) ≈ O(1)
전체: O(N + Q) — 대규모 데이터에도 적합

핵심 아이디어 설명

비트 AND에서 특정 비트가 1로 남으려면, 범위 내 모든 숫자에서 그 비트가 1이어야 합니다. 프리픽스 합을 이용해 각 비트별로 "1의 개수"를 빠르게 세고, 이 개수가 범위 길이와 일치하는지만 확인하면 됩니다. 비트 연산과 프리픽스 합을 조합한 전형적인 최적화 기법입니다.

결론

배열의 구간 비트 AND 쿼리를 무식한 O(N×Q) 풀이에서, 비트별 프리픽스 합을 이용해 O(N+Q)로 개선하는 방법을 살펴보았습니다. 이 기법은 C++, Java, Python 등 어떤 언어에서도 동일하게 적용 가능하며, 비트 연산 문제에서 자주 쓰이는 중요한 패턴입니다.