使用C++查詢給定數組在索引範圍內的位元或操作

在本文中，我們給了一個整數陣列。我們的任務是找到給定範圍內所有數字的位元或，例如，

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

在給定的問題中，我們將使用強力方法來解決它，然後檢查它是否可以適用於更高的約束。如果沒有，那麼我們將優化我們的方法以適應更高的限制。

暴力方法

在這種方法中，我們只需遍歷每個範圍併計算按位或該範圍內的所有數字並打印我們的答案。

範例

#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] 中按位或的查詢的問題給定的數組。我們也學習了解決這個問題的C 程序以及解決這個問題的完整方法（正常且有效率）。我們可以用其他語言像是C、java、python等語言來寫同樣的程式。我們希望這篇文章對您有幫助。

以上是使用C++查詢給定數組在索引範圍內的位元或操作的詳細內容。更多資訊請關注PHP中文網其他相關文章！