public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        // 求得nums在按序排列的数组中的脚标位置
        int[] temp = nums.clone();
        Arrays.sort(temp);
        for (int i = 0; i < temp.length; i++) {
            nums[i] = Arrays.binarySearch(temp, nums[i]);
        }
        // 这里用Integer是为了使用Arrays.asList
        Integer[] ans = new Integer[temp.length];
        int[] bit = new int[temp.length];
        // 遍历的时候使用逆序是因为位于数组最后面的数，逆序程度是最低的
        for (int i = temp.length-1; i >= 0; i--) {
            /**
             * 用bit数组的前num[i]项和作为逆序程度
             * 
             * 最后一位的逆序永远是0  
             * 次高位的逆序要么是1要么是0,最大值只能是1
             * query方法正好保证了这点。
             *     它查询bit数组中前nums[i]项的和
             *     如果最高位比次高位要小，那么计算次高位项的和就会加1，相反就不回家
             */
            ans[i] = query(bit,nums[i]);
            /**
             * 修改那条链上的数据+1
             */
            add(bit,nums[i]+1,1);
        }
        
        return Arrays.asList(ans);
    }
    
    /**
     * 功能：
     *        修改bit数组脚标i对应的链上的数据
     *     （因为求前n项和，是根据那几个数来求的，所以改动一个数要同时改动那几个数）
     * @param bit 树状数组
     * @param i    数组脚标
     * @param val 脚标所对应的树枝要修改的值
     */
    private void add(int[] bit, int i, int val) {
        for (;i<bit.length;i+=lowbit(i)) {
            bit[i]+=val;
        }
    }
    
    /**
     * 查询bit数组中前i项的和
     * @param bit 树状数组
     * @param i    数组脚标
     * @return
     */
    private Integer query(int[] bit, int i) {
        int ans = 0;
        for (;i>0;i-=lowbit(i)) {
            ans += bit[i];
        }
        return ans;
    }
    /**
     *   求二进制的i中第一个1对应的十进制值
     * @param i 
     * @return i转化为二进制之后第一个1所对应的值
     */
    private int lowbit(int i) {
        return i&(-i);
    }
}