資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C++ 查詢給定陣列索引範圍 [L, R] 內的按位與
在本文中，我們提出了一個問題，其中給定一個整數陣列，我們的任務是找到給定範圍的按位與，例如：
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 是查詢的數量。正如你所看到的，這種複雜度對於更高的約束條件並不適用，因此我們將為此問題提出一種更快的演算法。
高效方法
在這個問題中，我們預先計算陣列的字首位計數，透過檢查給定範圍內設定位的貢獻來計算給定範圍的按位與。
示例
#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，則該位的整個按位與將為零，這就是我們計算按位與的方式。
結論
在本文中，我們解決了一個問題，即列舉給定陣列索引範圍 [L, R] 內所有按位與的查詢。我們還學習了此問題的 C++ 程式以及我們用來解決此問題的完整方法（常規方法和高效方法）。我們可以用 C、Java、Python 等其他語言編寫相同的程式。希望本文對您有所幫助。
更新於：2021年11月26日
1K+ 次瀏覽
廣告