//定义线段树
class segtree{
    public:
       segtree* leftNode = NULL;
       segtree* rightNode = NULL;
       int left = 0;
       int right = 0;
       int sum = 0;
       segtree() = default;
};


class Solution {
    
    
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    
    void pushdown(segtree* root){
        if(root->leftNode == NULL) {
            root->leftNode = new segtree();
        }
        if(root->rightNode == NULL) {
            root->rightNode = new segtree();
        }
        int mid = (root->left + root->right) >> 1;
        root->leftNode->left = root->left;
        root->leftNode->right = mid;
        root->rightNode->left = mid+1;
        root->rightNode->right = root->right;
    }
    //只更新current 所在的节点
    void update(segtree* root, int current){
        if(root == NULL) {
            return;
        }
        if(current == root->left && current == root->right) {
            root->sum++;
            return;
        }
        if(current >= root->left && current <= root->right) {
            root->sum++;
            pushdown(root);
            int mid = (root->left + root->right) >> 1;
            update(root->leftNode, current);
            update(root->rightNode, current);
            return;
        }
    }
    
    int query(segtree* root, int l, int r){
         if(root == NULL) {
            return 0;
        }
        if(root->left == root->right) {
            return root->sum;
        }
        pushdown(root);
        int mid = (root->left + root->right) >> 1;
        int res = 0;
        if(root->left >= l && root->right <= r) {//查询的范围包含了当前节点的范围
            return root->sum;
        }
        if(l > root->right || r < root->left) { //查询的范围不包含当前节点的范围
            return 0;
        }
      
        //查询的范围和当前节点范围存在交集
        if(l <= mid) {
             res += query(root->leftNode, l, r);
        }
        if(r > mid){
             res += query(root->rightNode, l, r);
        }
      
        return res;
    }
    
    vector<int> smallerCount(vector<int>& nums) {
         int n = nums.size();
         vector<int> res(n, 0);
         segtree* root = new segtree();
         root->left = -10000;
         root->right = 10000;
         res[n-1] = 0;
         for (int i = n-2; i >= 0; i--) {
             update(root, nums[i+1]);
             res[i] = query(root,-10000, nums[i]-1);
         }
        return res;
    }
};