package code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/*
 * 315. Count of Smaller Numbers After Self
 * 
 * Hard
 * Divide and Conquer, Binary indexed Tree, Segment Tree, Binary Search Tree
 *  https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76580/9ms-short-Java-BST-solution-get-answer-when-building-BST
 *      +1index
 *      https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76583/11ms-JAVA-solution-using-merge-sort-with-explanation
 *      valueO(N)
 *      https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76576/My-simple-AC-Java-Binary-Search-code
 * Tips
 *       lc493
 */
public class lc315 {
    class TreeNode{
        int val;
        int dup_num;
        int sum;
        TreeNode left;
        TreeNode right;
        TreeNode(int val, int dup_num, int sum){
            this.val = val;
            this.dup_num = dup_num; //
            this.sum = sum; //
        }
    }

    TreeNode root;
    public List countSmaller(int[] nums) {
        if(nums.length=0 ; i--) {
            insert(root, nums[i], res_arr, i, 0);
        }
        return Arrays.asList(res_arr);  //list
    }

    public TreeNode insert(TreeNode tn, int n, Integer[] res_arr, int i, int path){ //path
        if(tn==null) {
            tn = new TreeNode(n, 1, 0);
            res_arr[i] = path;
            System.out.print(i);
            System.out.println("----"+path);
        }
        else if(tn.val==n){
            tn.dup_num++;
            res_arr[i] = path + tn.sum;
        }else if(tn.val>n){
            tn.sum++;
            tn.left = insert(tn.left, n, res_arr, i, path);
        }else{
            tn.right = insert(tn.right, n, res_arr, i, path + tn.dup_num + tn.sum);
        }
        return tn;  //
    }
}