Find the count of distinct numbers in a range | Function to perform queries in a range ; No overlap ; Totally Overlap ; Partial Overlap ; Finding the Answer for the left Child ; Finding the Answer for the right Child ; Combining the BitMasks ; Function to perform update operation in the Segment seg ; Forming the BitMask ; Updating the left Child ; Updating the right Child ; Updating the BitMask ; Building the Segment Tree ; Building the Initial BitMask ; Building the left seg tree ; Building the right seg tree ; Forming the BitMask ; Utility Function to answer the queries ; Counting the set bits which denote the distinct elements ; Updating the value ; Driver Code
def query ( start , end , left , right , node , seg ) : NEW_LINE INDENT if ( end < left or start > right ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT elif ( start >= left and end <= right ) : NEW_LINE INDENT return seg [ node ] NEW_LINE DEDENT else : NEW_LINE INDENT mid = ( start + end ) // 2 NEW_LINE leftChild = query ( start , mid , left , right , 2 * node , seg ) NEW_LINE rightChild = query ( mid + 1 , end , left , right , 2 * node + 1 , seg ) NEW_LINE return ( leftChild rightChild ) NEW_LINE DEDENT DEDENT def update ( left , right , index , Value , node , ar , seg ) : NEW_LINE INDENT if ( left == right ) : NEW_LINE INDENT ar [ index ] = Value NEW_LINE seg [ node ] = ( 1 << Value ) NEW_LINE return NEW_LINE DEDENT mid = ( left + right ) // 2 NEW_LINE if ( index > mid ) : NEW_LINE INDENT update ( mid + 1 , right , index , Value , 2 * node + 1 , ar , seg ) NEW_LINE DEDENT else : NEW_LINE INDENT update ( left , mid , index , Value , 2 * node , ar , seg ) NEW_LINE DEDENT seg [ node ] = ( seg [ 2 * node ] seg [ 2 * node + 1 ] ) NEW_LINE DEDENT def build ( left , right , node , ar , eg ) : NEW_LINE INDENT if ( left == right ) : NEW_LINE INDENT seg [ node ] = ( 1 << ar [ left ] ) NEW_LINE return NEW_LINE DEDENT mid = ( left + right ) // 2 NEW_LINE build ( left , mid , 2 * node , ar , seg ) NEW_LINE build ( mid + 1 , right , 2 * node + 1 , ar , seg ) NEW_LINE seg [ node ] = ( seg [ 2 * node ] seg [ 2 * node + 1 ] ) NEW_LINE DEDENT def getDistinctCount ( queries , ar , seg , n ) : NEW_LINE INDENT for i in range ( len ( queries ) ) : NEW_LINE INDENT op = queries [ i ] [ 0 ] NEW_LINE if ( op == 2 ) : NEW_LINE INDENT l = queries [ i ] [ 1 ] NEW_LINE r = queries [ i ] [ 2 ] NEW_LINE tempMask = query ( 0 , n - 1 , l - 1 , r - 1 , 1 , seg ) NEW_LINE countOfBits = 0 NEW_LINE for i in range ( 63 , - 1 , - 1 ) : NEW_LINE INDENT if ( tempMask & ( 1 << i ) ) : NEW_LINE INDENT countOfBits += 1 NEW_LINE DEDENT DEDENT print ( countOfBits ) NEW_LINE DEDENT else : NEW_LINE INDENT index = queries [ i ] [ 1 ] NEW_LINE val = queries [ i ] [ 2 ] NEW_LINE update ( 0 , n - 1 , index - 1 , val , 1 , ar , seg ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 7 NEW_LINE ar = [ 1 , 2 , 1 , 3 , 1 , 2 , 1 ] NEW_LINE seg = [ 0 ] * 4 * n NEW_LINE build ( 0 , n - 1 , 1 , ar , seg ) NEW_LINE q = 5 NEW_LINE queries = [ [ 2 , 1 , 4 ] , [ 1 , 4 , 2 ] , [ 1 , 5 , 2 ] , [ 2 , 4 , 6 ] , [ 2 , 1 , 7 ] ] NEW_LINE getDistinctCount ( queries , ar , seg , n ) NEW_LINE DEDENT