Count of Range Sum

Intuition

A slice sum equals prefix[j] - prefix[i] with i < j, so the task is counting prefix-sum pairs whose difference sits in the range. During merge sort both halves become sorted, and for a fixed left prefix value the qualifying right values form a contiguous window. Because the left half is sorted, that window's boundaries only slide forward as the left value grows, so two moving pointers count matches for the whole left half in linear time per merge. Summing these counts across every merge level yields the total. Prefix sums must use 64-bit integers to avoid overflow.

Algorithm walkthrough

1. 1Build a prefix-sum array of length n+1 using 64-bit integers, with prefix[0] = 0.
2. 2Recursively merge sort the prefix array; the answer accumulates across recursive calls.
3. 3Before merging a left and right half, for each left value advance two pointers over the right half to find how many right values satisfy lower ≤ right - left ≤ upper, adding that window width to the count.
4. 4Merge the two sorted halves back together so the parent call sees a sorted range.
5. 5Return the total count produced by the top-level call.

Implementation

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        prefix = [0] * (len(nums) + 1)
        for i, v in enumerate(nums):
            prefix[i + 1] = prefix[i] + v

        def merge_sort(lo: int, hi: int) -> int:
            if hi - lo <= 1:
                return 0
            mid = (lo + hi) // 2
            count = merge_sort(lo, mid) + merge_sort(mid, hi)
            j = k = mid
            for left_val in prefix[lo:mid]:
                while j < hi and prefix[j] - left_val < lower:
                    j += 1
                while k < hi and prefix[k] - left_val <= upper:
                    k += 1
                count += k - j
            prefix[lo:hi] = sorted(prefix[lo:hi])
            return count

        return merge_sort(0, len(prefix))