Queries to count array elements from a given range having a single set bit | 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 ; Input ; Function call to solve queries
function check ( N ) { if ( N == 0 ) return 0 ; return ! ( N & ( N - 1 ) ) ; } function build_seg_tree ( ss , se , si , tree , arr ) { if ( ss == se ) { tree [ si ] = check ( arr [ ss ] ) ; return ; } var mid = parseInt ( ( 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 ] ; } function update ( ss , se , si , X , V , tree , arr ) { if ( ss == se ) { if ( ss == X ) { arr [ X ] = V ; tree [ si ] = check ( V ) ; } return ; } var mid = parseInt ( ( 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 ] ; } function query ( l , r , ss , se , si , tree ) { if ( r < ss l > se ) return 0 ; if ( l <= ss && r >= se ) return tree [ si ] ; var mid = parseInt ( ( ss + se ) / 2 ) ; return query ( l , r , ss , mid , 2 * si + 1 , tree ) + query ( l , r , mid + 1 , se , 2 * si + 2 , tree ) ; } function Query ( arr , N , Q ) { var tree = new Array ( 4 * N ) ; tree . fill ( 0 ) ; build_seg_tree ( 0 , N - 1 , 0 , tree , arr ) ; for ( var i = 0 ; i < Q . length ; i ++ ) { if ( Q [ i ] [ 0 ] == 1 ) document . 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 ) ; } } var arr = [ 12 , 11 , 16 , 2 , 32 ] ; var Q = [ [ 1 , 0 , 2 ] , [ 2 , 4 , 24 ] , [ 1 , 1 , 4 ] ] ; var N = arr . length ; Query ( arr , N , Q ) ;