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
using System ; using System . Collections . Generic ; class GFG { static int check ( int N ) { if ( N == 0 || ( N & ( N - 1 ) ) != 0 ) return 0 ; return 1 ; } 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 , List < List < int > > Q ) { int [ ] tree = new int [ 4 * N ] ; build_seg_tree ( 0 , N - 1 , 0 , tree , arr ) ; for ( int i = 0 ; i < ( int ) Q . Count ; i ++ ) { if ( Q [ i ] [ 0 ] == 1 ) Console . Write ( 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 ) ; } } static void Main ( ) { int [ ] arr = { 12 , 11 , 16 , 2 , 32 } ; List < List < int > > Q = new List < List < int > > ( ) ; Q . Add ( new List < int > ( new int [ ] { 1 , 0 , 2 } ) ) ; Q . Add ( new List < int > ( new int [ ] { 2 , 4 , 24 } ) ) ; Q . Add ( new List < int > ( new int [ ] { 1 , 1 , 4 } ) ) ; int N = arr . Length ; Query ( arr , N , Q ) ; } }