Count number of increasing sub | Python3 implementation of the approach ; Segment tree array ; Function for point update in segment tree ; Base case ; If l == r == up ; Mid element ; Updating the segment tree ; Function for the range sum - query ; Base case ; Mid element ; CallIng for the left and the right subtree ; Function to return the count ; Copying array arr to sort it ; Sorting array brr ; Map to store the rank of each element ; dp array ; To store the final answer ; Updating the dp array ; Rank of the element ; Solving the dp - states using segment tree ; UpdatIng the final answer ; Updating the segment tree ; Returning the final answer ; Driver code
N = 10000 NEW_LINE seg = [ 0 ] * ( 3 * N ) NEW_LINE def update ( In , l , r , up_In , val ) : NEW_LINE INDENT if ( r < up_In or l > up_In ) : NEW_LINE INDENT return seg [ In ] NEW_LINE DEDENT if ( l == up_In and r == up_In ) : NEW_LINE INDENT seg [ In ] = val NEW_LINE return val NEW_LINE DEDENT m = ( l + r ) // 2 NEW_LINE seg [ In ] = update ( 2 * In + 1 , l , m , up_In , val ) + update ( 2 * In + 2 , m + 1 , r , up_In , val ) NEW_LINE return seg [ In ] NEW_LINE DEDENT def query ( In , l , r , l1 , r1 ) : NEW_LINE INDENT if ( l > r ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( r < l1 or l > r1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( l1 <= l and r <= r1 ) : NEW_LINE INDENT return seg [ In ] NEW_LINE DEDENT m = ( l + r ) // 2 NEW_LINE return query ( 2 * In + 1 , l , m , l1 , r1 ) + query ( 2 * In + 2 , m + 1 , r , l1 , r1 ) NEW_LINE DEDENT def fIndCnt ( arr , n ) : NEW_LINE INDENT brr = [ 0 ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT brr [ i ] = arr [ i ] NEW_LINE DEDENT brr = sorted ( brr ) NEW_LINE r = dict ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT r [ brr [ i ] ] = i + 1 NEW_LINE DEDENT dp = [ 0 ] * n NEW_LINE ans = 0 NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT rank = r [ arr [ i ] ] NEW_LINE dp [ i ] = 1 + query ( 0 , 0 , n - 1 , rank , n - 1 ) NEW_LINE ans += dp [ i ] NEW_LINE update ( 0 , 0 , n - 1 , rank - 1 , dp [ i ] + query ( 0 , 0 , n - 1 , rank - 1 , rank - 1 ) ) NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ 1 , 2 , 10 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE print ( fIndCnt ( arr , n ) ) NEW_LINE