Queries to count array elements from a given range having a single set bit | package whatever do not write package name here ; 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
import java . io . * ; class GFG { static int check ( int N ) { if ( Integer . bitCount ( N ) == 1 ) return 1 ; else return 0 ; } static 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 ] ; } static 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 ] ; } static 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 ) ; } static void Query ( int arr [ ] , int N , int [ ] [ ] Q ) { int tree [ ] = new int [ 4 * N ] ; build_seg_tree ( 0 , N - 1 , 0 , tree , arr ) ; for ( int i = 0 ; i < Q . length ; i ++ ) { if ( Q [ i ] [ 0 ] == 1 ) System . out . print ( 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 ) ; } } public static void main ( String [ ] args ) { int arr [ ] = { 12 , 11 , 16 , 2 , 32 } ; int [ ] [ ] Q = { { 1 , 0 , 2 } , { 2 , 4 , 24 } , { 1 , 1 , 4 } } ; int N = arr . length ; Query ( arr , N , Q ) ; } }