Range query for count of set bits | C ++ program to Range query for Count number of set bits ; 2 - D array that will stored the count of bits set in element of array ; Function store the set bit count in BitCount Array ; traverse over all bits ; mark elements with i 'th bit set ; Check whether the current bit is set or not if it 's set then mark it. ; store cumulative sum of bits ; Function to process queries ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int BitCount [ 10000 ] = { 0 } ; void fillSetBitsMatrix ( int arr [ ] , int n ) { for ( int i = 0 ; i < 32 ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { long temp = arr [ j ] >> i ; if ( temp % 2 != 0 ) BitCount [ j ] += 1 ; } } for ( int i = 1 ; i < n ; i ++ ) BitCount [ i ] += BitCount [ i - 1 ] ; } void Query ( int Q [ ] [ 2 ] , int q ) { for ( int i = 0 ; i < q ; i ++ ) cout << ( BitCount [ Q [ i ] [ 1 ] ] - BitCount [ Q [ i ] [ 0 ] - 1 ] ) << endl ; } int main ( ) { int Arr [ ] = { 1 , 5 , 6 , 10 , 9 , 4 , 67 } ; int n = sizeof ( Arr ) / sizeof ( Arr [ 0 ] ) ; fillSetBitsMatrix ( Arr , n ) ; int q = 2 ; int Q [ 2 ] [ 2 ] = { { 1 , 5 } , { 2 , 6 } } ; Query ( Q , q ) ; return 0 ; }