315. Count of Smaller Numbers After Self

class SegmentTreeNode(object):
    def __init__(self,val,start,end):
        self.val=val
        self.start=start
        self.end=end
        self.children=[]
class SegmentTree(object):
    def __init__(self,n):
        self.root=self.build(0,n-1)
    def build(self,start,end):
        if start>end:
            return 
        root=SegmentTreeNode(0,start,end)
        if start==end:
            return root 
        mid=start+end >>1
        root.children=filter(None,[self.build(start,end) for start,end in ((start,mid),(mid+1,end))])
        return root 
    def update(self,i,val,root=None):
        root=root or self.root
        if i<root.start or i>root.end:
            return root.val
        if i==root.start==root.end:
            root.val+=val
            return root.val
        root.val=sum([self.update(i,val,c) for c in root.children])
        return root.val
    def sum(self,start,end,root=None):
        root=root or self.root
        if end<root.start or start>root.end:
            return 0
        if start<=root.start and end>=root.end:
            return root.val
        return sum([self.sum(start,end,c) for c in root.children])
        

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        hash_table={v:i for i,v in enumerate(sorted(set(nums)))}
        
        tree=SegmentTree(len(hash_table))
        res=[]
        #start calculate from the right most element
        for i in range(len(nums)-1,-1,-1):
            #get the sum of the occurances of all numbers smaller than nums[i]
            res.append(tree.sum(0,hash_table[nums[i]]-1))
            #add the occurance of nums[i] to the tree
            tree.update(hash_table[nums[i]],1)
        return res[::-1]