给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

    示例：

    输入：nums = [5,2,6,1]

    输出：[2,1,1,0]

    解释：

    5 的右侧有 2 个更小的元素 (2 和 1)

    2 的右侧仅有 1 个更小的元素 (1)

    6 的右侧有 1 个更小的元素 (1)

    1 的右侧有 0 个更小的元素

    这题非常经典的可用树状数组来解题的场景。
    为什么会想到用树状数组？
    首先暴力枚举的时间复杂度O(N^2)是不可能在OJ上通过的。因为需要统计的是右侧的严格小于本元素的数的数量，从统计层面上的高等策略来讲，前缀数和数组和差分数组会比较常用，显然此题不是求静态的区间和，也不是区间更新的场景。我们的解题思路可以是：从右往左遍历，将遇到的数加入到一个容器，再对这个容器进行查询，结果为右侧小于此数的元素的数量，这就涉及到了一个动态的更新，而且是单点更新，然后查询，这就是树状数组的拿手菜了。具体策略为：先对原数组进行去重得到N个数并给出他们各自的排名(从1到N），排名和原数一一映射。借助一个长度为N+1的树状数组arr，该数组中的元素arr[i]表示排名为i的元素有arr[i]个。利用树状数组的更新和查询操作，从右往左遍历原数组，使每个数对应的排名统计位arr[i]加一，这里借助树状数组的更新(会触发连带的更新其他arr[i])，更新的时间复杂度为logN，在这轮更新结束后，便可以进行查询，查询排名比自己低的有多少—累加arr[1]~arr[i-1]就是结果，不过这里可以借助树状数组的区间和查询，时间复杂度为logN，因为总是从右往左遍历更新树状数组的，所以只能统计到右侧的，非常满足题意。

    树状数组视频详解
    树状数组模板：

    1. int lowbit(int n){
    2.     return n&(-n);
    3. }
    4. //arr[i]加上value
    5. void update(vector<int>& tree, int i, int value){
    6.     while(i<tree.size()){
    7.         tree[i]+=value;
    8.         i+=lowbit(i);
    9.     }
    10. }
    11. int query(vector<int>& tree, int i){
    12.      int ret=0;
    13.     while(i>0){    //注意：树状数组是从1开始的
    14.          ret+=tree[i];
    15.         i-=lowbit(i);
    16.     }
    17.     return ret;
    18. }

    315题解：

    1.     vector<int> countSmaller(vector<int>& nums) {
    2.         vector<int>N(nums);
    3.         // 排序、去重、获得各个元素的排名
    4.         sort(N.begin(), N.end());
    5.         removeDups(N,1);
    6.         unordered_map<int,int> map;
    7.         int rank=1;
    8.         for(auto n:N){
    9.              map[n]=rank;
    10.             rank++;
    11.         }
    13.         vector<int> ret(nums.size(), 0);
    14.         vector<int> C(N.size()+1,0);
    15.         for(int j=nums.size()-1;j>=0;--j){
    16.              int rank=map[nums[j]];   
    17.             update(C,rank,1);
    18.             if(rank==1){
    19.                 ret[j]=0;
    20.             }else{
    21.                  ret[j]=query(C,rank-1);   
    22.             }
    23.         }
    24.         return ret;
    25.     }
    26.     void removeDups(vector<int>& arr, int k){
    27.          int index=k;
    28.         for(int i=k;i<arr.size();++i){
    29.              if(arr[i]!=arr[index-k]){
    30.                 arr[index++]=arr[i];
    31.             }
    32.         }
    33.         arr.resize(index);
    34.     }

    如果面试巧遇这题，很大可能是个滑铁卢唉。