資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C++ 在給定陣列的索引範圍 [L, R] 內查詢按位或
在本文中，我們給定一個整數陣列。我們的任務是找到給定範圍內所有數字的按位或，例如：
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] 中數字的位計數。現在我們知道，如果一個位在任何數字中都被設定了，那麼如果你將其與任何其他數字進行按位或運算，該位將保持設定狀態。利用按位或的這一特性，我們檢查位計數是否不為零，這意味著在該範圍內存在一個具有設定位的數字，因此我們將答案的該位設定為 1 並繼續迴圈，最後列印答案。
結論
本文解決了一個問題，即計算給定陣列的索引範圍 [L, R] 內的按位或查詢。我們還學習了此問題的 C++ 程式以及解決此問題的完整方法（普通方法和高效方法）。我們可以用其他語言（如 C、Java、Python 和其他語言）編寫相同的程式。希望本文對您有所幫助。
更新於： 2021年11月26日
888 次瀏覽
廣告