Queries to count array elements from a given range having a single set bit | C ++ implementation for above approach ; Check if N has only one set bit ; Function to build segment tree ; If se is leaf node ; Update the node ; Stores mid value of segment [ ss , se ] ; Recursive call for left Subtree ; Recursive call for right Subtree ; Update the Current Node ; Function to update a value at Xth index ; If ss is equal to X ; Update the Xth node ; Update the tree ; Stores the mid of segment [ ss , se ] ; Update current node ; Count of numbers having one set bit ; If L > se or R < ss Invalid Range ; If [ ss , se ] lies inside the [ L , R ] ; Stores the mid of segment [ ss , se ] ; Return the sum after recursively traversing left and right subtree ; Function to solve queries ; Initialise Segment tree ; Build segment tree ; Perform queries ; Driver Code ; Input ; Function call to solve queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool check ( int N ) { if ( N == 0 ) return 0 ; return ! ( N & ( N - 1 ) ) ; } void build_seg_tree ( int ss , int se , int si , int tree [ ] , int arr [ ] ) { if ( ss == se ) { tree [ si ] = check ( arr [ ss ] ) ; return ; } int mid = ( ss + se ) / 2 ; build_seg_tree ( ss , mid , 2 * si + 1 , tree , arr ) ; build_seg_tree ( mid + 1 , se , 2 * si + 2 , tree , arr ) ; tree [ si ] = tree [ 2 * si + 1 ] + tree [ 2 * si + 2 ] ; } void update ( int ss , int se , int si , int X , int V , int tree [ ] , int arr [ ] ) { if ( ss == se ) { if ( ss == X ) { arr [ X ] = V ; tree [ si ] = check ( V ) ; } return ; } int mid = ( ss + se ) / 2 ; if ( X <= mid ) update ( ss , mid , 2 * si + 1 , X , V , tree , arr ) ; else update ( mid + 1 , se , 2 * si + 2 , X , V , tree , arr ) ; tree [ si ] = tree [ 2 * si + 1 ] + tree [ 2 * si + 2 ] ; } int query ( int l , int r , int ss , int se , int si , int tree [ ] ) { if ( r < ss l > se ) return 0 ; if ( l <= ss && r >= se ) return tree [ si ] ; int mid = ( ss + se ) / 2 ; return query ( l , r , ss , mid , 2 * si + 1 , tree ) + query ( l , r , mid + 1 , se , 2 * si + 2 , tree ) ; } void Query ( int arr [ ] , int N , vector < vector < int > > Q ) { int tree [ 4 * N ] = { 0 } ; build_seg_tree ( 0 , N - 1 , 0 , tree , arr ) ; for ( int i = 0 ; i < ( int ) Q . size ( ) ; i ++ ) { if ( Q [ i ] [ 0 ] == 1 ) cout << query ( Q [ i ] [ 1 ] , Q [ i ] [ 2 ] , 0 , N - 1 , 0 , tree ) << " ▁ " ; else update ( 0 , N - 1 , 0 , Q [ i ] [ 1 ] , Q [ i ] [ 2 ] , tree , arr ) ; } } int main ( ) { int arr [ ] = { 12 , 11 , 16 , 2 , 32 } ; vector < vector < int > > Q { { 1 , 0 , 2 } , { 2 , 4 , 24 } , { 1 , 1 , 4 } } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; Query ( arr , N , Q ) ; return 0 ; }