关于逆序数的问题描述如下：

已知数组nums，求新数组count，count[i]代表了在nums[i]右侧且比 nums[i]小的元素个数。
例如:
nums = [5, 2, 6, 1], count = [2, 1, 1, 0];
nums = [6, 6, 6, 1, 1, 1], count = [3, 3, 3, 0, 0, 0];
nums = [5, -7, 9, 1, 3, 5, -2, 1], count = [5, 0, 5, 1, 2, 2, 0, 0];

这里我们使用二叉搜索树实现，可以思考如下：
将nums和count数组都进行逆序，则会有如下结果
nums=[1,-2,5,3,1,9,-7,5],count = [0,0,2,2,1,5,0,5]

此时我们发现，对于nums中的每个元素，只需要确定它的左侧比自己小的元素的个数，这样的结果就可以构造出右侧的count。

自然，我们想到了二叉搜索树的性质，可以画出如下导图：

代码实现如下（文末有完整测试代码）:

/*二叉树数据结构，新增count属性，保存左节点的个数*/
typedef struct tree
{
    int data;
    int count;//保存当前节点有多少个左节点
    struct tree *left;
    struct tree *right;
    tree(int x):data(x),left(NULL),right(NULL),count(0){}
}Tree,*TreeNode;

/*通过二叉树进行计算*/
void insert(Tree *root, Tree *node, int &small_count) {
    if (node -> data <= root ->data) {
        root -> count ++; //当前节点左节点个数累加，因为插入的节点已经比当前节点小了
        if (root -> left) {
            insert(root->left,node, small_count);
        } else {
            root -> left = node;
        }
    } else {
        /*如果大于当前节点，则说明当前节点的所有左节点包括自己都比插入节点小，进行赋值*/
        small_count += root -> count + 1; 
        if (root ->right) {
            insert(root ->right, node, small_count);
        } else {
            root -> right = node;
        }
    }
}


/*获取最终的逆序数组*/
std::vector<int> get_smaller_numbers(std::vector<int> &arr) {
    std::vector<int> count; //逆序后的数组
    std::vector<Tree *> node; //二叉树节点数组
    std::vector<int> result; //最终逆序结果的数组
    Tree *tmp;

    for (int i  = arr.size() - 1;i >= 0; i--) {
        node.push_back(new tree(arr[i]));
    }

    count.push_back(0);
    for (int i = 1;i < arr.size(); ++i) {
        int small_count = 0;
        insert(node[0],node[i],small_count);
        count.push_back(small_count);
    }
    /*对计算好的结果进行逆序，恢复初始结果*/
    for (int i = count.size() - 1; i >= 0; --i) {
        delete node[i];
        result.push_back(count[i]);
    }
    return result;
}

测试代码如下:

#include <iostream>
#include <stack>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


using namespace std;
/*二叉树数据结构*/
typedef struct tree
{
    int data;
    int count;//保存当前节点有多少个左节点
    struct tree *left;
    struct tree *right;
    tree(int x):data(x),left(NULL),right(NULL),count(0){}
}Tree,*TreeNode;

/*通过二叉树进行计算*/
void insert(Tree *root, Tree *node, int &small_count) {
    if (node -> data <= root ->data) {
        root -> count ++;
        if (root -> left) {
            insert(root->left,node, small_count);
        } else {
            root -> left = node;
        }
    } else {
        small_count += root -> count + 1;
        if (root ->right) {
            insert(root ->right, node, small_count);
        } else {
            root -> right = node;
        }
    }
}

std::vector<int> get_smaller_numbers(std::vector<int> &arr) {
    std::vector<int> count; //逆序后的数组
    std::vector<Tree *> node; //二叉树节点数组
    std::vector<int> result; //最终逆序结果的数组
    Tree *tmp;

    for (int i  = arr.size() - 1;i >= 0; i--) {
        node.push_back(new tree(arr[i]));
    }

    count.push_back(0);
    for (int i = 1;i < arr.size(); ++i) {
        int small_count = 0;
        insert(node[0],node[i],small_count);
        count.push_back(small_count);
    }
    /*对计算好的结果进行逆序，恢复初始结果*/
    for (int i = count.size() - 1; i >= 0; --i) {
        delete node[i];
        result.push_back(count[i]);
    }
    return result;
}

int main(int argc, char const *argv[])
{
    int test[] = {5,-7,9,1,3,5,-2,1};
    std::vector<int> num;
    for (int i = 0;i < 8; ++i) {
        num.push_back(test[i]);
    }

    std::vector<int> result;
    result = get_smaller_numbers(num);
    for (int i = 0;i < result.size(); ++i) {
        cout << "[" << result[i] << "] ";
    }
    return 0;
}

输出结果如下:

[5] [0] [5] [1] [2] [2] [0] [0]