@@ -0,0 +1,970 @@
+// Solution runs in O(n log n) time and O(n) space%0Aclass Solution %7B%0A  static class Node %7B%0A    Node left;%0A    Node right;%0A    int val = 1, sum = 1, dup = 1;%0A%0A    public Node(int v, int s) %7B%0A      val = v;%0A      sum = s;%0A    %7D%0A  %7D%0A%0A  public List%3CInteger%3E countSmaller(int%5B%5D nums) %7B%0A    Node root = null;%0A    Integer%5B%5D counts = new Integer%5Bnums.length%5D;%0A    for (int i = nums.length - 1; i %3E= 0; i--) %7B%0A      root = insert(nums%5Bi%5D, root, counts, i, 0);%0A    %7D%0A    return Arrays.asList(counts);%0A  %7D%0A%0A  private Node insert(int num, Node node, Integer%5B%5D ans, int i, int preSum) %7B%0A    if (node == null) %7B%0A      node = new Node(num, 0);%0A      ans%5Bi%5D = preSum;%0A    %7D else if (node.val == num) %7B%0A      node.dup++;%0A      ans%5Bi%5D = preSum + node.sum;%0A    %7D else if (node.val %3E num) %7B%0A      node.sum++;%0A      node.left = insert(num, node.left, ans, i, preSum);%0A    %7D else %7B%0A      node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);%0A    %7D%0A    return node;%0A  %7D%0A%7D%0A

add solution