在本文中，我们给出了一个整数数组。我们的任务是找到给定范围内所有数字的按位或，例如，
Input: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}Output:371 OR 3 = 32 OR 3 OR 4 = 7Input: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}Output:77
在给定的问题中，我们将使用强力方法来解决它，然后检查它是否可以适用于更高的约束。如果没有，那么我们将优化我们的方法以适应更高的约束。
暴力方法
在这种方法中，我们只需遍历每个范围并计算按位或该范围内的所有数字并打印我们的答案。
示例
#include 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;}
输出
73
这种方法的时间复杂度为 O(N*Q)，其中 N 是数组的大小，Q 是现在的查询数量，如您所见，这种复杂性不适用于更高的约束，所以现在我们将优化我们的方法，使其也适用于更高的约束。
立即学习“C++免费学习笔记（深入）”；
高效方法
在这种方法中，我们将计算前缀位数，然后检查是否数字有一个特定的位集。如果是，那么我们将这一点放入答案中；否则，我们保留这一点。
示例
#include using namespace std;#define bitt 32#define MAX (int)10e5int 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;}
输出
73
此方法的时间复杂度为 O(N)，其中 N 是数组的大小，因此此方法可以适用于更高的约束。
说明上面的代码
在这种方法中，我们计算前缀位数并存储它。现在我们计算一个查询，我们遍历该前缀计数并删除 l-1 的位计数，这样我们就有 [l, r] 范围内数字的位计数，因为我们知道如果在任何数字中设置了一个位因此，如果您将其与任何其他数字进行按位或，则该位将保持设置状态，因此使用按位或的此属性，我们检查位计数是否不为零，这意味着范围内存在具有设置位的数字，因此我们设置该位答案并继续循环，最后打印答案。
结论
本文解决了计算索引范围 [L, R] 中按位或的查询的问题给定的数组。我们还学习了解决这个问题的C++程序以及解决这个问题的完整方法（正常且高效）。我们可以用其他语言比如C、java、python等语言来编写同样的程序。我们希望这篇文章对您有所帮助。
以上就是使用C++查询给定数组在索引范围内的按位或操作的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445636.html
微信扫一扫 
支付宝扫一扫 
