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