题解 | #维护x的秩#

要求随着数字的到来统计之前所有比当前小的数字的数目
通过维护一棵二叉搜索树来实现，树的节点增加一个域Count用于统计左孩子节点的总数
即：比当前节点更小的节点的数目

那么一个新的数字A[i]，从根节点开始插入
如果大于某节点，那么其最终ans[i]+=count+1
即：累加上某节点以及该节点所有左孩子节点的总数
如果小于某节点，那么当前节点的count+=1

在插入的过程中即可完成ans[]数组的填充，需要注意左右孩子为NULL的情形。

struct treenode
{
    int val;//当前节点值
    int count;//当前节点左子树节点数目  用于计算比当前val小的节点的数目
    treenode* left;
    treenode* right;
    treenode(int _v)
    {
        val=_v;
        count=0;
        left=NULL;
        right=NULL;
    }

};

class Rank {
public:
    vector<int> getRankOfNumber(vector<int> A, int n) {

        vector<int> ans(n,0);
        treenode* root=new treenode(A[0]);
        for(int i=1;i<n;i++)  //从A[1]开始构建二叉搜索树
        {

            treenode* p=root;//从根节点开始搜索
            while(p)
            {
                if(p->val==A[i])  //刚好等于当前值
                    break;
                if(A[i]<p->val)  //比当前节点更小  那么当前节点的count+1
                {
                    p->count+=1;
                    if(p->left==NULL)  //左边没有节点
                    {
                        p->left=new treenode(A[i]);
                        break;
                    }
                    else
                        p=p->left;

                }
                else   //A[i]比当前节点更大  那么之前比A[i]小的值进行叠加
                {
                    ans[i]+=1;//累加上当前节点
                    ans[i]+=p->count;//累加上比当前节点更小 （那么也比A[i]小）
                    if(p->right==NULL)
                    {
                        p->right=new treenode(A[i]);
                        break;
                    }
                    else
                        p=p->right;
                }    
            }
        }   
        return ans;

    }
};