在本文中，我们给出了一个问题，其中给定一个整数数组，我们的任务是找到给定范围的按位与，例如 7minus；
Input: arr[ ] = {1, 3, 1, 2, 32, 3, 3, 4, 4}, q[ ] = {{0, 1}, {3, 5}}Output:10 01 AND 31 = 123 AND 34 AND 4 = 00Input: arr[ ] = {1, 2, 3, 4, 510, 10 , 12, 16, 8}, q[ ] = {{0, 42}, {1, 33, 4}}Output:0 80
我们将首先应用暴力方法并检查其时间复杂度。如果我们的时间复杂度不够好，我们会尝试开发更好的方法。
暴力方法
在给定的方法中，我们将遍历给定的范围并找到我们的方法回答并打印。
示例
#include 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;}
输出
80
在这种方法中，我们对每个查询的范围运行一个循环，并按位打印它们的集合，因此我们程序的整体复杂性变为O(N*Q)，其中 N 是数组的大小，Q 是我们现在的查询数量，您可以看到这种复杂性不适合更高的约束，因此我们将针对此问题提出更快的方法。
立即学习“C++免费学习笔记（深入）”；
高效方法 h2>
在这个问题中，我们预先计算数组的前缀位数，通过检查给定范围内设置位的贡献来计算给定范围的按位与。
示例
#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 == 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;}
输出
20
在这种方法中，我们使用恒定的时间来计算查询，从而将时间复杂度从 O(N*Q) 大大降低到 O(N)，其中 N 是现在给定数组的大小。该程序也可以适用于更高的约束。
上述代码的说明
在这种方法中，我们计算所有前缀位数并将其存储在索引中。现在，当我们计算查询时，我们只需要检查某个位的计数是否与范围中存在的元素数量相同。如果是，我们在 x 中将此位设置为 1，如果否，我们保留该位，就好像给定范围中存在的任何数字都具有该位 0，因此该位的整个按位 AND 将为零，这就是如何我们正在计算按位与。
结论
在本文中，我们解决了一个问题，枚举给定索引范围 [L, R] 中按位与的所有查询大批。我们还学习了解决这个问题的C++程序以及解决这个问题的完整方法（正常且高效）。我们可以用其他语言比如C、java、python等语言来编写同样的程序。我们希望这篇文章对您有所帮助。
以上就是使用C++，将以下内容翻译为中文：在给定数组的索引范围内进行按位与的查询的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1443862.html
微信扫一扫 
支付宝扫一扫 
