C++로 배열 인덱스 범위 [L, R]의 비트 OR(Bitwise OR) 쿼리 처리하기

이 글에서는 정수 배열이 주어졌을 때, 지정된 범위 내에 있는 모든 숫자의 비트 OR(bitwise OR) 값을 구하는 방법을 다룹니다.

입력: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
출력:
3
7
1 OR 3 = 3
2 OR 3 OR 4 = 7

입력: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
출력:
7
7

이 문제는 우선 무차별 대입(brute force) 방식으로 접근한 뒤, 더 큰 입력 제약 조건에서도 동작 가능한지 확인해 보겠습니다. 만약 불가능하다면, 접근 방식을 최적화하여 높은 제약 조건에서도 원활하게 작동하도록 개선합니다.

무차별 대입(Brute Force) 접근법

이 방식에서는 각 쿼리의 범위를 단순히 순회하면서 범위 내 모든 숫자의 비트 OR를 계산하고 그 결과를 출력합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = { 7, 5, 3, 5, 2, 3 };
   int n = sizeof(arr) / sizeof(int); // 배열의 크기
   int queries[][2] = { { 1, 3 }, { 4, 5 } }; // 주어진 쿼리
   int q = sizeof(queries) / sizeof(queries[0]); // 쿼리의 개수
   for(int i = 0; i < q; i++) { // 모든 쿼리를 순회
      long ans = 0;
      for(int j = queries[i][0]; j <= queries[i][1]; j++) // 범위를 순회
         ans |= arr[j]; // 답 계산
      cout << ans << "\n";
   }
   return 0;
}

실행 결과

7
3

이 방식의 시간 복잡도는 O(N*Q)입니다. 여기서 N은 배열의 크기, Q는 쿼리의 개수입니다. 보시다시피 이 복잡도로는 큰 입력을 처리하기 어렵기 때문에, 이제 더 높은 제약 조건에서도 동작할 수 있도록 접근 방식을 최적화해 보겠습니다.

효율적인 접근법(Efficient Approach)

이 방식에서는 미리 접두사(prefix) 비트 카운트를 계산해 둔 후, 각 쿼리마다 해당 범위 내 숫자들 중 특정 비트가 설정되어 있는지 확인합니다. 설정되어 있다면 답에 해당 비트를 포함하고, 그렇지 않다면 그 비트는 제외합니다.

예제 코드

#include <bits/stdc++.h>

using namespace std;
#define bitt 32
#define MAX (int)10e5

int prefixbits[bitt][MAX];
void bitcount(int *arr, int n) { // 접두사 비트 카운트 생성
   for (int j = 31; j >= 0; j--) {
      prefixbits[j][0] = ((arr[0] >> j) & 1);
      for (int i = 1; i < n; i++) {
         prefixbits[j][i] = arr[i] & (1LL << j);
         prefixbits[j][i] += prefixbits[j][i - 1];
      }
   }
   return;
}
int check(int l, int r) { // 답 계산
   long ans = 0; // 오버플로 방지를 위해 ans를 long으로 선언
   for (int i = 0; i < 32; i++) {
      int x;
      if (l == 0)
         x = prefixbits[i][r];
      else
         x = prefixbits[i][r] - prefixbits[i][l - 1];
      if (x != 0)
         ans = (ans | (1LL << i));
   }
   return ans;
}
int main() {
   int arr[] = {7, 5, 3, 5, 2, 3};
   int n = sizeof(arr) / sizeof(int); // 배열의 크기
   bitcount(arr, n);
   int queries[][2] = {{1, 3}, {4, 5}}; // 주어진 쿼리
   int q = sizeof(queries) / sizeof(queries[0]); // 쿼리의 개수
   for (int i = 0; i < q; i++) {
      cout << check(queries[i][0], queries[i][1]) << "\n";
   }
   return 0;
}

실행 결과

7
3

이 방식의 시간 복잡도는 O(N)입니다(N은 배열의 크기). 따라서 이 접근법은 훨씬 큰 입력 제약 조건에서도 원활하게 동작할 수 있습니다.

코드 설명

이 접근법에서는 먼저 접두사 비트 카운트를 계산하여 저장합니다. 이후 쿼리를 처리할 때는 이 접두사 카운트에서 l-1까지의 비트 카운트를 빼줌으로써 범위 [l, r] 내 숫자들의 비트 카운트를 구합니다. 비트 OR의 성질상, 어떤 숫자에서 특정 비트가 설정되어 있다면 다른 숫자와 OR 연산을 수행해도 해당 비트는 계속 설정된 상태로 유지됩니다. 이러한 성질을 활용하여 비트 카운트가 0이 아니라면, 즉 범위 내에 해당 비트가 설정된 숫자가 존재한다면 답의 그 비트를 설정하고 반복문을 계속 진행한 뒤 최종적으로 답을 출력합니다.

결론

이 글에서는 주어진 배열의 인덱스 범위 [L, R]에 대한 비트 OR 쿼리를 계산하는 문제를 해결했습니다. 또한 이 문제를 위한 C++ 프로그램과 함께 일반 방식과 효율적인 방식 두 가지 접근 방법을 모두 살펴보았습니다. 동일한 프로그램은 C, Java, Python 등 다른 언어로도 작성할 수 있습니다. 이 글이 여러분에게 도움이 되기를 바랍니다.