@@ -0,0 +1,1389 @@
+package dtprogrammer.github.io.p315;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.List;%0A%0Apublic class Solution %7B%0A    public List%3CInteger%3E countSmaller(int%5B%5D nums) %7B%0A        if (nums == null %7C%7C nums.length == 0) %7B%0A            return new ArrayList%3C%3E();%0A        %7D%0A        Integer%5B%5D result = new Integer%5Bnums.length%5D;%0A        Node node = null;%0A        // visit the array from right to left%0A        for (int i = nums.length - 1; i %3E= 0; i--) %7B%0A            node = addToTree(result, node, i, nums%5Bi%5D, 0);%0A        %7D%0A        return Arrays.asList(result);%0A    %7D%0A%0A    private Node addToTree(Integer%5B%5D result, Node node, int i, int val, int preSum) %7B%0A        if (node == null) %7B%0A            result%5Bi%5D = preSum;%0A            return new Node(val, 0);%0A        %7D%0A        if (node.val == val) %7B%0A            node.dupCount += 1;%0A            result%5Bi%5D = preSum + node.sum;%0A        %7D else if (node.val %3C val) %7B%0A            node.right = addToTree(result, node.right, i, val, preSum + node.sum + node.dupCount);%0A        %7D else %7B%0A            node.sum += 1;%0A            node.left = addToTree(result, node.left, i, val, preSum);%0A        %7D%0A        return node;%0A    %7D%0A%0A%0A    private class Node %7B%0A        Node left, right;%0A        int val, sum, dupCount;%0A%0A        Node(int val, int sum) %7B%0A            this.val = val;%0A            this.sum = sum;%0A            this.dupCount = 1;%0A        %7D%0A    %7D%0A%7D%0A

315. Count of Smaller Numbers After Self