<p>Given an integer array <code>nums</code>, return<em> an integer array </em><code>counts</code><em> where </em><code>counts[i]</code><em> is the number of smaller elements to the right of </em><code>nums[i]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,2,6,1]
<strong>Output:</strong> [2,1,1,0]
<strong>Explanation:</strong>
To the right of 5 there are <b>2</b> smaller elements (2 and 1).
To the right of 2 there is only <b>1</b> smaller element (1).
To the right of 6 there is <b>1</b> smaller element (1).
To the right of 1 there is <b>0</b> smaller element.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1]
<strong>Output:</strong> [0]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1,-1]
<strong>Output:</strong> [0,0]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

# SegmentTree

class Solution: 
    # entry_
    def countSmaller(self, nums: List[int]) -> List[int]:
        nums = list(reversed(nums))
        self.sorted_unique_nums = sorted(list(set(nums)))
        root = self.BUILD(0, len(self.sorted_unique_nums) - 1) if nums else None
        
        res = []
        for num in nums:
            count_smaller = self.QUERY(root, float('-inf'), num - 1)
            res.append(count_smaller) 
            self.UPDATE(root, num)
        return reversed(res)

    def BUILD(self, left_idx, right_idx):
        root = SegmentTreeNode(self.sorted_unique_nums[left_idx], self.sorted_unique_nums[right_idx])
        if left_idx == right_idx:
            return root
        mid = (left_idx + right_idx) // 2
        root.left = self.BUILD(left_idx, mid)
        root.right = self.BUILD(mid+1, right_idx)
        return root
    
    def UPDATE(self, root, val):
        if not root: return 
        if root.low <= val <= root.high:
            root.cnt += 1
            # update subtrees for count if their range covers input value
            self.UPDATE(root.left, val)
            self.UPDATE(root.right, val)
            
    def QUERY(self, root, lower, upper):
        if lower <= root.low and root.high <= upper: # node's range is within the query-range
            return root.cnt
        if upper < root.low or root.high < lower: # node's range is outside
            return 0
        # query subtrees with the same target range
        return self.QUERY(root.left, lower, upper) + self.QUERY(root.right, lower, upper)


class SegmentTreeNode:
    def __init__(self, low, high):
        self.low = low # range
        self.high = high # range
        self.left = None # sub tree node
        self.right = None # sub tree node
        self.cnt = 0
3104