python segment tree - count of smaller numbers after self
So, the time complexity of the solution posted in the question is O(n^2 log(n)).

Answering each query takes n log(n), and we have n queries in total. 

We don't necessarily need to merge the left and right subtrees to find the inversion count; given that the sublists are sorted, we can exploit binary search.

import bisect

from functools import lru_cache

def merge(left, right):
    res = []
    i, j = 0, 0 
    while i&lt;len(left) and j&lt;len(right):
        if left[i]&lt;right[j]:
            res.append(left[i])
            i+=1 
        else:
            res.append(right[j])
            j+=1 

    while i&lt;len(left):
        res.append(left[i])
        i+=1 
    while j&lt;len(right):
        res.append(right[j])
        j+=1 
    return res


class SegmentTree:
    def __init__(self, nums):
        self.nums = nums 
        self.tree = {}
        if len(nums)&gt;0:
            self._build(0, len(nums)-1, 1)
    def _build(self, l, r, index):
        if l==r:
            self.tree[index] = [self.nums[r]]
            return self.tree[index]
        else:
            mid = (l+r)//2 
            left= self._build(l, mid, index*2)
            right = self._build(mid+1, r, index*2+1)
            self.tree[index] = merge(left, right)
            return self.tree[index]

    def get_range(self, l,r, target):
        def get_range(left_boundary, right_boundary, l, r, index):
            if l&gt;r:
                return 0 
            if left_boundary == right_boundary or (left_boundary == l and right_boundary==r):
                return bisect.bisect(self.tree[index], target)
            else:
                mid = (left_boundary+ right_boundary)//2 
                left = get_range(left_boundary, mid, l, min(r, mid), index*2)
                right = get_range(mid+1, right_boundary, max(l, mid+1), r, index*2+1)
                return left+right
        return get_range(0, len(self.nums)-1, l, r, 1)

class Solution:
    def countSmaller(self, nums: List[int]) -&gt; List[int]:
        s = SegmentTree(nums)
        result = []
        for i in range(len(nums)):
            res = s.get_range(i+1, len(nums)-1, nums[i]-1)
            result.append(res)
        return result