在本文中，我们将讨论找到给定范围内存在第 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 和其他语言）编写相同的程序。我们希望这篇文章对您有所帮助。