Count number of increasing sub | Javascript implementation of the approach ; Segment tree array ; Function for point update inVal 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
var N = 10000 ; var seg = Array ( 3 * N ) . fill ( 0 ) ; function update ( inVal , l , r , up_in , val ) { if ( r < up_in l > up_in ) return seg [ inVal ] ; if ( l == up_in && r == up_in ) return seg [ inVal ] = val ; var m = parseInt ( ( l + r ) / 2 ) ; seg [ inVal ] = update ( 2 * inVal + 1 , l , m , up_in , val ) + update ( 2 * inVal + 2 , m + 1 , r , up_in , val ) ; return seg [ inVal ] ; } function query ( inVal , l , r , l1 , r1 ) { if ( l > r ) return 0 ; if ( r < l1 l > r1 ) return 0 ; if ( l1 <= l && r <= r1 ) return seg [ inVal ] ; var m = parseInt ( ( l + r ) / 2 ) ; return query ( 2 * inVal + 1 , l , m , l1 , r1 ) + query ( 2 * inVal + 2 , m + 1 , r , l1 , r1 ) ; } function findCnt ( arr , n ) { var brr = Array ( n ) ; for ( var i = 0 ; i < n ; i ++ ) brr [ i ] = arr [ i ] ; brr . sort ( ( a , b ) => a - b ) ; var r = new Map ( ) ; for ( var i = 0 ; i < n ; i ++ ) r [ brr [ i ] ] = i + 1 ; var dp = Array ( n ) . fill ( 0 ) ; var ans = 0 ; for ( var i = n - 1 ; i >= 0 ; i -- ) { var rank = r [ arr [ i ] ] ; dp [ i ] = 1 + query ( 0 , 0 , n - 1 , rank , n - 1 ) ; ans += dp [ i ] ; update ( 0 , 0 , n - 1 , rank - 1 , dp [ i ] + query ( 0 , 0 , n - 1 , rank - 1 , rank - 1 ) ) ; } return ans ; } var arr = [ 1 , 2 , 10 , 9 ] ; var n = arr . length ; document . write ( findCnt ( arr , n ) ) ;