LeetCode 327 Count of Range Sum - Implementation

def countRangeSum(nums, lower, upper):
    prefix = [0]
    for num in nums: prefix.append(prefix[-1] + num)
    def mergeSort(lo, hi):
        if hi - lo <= 1: return 0
        mid = (lo + hi) // 2
        count = mergeSort(lo, mid) + mergeSort(mid, hi)
        j = k = mid
        for i in range(lo, mid):
            while j < hi and prefix[j] - prefix[i] < lower: j += 1
            while k < hi and prefix[k] - prefix[i] <= upper: k += 1
            count += k - j
        prefix[lo:hi] = sorted(prefix[lo:hi])
        return count
    return mergeSort(0, len(prefix))

Time: $O(n \log n)$. Space: $O(n)$.