C++를 사용하여 주어진 배열의 인덱스 범위 [L, R]에서 Bitwise OR에 대한 쿼리

이 기사에서는 정수 배열이 제공됩니다. 우리는 주어진 범위에 있는 모든 숫자의 비트 OR을 찾는 임무를 받았습니다. 예를 들어,

Input: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
Output:
3
7
1 OR 3 = 3
2 OR 3 OR 4 = 7
Input: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
Output:
7
7

주어진 문제에서 무차별 대입 접근 방식으로 접근한 다음 더 높은 제약 조건에서 작동할 수 있는지 여부를 확인합니다. 그렇지 않은 경우 더 높은 제약 조건에서도 작동하도록 접근 방식을 최적화할 것입니다.

무차별 대입 접근

이 접근 방식에서는 단순히 각 범위를 탐색하고 해당 범위에 있는 모든 숫자의 비트 OR을 계산하고 답을 인쇄합니다.

예시

#include <bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = { 7, 5, 3, 5, 2, 3 };
   int n = sizeof(arr) / sizeof(int); // size of our array
   int queries[][2] = { { 1, 3 }, { 4, 5 } }; // given queries
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries
   for(int i = 0; i < q; i++) { // traversing through all the queries
      long ans = 0;
      for(int j = queries[i][0]; j <= queries[i][1]; j++) // traversing through the range
         ans |= arr[j]; // calculating the answer
      cout << ans << "\n";
   }
   return 0;
}

출력

7
3

이 접근 방식은 O(N*Q)의 시간 복잡도를 가지고 있습니다. 여기서 N은 배열의 크기이고 Q는 현재 볼 수 있는 쿼리 수입니다. 이 복잡성은 더 높은 제약 조건에서는 작동하지 않으므로 이제 접근 방식을 최적화합니다. 더 높은 제약 조건에서도 작동하도록 합니다.

효율적인 접근

이 접근 방식에서는 접두사 비트 수를 계산한 다음 숫자 중 하나에 특정 비트 세트가 있는지 여부를 확인합니다. 그렇다면 이 비트를 답에 넣습니다. 그렇지 않으면 이 비트를 남겨둡니다.

예시

#include <bits/stdc++.h>

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

int prefixbits[bitt][MAX];
void bitcount(int *arr, int n) { // making prefix counts
   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) { // calculating the answer
   long ans = 0; // to avoid overflow we are taking ans as 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); // size of our array
   bitcount(arr, n);
   int queries[][2] = {{1, 3}, {4, 5}}; // given queries
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries
   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++ 프로그램과 이 문제를 해결하는 완전한 접근 방식( Normal 및 Efficient)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.