1. 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].

Segment Tree

class SegmentTreeNode {
    int start, end;
    int num;
    SegmentTreeNode ltree, rtree;
    public SegmentTreeNode(int s, int e) {
        start = s;
        end = e;
    }
}

public class Solution { 
    SegmentTreeNode root = null;

    public SegmentTreeNode buildTree(int[] nums, int left, int right) {
        SegmentTreeNode root = new SegmentTreeNode(left, right);
        if (left != right) {
            int mid = left + (right - left)/2;
            root.ltree = buildTree(nums, left, mid);
            root.rtree = buildTree(nums, mid+1, right);
        }
        return root;
    }

    private void update(SegmentTreeNode root, int i, int val) {
        if (root.start == root.end) {
            root.num += 1;
        } else {
            int mid = root.start + (root.end - root.start)/2;
            if (i <= mid) {
                update(root.ltree, i, val);
            } else {
                update(root.rtree, i, val);
            }
            root.num = root.ltree.num + root.rtree.num;
        }
    }

    private int query(SegmentTreeNode root, int i, int j) {
        if (root.start == i && root.end == j) {
            return root.num;
        } else {
            int mid = root.start + (root.end - root.start)/2;
            if (j <= mid) {
                return query(root.ltree, i, j);
            } else if (i > mid) {
                return query(root.rtree, i, j);
            } else {
                return query(root.ltree, i, root.ltree.end) + query(root.rtree, root.rtree.start, j);
            }
        }
    }

    public List<Integer> countSmaller(int[] nums) {
        int[] tmp = nums.clone();
        Arrays.sort(tmp);
        for (int i = 0; i < nums.length; i++) {
            nums[i] = Arrays.binarySearch(tmp, nums[i]) + 1;
        }
        int[] bit = new int[nums.length + 1];
        root = buildTree(bit, 0, bit.length-1);
        Integer[] ans = new Integer[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            ans[i] = query(root, 0, nums[i] - 1);
            update(root, nums[i], 1);
        }
        return Arrays.asList(ans);
    }
}

Use binary to insert each node from back of array, tail element is the root node. this is an augmented binary search tree where each node contains how many nodes have less values than current node, then when new node is inserted and the new value is greater than root node, there will be root.count number of nodes, the count is initialized to 1, cause root node itself count when greater value is inserted.

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if(nums.length == 0) return res;
        TreeNode root= new TreeNode(nums[nums.length-1]);
        res.add(0);
        for(int i= nums.length-2; i>=0; i-- ){
            int count = insert(root, nums[i]);
            res.add(count);
        }
        Collections.reverse(res);
        return res;
    }

    private int insert(TreeNode root, int val){
        int c = 0;
        while(true){
            if(val <=  root.val){
                root.count++;
                if(root.left == null){
                    root.left = new TreeNode(val);
                    break;
                }else{
                    root = root.left;
                }

            }else{
                c += root.count;
                if(root.right == null){
                    root.right = new TreeNode(val);
                    break;
                }else{
                    root = root.right;
                }
            }
        }
        return c;
    }

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