使用 C++ 查询具有第 K 位设置的范围内的数组元素数
在本文中，我们将讨论找到给定范围内存在第k位设置的元素数量的问题，例如-
Input : arr[] = { 4, 5, 7, 2 }
Query 1: L = 2, R = 4, K = 4
Query 2: L = 3, R = 5, K = 1
Output :
0
1我们将通过蛮力方法解决这个问题，看看这种方法是否适用于更高的约束。如果没有，那么我们尝试考虑一种新的有效方法。
蛮力方法
在这种方法中，我们将简单地遍历范围并检查每个元素是否设置了第k位，如果是，则增加计数。
示例
#include<bits/stdc++.h>
using namespace std;
#define MAX_BITS 32
bool Kset(int n, int k) { //检查是否设置了第k位
if (n & (1 << (k - 1)))
return true;
return false;
}
int query(int L, int R, int K, int arr[]) {
int count = 0; //计数器以保持范围内的数字计数
for (int i = L; i <= R; i++) { //穿越范围
if (Kset(arr[i], K)) {
count++;
}
}
return count;
}
int main() {
int arr[] = { 4, 5, 7, 2 }; //给定数组
int n = sizeof(arr) / sizeof(arr[0]); //我们数组的大小
int queries[][3] = { //给定L、R和k
{ 2, 4, 4 },
{ 3, 5, 1 }
};
int q = sizeof(queries) / sizeof(queries[0]); //查询次数
for (int i = 0; i < q; i++) {
int L = queries[i][0] - 1;
int R = queries[i][1] - 1;
int K = queries[i][2];
cout << query(L, R, K, arr) << "\n";
}
return 0;
}输出结果0 1
上述方法的时间复杂度为O(N*Q)，其中N是我们数组的大小，Q是我们现在给出的查询数量；如您所见，这种方法不适合更高的约束，因为它会花费太多时间，所以现在我们将尝试制定一个有效方法的程序。
有效的方法
在这种方法中，我们将维护一个二维前缀和数组，该数组将保留使用到每个索引的每一位的计数，然后我们可以以O(1)复杂度计算答案。
示例
#include<bits/stdc++.h>
using namespace std;
#define bits 32 //位数
int P[100000][bits+1];
bool Kset(int n, int k) {
if (n & (1 << (k - 1)))
return true;
return false;
}
void prefixArray(int n, int arr[]) { //构建前缀数组
for (int i = 0; i <= bits; i++) {
P[0][i] = 0; //设置每一位初始计数=0
}
for (int i = 0; i < n; i++) {
for (int j = 1; j <= bits; j++) {
bool flag = Kset(arr[i], j);
if (i) //我们将先前的计数添加到最新的计数
P[i][j] = P[i - 1][j];
if (flag) { //如果设置了第j位，则我们增加计数
P[i][j]++;
}
}
}
}
int query(int L, int R, int K) {
if (L) //如果L不等于0，那么我们返回R处的前缀减去L-1处的前缀
return P[R][K] - P[L - 1][K];
else
return P[R][K];
}
int main() {
int arr[] = { 8, 9, 1, 3 }; //给定数组
int n = sizeof(arr) / sizeof(arr[0]); //给定数组的大小
int queries[][3] = {
{ 1, 3, 4 },
{ 2, 4, 1 }
};
prefixArray(n, arr); //调用函数创建前缀数组
int q = sizeof(queries) / sizeof(queries[0]); //查询次数
for (int i = 0; i < q; i++) {
int L = queries[i][0] - 1;
int R = queries[i][1] - 1;
int K = queries[i][2];
cout << query(L, R, K) << "\n";
}
return 0;
}输出结果2 3
由于我们正在维护帮助我们在O(1)中找到答案的前缀数组，因此，我们的时间复杂度大大降低到O(N)，其中N是给定数组的大小。
上面代码的解释
在这个程序中，我们为数组的每个索引维护一个前缀计数器，它计算索引之前使用的每个位。我们现在为我们的数组构建这个计数，因为我们已经存储了每一位的前缀计数，所以对于第k位计数，我们需要减去第k位的前缀计数直到R索引与第k位的前缀计数直到L-1指数，这就是我们的答案。
结论
在本文中，我们解决了一个问题，以解决对具有第K位集的范围内数组元素数量的查询。我们还学习了针对这个问题的C++程序以及我们解决这个问题的完整方法（普通和高效）problem.We可以用其他语言（例如C、java、python和其他语言）编写相同的程序。我们希望这篇文章对您有所帮助。