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
def check ( N ) : NEW_LINE INDENT if ( N == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT return ( ( N & ( N - 1 ) ) == 0 ) NEW_LINE DEDENT def build_seg_tree ( ss , se , si , tree , arr ) : NEW_LINE INDENT if ( ss == se ) : NEW_LINE INDENT tree [ si ] = check ( arr [ ss ] ) NEW_LINE return NEW_LINE DEDENT mid = ( ss + se ) // 2 NEW_LINE build_seg_tree ( ss , mid , 2 * si + 1 , tree , arr ) NEW_LINE build_seg_tree ( mid + 1 , se , 2 * si + 2 , tree , arr ) NEW_LINE tree [ si ] = tree [ 2 * si + 1 ] + tree [ 2 * si + 2 ] NEW_LINE DEDENT def update ( ss , se , si , X , V , tree , arr ) : NEW_LINE INDENT if ( ss == se ) : NEW_LINE INDENT if ( ss == X ) : NEW_LINE INDENT arr [ X ] = V NEW_LINE tree [ si ] = check ( V ) NEW_LINE DEDENT return NEW_LINE DEDENT mid = ( ss + se ) // 2 NEW_LINE if ( X <= mid ) : NEW_LINE INDENT update ( ss , mid , 2 * si + 1 , X , V , tree , arr ) NEW_LINE DEDENT else : NEW_LINE INDENT update ( mid + 1 , se , 2 * si + 2 , X , V , tree , arr ) NEW_LINE DEDENT tree [ si ] = tree [ 2 * si + 1 ] + tree [ 2 * si + 2 ] NEW_LINE DEDENT def query ( l , r , ss , se , si , tree ) : NEW_LINE INDENT if ( r < ss or l > se ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( l <= ss and r >= se ) : NEW_LINE INDENT return tree [ si ] NEW_LINE DEDENT mid = ( ss + se ) // 2 NEW_LINE return ( query ( l , r , ss , mid , 2 * si + 1 , tree ) + query ( l , r , mid + 1 , se , 2 * si + 2 , tree ) ) NEW_LINE DEDENT def Query ( arr , N , Q ) : NEW_LINE INDENT tree = [ 0 ] * ( 4 * N ) NEW_LINE build_seg_tree ( 0 , N - 1 , 0 , tree , arr ) NEW_LINE for i in range ( len ( Q ) ) : NEW_LINE INDENT if ( Q [ i ] [ 0 ] == 1 ) : NEW_LINE INDENT print ( query ( Q [ i ] [ 1 ] , Q [ i ] [ 2 ] , 0 , N - 1 , 0 , tree ) , end = " ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT update ( 0 , N - 1 , 0 , Q [ i ] [ 1 ] , Q [ i ] [ 2 ] , tree , arr ) NEW_LINE DEDENT DEDENT DEDENT arr = [ 12 , 11 , 16 , 2 , 32 ] NEW_LINE Q = [ [ 1 , 0 , 2 ] , [ 2 , 4 , 24 ] , [ 1 , 1 , 4 ] ] NEW_LINE N = len ( arr ) NEW_LINE Query ( arr , N , Q ) NEW_LINE