
在本文中,我们将讨论一个问题,即找到给定范围内具有第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>
using namespace std;
#define MAX_BITS 32
bool Kset(int n, int k) { // to check if kth bit is set
if (n & (1 <h2>输出</h2>
<pre class="brush:php;toolbar:false;">0
1
上述方法的时间复杂度为O(N*Q),其中N是数组的大小,Q是给定的查询数量;如您所见,这种方法对于更高的约束条件不适用,因为它将花费太多时间,所以现在我们将尝试制作一个高效的程序。
高效的方法
在这种方法中,我们将维护一个二维前缀和数组,该数组将保持每个索引位置使用的位数,并且我们可以在O(1)的复杂度中计算出答案。
示例
#include<bits>
using namespace std;
#define bits 32 // number of bits
int P[100000][bits+1];
bool Kset(int n, int k) {
if (n & (1 <h2>输出</h2>
<pre class="brush:php;toolbar:false;">2
3
由于我们正在维护帮助我们以O(1)的时间复杂度找到答案的前缀数组,所以我们的时间复杂度大大降低到了O(N),其中N是给定数组的大小。
上述代码的解释
在这个程序中,我们为数组的每个索引维护一个前缀计数器,用于计算该索引之前使用的每个位数。现在,我们已经存储了每个位数的前缀计数,所以对于第k位的计数,我们需要用第R索引处的第k位的前缀计数减去第L-1索引处的第k位的前缀计数,这就是我们的答案。
结论
在本文中,我们解决了一个问题,即解决具有第K位设置的范围内数组元素的查询。我们还学习了这个问题的C++程序以及我们解决这个问题的完整方法(普通和高效)。我们可以用其他语言(如C、Java、Python和其他语言)编写相同的程序。希望您会觉得这篇文章有帮助。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











