使用C++，將以下內容翻譯為中文：在給定數組的索引範圍內進行位元與的查詢

在本文中，我們給出了一個問題，其中給定一個整數數組，我們的任務是找到給定範圍的按位與，例如7minus；

Input: arr[ ] = {1, 3, 1, 2, 32, 3, 3, 4, 4}, q[ ] = {{0, 1}, {3, 5}}
Output:
1
0 0
1 AND 31 = 1
23 AND 34 AND 4 = 00
Input: arr[ ] = {1, 2, 3, 4, 510, 10 , 12, 16, 8}, q[ ] = {{0, 42}, {1, 33, 4}}
Output:
0 8
0

我們將首先應用暴力方法並檢查其時間複雜度。如果我們的時間複雜度不夠好，我們會嘗試開發更好的方法。

暴力方法

在給定的方法中，我們將遍歷給定的範圍並找到我們的方法回答並列印。

範例

#include <bits/stdc++.h>
using namespace std;
int main() {
   int ARR[] = { 10, 10 , 12, 16, 8 };
   int n = sizeof(ARR) / sizeof(int); // size of our array
   int queries[][2] = { {0, 2}, {3, 4} }; // 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 = 1LL << 32;
      ans -= 1; // making all the bits of ans 1
      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;
}

輸出

8
0

在這個方法中，我們對每個查詢的範圍運行一個循環，並按位元列印它們的集合，因此我們程序的整體複雜度變成O(N*Q)，其中N 是陣列的大小，Q 是我們現在的查詢數量，您可以看到這種複雜性不適合更高的約束，因此我們將針對此問題提出更快的方法。

高效方法 h2>

在這個問題中，我們預先計算數組的前綴位數，透過檢查給定範圍內設定位的貢獻來計算給定範圍的位元與。

範例

#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 == r - l + 1)
         ans = ans | 1LL << i;
      }
   return ans;
}
int main() {
   int ARR[] = { 10, 10 , 12, 16, 8 };
   int n = sizeof(ARR) / sizeof(int); // size of our array
   memset(prefixbits, 0, sizeof(prefixbits)); // initializing all the elements with 0
   bitcount(ARR, n);
   int queries[][2] = {{0, 2}, {3, 4}}; // 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;
}

輸出

2
0

在這個方法中，我們使用恆定的時間來計算查詢，從而將時間複雜度從O(N* Q) 大幅降低到O(N)，其中N 是現在給定陣列的大小。該程式也可以適用於更高的約束。

上述程式碼的說明

在這種方法中，我們計算所有前綴位數並將其儲存在索引中。現在，當我們計算查詢時，我們只需要檢查某個位元的計數是否與範圍中存在的元素數量相同。如果是，我們在x 中將此位設為1，如果否，我們保留該位，就好像給定範圍中存在的任何數字都具有該位0，因此該位的整個按位AND 將為零，這就是如何我們正在計算按位與。

結論

在本文中，我們解決了一個問題，枚舉給定索引範圍 [L, R] 中按位與的所有查詢大批。我們也學習了解決這個問題的C 程序以及解決這個問題的完整方法（正常且有效率）。我們可以用其他語言像是C、java、python等語言來寫同樣的程式。我們希望這篇文章對您有幫助。

以上是使用C++，將以下內容翻譯為中文：在給定數組的索引範圍內進行位元與的查詢的詳細內容。更多資訊請關注PHP中文網其他相關文章！