数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告