#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/segment-tree/count-of-range-sum-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/segment-tree/count-of-range-sum-implementation

Repovive

LeetCode 327 Count of Range Sum - Implementation - Segment Tree | Pattern 22: LeetCode Interview Patterns | Repovive

Repovive.

Pattern 22: LeetCode Interview Patterns24 sections · 736 units32h total

Open in Course

LeetCode 327 Count of Range Sum - Implementation

The approach

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)$ .