Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Tips:

1. we should build an array with the length equals to the max element of the nums array as BIT.
2. To avoid minus value in the array, we should first add the (min+1) for every elements (It may be out of range, where we can use long to build another array. But no such case in the test cases so far.)
3. Using standard BIT operation to solve it.

用max.length建立的数组，每个数都减去了最小值+1，所以这个tree数组的index的是从1到max的所有数。然后从最后一位开始更新，找到这个数在tree里面的位置，取他的parent就是比他大一个的数的在tree里的地方算prefix sum

https://en.wikipedia.org/wiki/Fenwick_tree

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

Code:

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] - min + 1;
            max = Math.max(max, nums[i]);
        }
        int[] tree = new int[max + 1];
        for (int i = nums.length - 1; i >= 0; i--) {
            res.add(0, getSum(nums[i] - 1, tree));
            update(nums[i], tree);
        }
        return res;
    }
    private int getSum (int i, int[] tree) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i  -= i & (-i);
        }
        return sum;
    }
    private void update (int i, int[] tree) {
        while (i < tree.length) {
            tree[i]++;
            i += i & (-i);
        }
    }
}