Template Function ADS::smallerToTheRight

• Defined in File SequenceQueries.h

Function Documentation

template<class T, class C = std::less<>>
std::vector<std::size_t> ADS::smallerToTheRight(const std::vector<T> &A, C less = C())

smallerToTheRight(): c[ i ], the number of j > i with A[ j ] < A[ i ], by mergesort on the places; O( n log n )

Post:

the sum of c is the number of inversions of A (an audit)