315. Count of Smaller Numbers After Self

Problem:
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].

6/27/2018 update:
Another approach is to use binary index tree.
Use  [5, 2, 6, 1] as example

1. Get the ranks of sorted numbers.
sorted: [1, 2, 5, 6]
ranks<number, rank>: [1: 1, 2 : 2, 5 :3, 6: 4]

2. Distribute rank to BIT.
If number 2 ranks 2, add 1 to index 2 of BIT.

3. Get sum of BIT before current rank
If we reach 6, the rank is 4. Then we count how many numbers before rank 4. BIT helps to reduce the counting process to O(logN) instead of O(N).

class Solution {
    int[] BIT;
    public List<Integer> countSmaller(int[] nums) {
        Map<Integer, Integer> ranks = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        BIT = new int[nums.length + 1];
        int[] sorted = Arrays.copyOf(nums, nums.length);
        int rank = 1;
        Arrays.sort(sorted);
        for (int n: sorted) {
            if (!ranks.containsKey(n)) {
                ranks.put(n, rank++);
            }
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            res.add(sum(ranks.get(nums[i]) - 1));
            update(ranks.get(nums[i]), 1);
        }
        Collections.reverse(res);
        return res;
    }
     public void update(int i, int val) {
        for (int j = i; j < BIT.length; j += lowBit(j)) {
            BIT[j] += val;
        }
    }
    private int sum(int i) {
        int sum = 0;
        for (int j = i; j > 0; j -= lowBit(j)) {
            sum += BIT[j];
        }
        return sum;
    }
    private int lowBit(int i) {
        return i & (-i);
    }
}

--------------------------------------------------------------------------------------------------------------------------

6/21/2018 update:
SegmentLeft:
The number of nodes on left the current node

PreSum:
The number of nodes less than current node.val. Each time goes right, we need to think about update preSum. If node.val > current.val, so node.val > current's  segmentLefts' vals. So include segmentLeft to preSum.

We have a BST above now. Only 6 has segmentLeft > 0, what on its left are 2 and 5. Insert 7 to this tree. 7 > 1, preSum ++. When reach 6, 7 > 6, preSum++, 7 is also > what on 6's left. So preSum of 7 is 4.
--------------------------------------------------------------------------------------------------------------------------
Analysis:
The idea is to build a BST, not necessarily segment tree. Define count of node on left in TreeNode. Keep track of how many smaller numbers count traversed. 

Insert a node to current tree. If current node's value is smaller than the inserted value, insert the node to current node's left, increment current node's left count by 1.

If current node's value <= inserted value, inserted node go right, update the number of smaller count so far. 

Solution: 
The implementation is a bit challenging. In buildNode method, returning root serves two purposes. 
1. bound new node to its parent. 
2. always return root at top, so that loop can go on. 

 class Solution {
    public List<Integer> countSmaller(int[] nums) {
        if (nums == null || nums.length == 0) 
            return new ArrayList<>();
        TreeNode root = null;
        Integer[] res = new Integer[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            root = buildNode(root, res, 0, i, nums[i]);
        }
        return Arrays.asList(res);
    }

    class TreeNode {
        TreeNode left;
        TreeNode right;
        int val;
        int segmentLeft;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    private TreeNode buildNode(TreeNode root, Integer[] res, int preSum, int index, int num) {
        if (root == null) {
            res[index] = preSum;
            root = new TreeNode(num);
        } else if (root.val <= num) {
            root.right = buildNode(root.right, res, preSum + root.segmentLeft + ((root.val == num) ? 0 : 1), index, num);
        } else {
            root.segmentLeft++;
            root.left = buildNode(root.left, res, preSum, index, num);
        }
        return root;
    }
}