#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>

using namespace std;

    void update(int rank, int increment, vector<int>& binaryIndexTree)
	{
	    while (rank < binaryIndexTree.size()) { // Increment the current rank and all higher ranks
	        binaryIndexTree[rank - 1] += increment;
	        rank += (rank & -rank);
	    }
	}
	
	int getValue(int rank, const vector<int>& binaryIndexTree)
	{
	    auto result = 0;
	    while (rank > 0) { // Search the current rank and all lower ranks
	        result += binaryIndexTree[rank - 1]; // Sum any value found into result
            rank -= (rank & -rank);
	    }
	    return result;
	}

int main(void) {
   vector<int> values{ 2, 3, 4, 3, 4, 1 };
   
   // O(n*n) solution
   vector<int> largerNumbers(values.size());
   auto count = 0;

    for (int i = values.size() - 1; i >= 0; --i){
        for (int j = i + 1; j < values.size(); ++j){
            if (values[i] < values[j]){
                largerNumbers[i]++;
                count += largerNumbers[j];
            }
        }
    }
    cout << "O(n*n): " << count << endl;

    // O(nklogn) solution
    int n = values.size(), k = 3; // k is the length of the subsequesnces
    vector<vector<int>> cumBIT(k, vector<int>(n)); // 0 out cumBIT this is the binary tree
    vector<int> temp(n); // Array for sorting
    map<int, int> mapIndex; // This will translate from the value in index to the 1-based count of values less than it
    
    partial_sort_copy(values.cbegin(), values.cend(), temp.begin(), temp.end());

    for(auto i = 0; i < n; ++i){
        mapIndex.insert(make_pair(temp[i], i + 1)); // insert will only allow each number to be added to the map the first time
    }

    vector<vector<int>> binaryIndexTree(k, vector<int>(n)); // A 2D binary index tree with depth k
    auto result = 0;

    for(auto it = values.cbegin(); it != values.cend(); ++it){
        auto rank = mapIndex[*it];
        auto value = 1; // Number of sequences to be added to this rank and all subsequent ranks
        update(rank, value, binaryIndexTree[0]); // Populate the binary index tree for sub-sequences of length 1

        for(auto i = 1; i < k; ++i){ // Itterate over all sub-sequence lengths 2 - k
            value = getValue(rank - 1, binaryIndexTree[i - 1]); // Retrieve all possible shorter sub-sequences of lesser or equal rank
            update(rank, value, binaryIndexTree[i]); // Update the binary index tree for sub sequences of this length
        }
        result += value; // Add the possible sub-sequences of length k for this rank
    }

    cout << "O(nklogn): " << result << endl;
    return 0;
}