C ++を使用した、指定された配列のインデックス範囲[L、R]でのビットごとの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]の範囲の数値のビットカウントが得られます。したがって、ビット単位または他の数値を使用すると、ビットは設定されたままになるため、ビット単位のこのプロパティを使用して、ビット数がゼロでないかどうかを確認します。つまり、ビットが設定された数値が範囲内に存在することを意味するため、そのビットを設定します。答えを確認し、ループを続行して、最後に答えを印刷します。

結論

この記事では、指定された配列のインデックス範囲[L、R]でビット単位のORのクエリを計算する問題を解決します。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常および効率的）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。