Count number of increasing sub | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  10000 NEW_LINE int seg [ 3 * N ] ; int update ( int in , int l , int r , int up_in , int val ) { if ( r < up_in l > up_in ) return seg [ in ] ; if ( l == up_in and r == up_in ) return seg [ in ] = val ; int m = ( l + r ) / 2 ; return seg [ in ] = update ( 2 * in + 1 , l , m , up_in , val ) + update ( 2 * in + 2 , m + 1 , r , up_in , val ) ; } int query ( int in , int l , int r , int l1 , int r1 ) { if ( l > r ) return 0 ; if ( r < l1 l > r1 ) return 0 ; if ( l1 <= l and r <= r1 ) return seg [ in ] ; int m = ( l + r ) / 2 ; return query ( 2 * in + 1 , l , m , l1 , r1 ) + query ( 2 * in + 2 , m + 1 , r , l1 , r1 ) ; } int findCnt ( int * arr , int n ) { int brr [ n ] ; for ( int i = 0 ; i < n ; i ++ ) brr [ i ] = arr [ i ] ; sort ( brr , brr + n ) ; map < int , int > r ; for ( int i = 0 ; i < n ; i ++ ) r [ brr [ i ] ] = i + 1 ; int dp [ n ] = { 0 } ; int ans = 0 ; for ( int i = n - 1 ; i >= 0 ; i -- ) { int 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 ; } int main ( ) { int arr [ ] = { 1 , 2 , 10 , 9 } ; int n = sizeof ( arr ) / sizeof ( int ) ; cout << findCnt ( arr , n ) ; return 0 ; }