leetcode -- tree 3

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def mergesort(nums: List[int], low: int, high: int) -> None:
            if low == high:
                return

            mid = (high + low)>>1
            mergesort(nums, low, mid)
            mergesort(nums, mid + 1, high)

            tmp = []
            l, h = low, mid + 1
            
            while l <= mid or h <= high:
                if l > mid or (h <= high and nums[h] < nums[l]):
                    tmp.append(nums[h])
                    h += 1
                else:
                    tmp.append(nums[l])
                    l += 1

            nums[low : high + 1] = tmp

        
        mergesort(nums, 0, len(nums) - 1)
        return nums
        
        

class Solution:
    # prewindow 可以用 sortedlist 替代
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        # 创建前缀和数组
        presum = [0 for i in range(len(nums) + 1)]
        for i in range(len(nums)):
            presum[i + 1] = nums[i] + presum[i]
        
        res = 0
        prewindow = []
        for _, p in enumerate(presum):
            L = bisect_left(prewindow, p - upper)
            R = bisect_right(prewindow, p - lower)
            res += R - L
            bisect.insort(prewindow, p)
        
        return res

# 归并排序中进行嵌套处理
class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        self.lower = lower 
        self.upper = upper
        self.res = 0 
        
        # create the presum
        n = len(nums)
        presum = [0 for _ in range(n + 1)]
        for i in range(n):
            presum[i + 1] = presum[i] + nums[i]
        
        self.mergesort(presum, 0, n)
        return self.res

    def mergesort(self, nums: List[int], L: int, R: int) -> None:
        if L < R:
            mid = L + (R - L) // 2
            self.mergesort(nums, L, mid)
            self.mergesort(nums, mid + 1, R)
            self.merge(nums, L, mid, R)


    def merge(self, nums:List[int], low: int, mid: int, high: int) -> None:
        tmp = []
        i, j = low, mid + 1
        while i <= mid or j <= high:
            if i > mid or (j <= high and nums[j] < nums[i]):
                tmp.append(nums[j])
                j += 1
            else:
                tmp.append(nums[i])
                i += 1
        
        i, l, r = low, mid + 1, mid + 1
        while i <= mid:
            while l <= high and nums[l] < nums[i] + self.lower:
                l += 1
            while r <= high and nums[r] <= nums[i] + self.upper:
                r += 1
            self.res += r-l
            i += 1

        # for _ in range(mid - low + 1):
        #     l = bisect_left(nums, nums[i] + self.lower, lo=l, hi=high)
        #     r = bisect_right(nums, nums[i] + self.upper, lo=r, hi=high)
        #     self.res += r-l
        #     i += 1
        

        nums[low: high + 1] = tmp

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.res = 0
        self.mergesort(nums, 0, len(nums) - 1)

        return self.res

    
    def mergesort(self, nums: List[int], L: int, R: int) -> None:
        if L < R:
            mid = L + (R - L) // 2
            self.mergesort(nums, L, mid)
            self.mergesort(nums, mid + 1, R)
            self.merge(nums, L, mid, R)



    def merge(self, nums: List[int], L: int, M: int, R: int) -> None:
        tmp = []
        i, j = L, M + 1
        while i <= M or j <= R:
            if i > M or (j <= R and nums[j] < nums[i]):
                tmp.append(nums[j])
                j += 1
            else:
                tmp.append(nums[i])
                i += 1

        i, j = L, M + 1
        while i <= M:
            while j <= R and nums[i] > 2 * nums[j]:
                j += 1
            self.res += j - M - 1
            j = M + 1
            i += 1
        
        nums[L: R + 1] = tmp