Count of Range Sum — Merge Sort / BIT

Problem

Count number of range sums sum(nums[i..j]) that lie in [lower, upper].

Approach — Merge Sort on Prefix Sums

Build prefix sums. During merge sort, use two pointers to count how many right prefix sums satisfy lower <= right - left <= upper.

Time: O(n log n) | Space: O(n)

Solutions

Python

class Solution:
    def countRangeSum(self, nums: list[int], lower: int, upper: int) -> int:
        prefix=[0]
        for n in nums: prefix.append(prefix[-1]+n)
        self.count=0
        def merge_sort(arr):
            if len(arr)<=1: return arr
            mid=len(arr)//2
            left=merge_sort(arr[:mid]); right=merge_sort(arr[mid:])
            j=k=0
            for lv in left:
                while j<len(right) and right[j]-lv<lower: j+=1
                while k<len(right) and right[k]-lv<=upper: k+=1
                self.count+=k-j
            return sorted(left+right)
        merge_sort(prefix); return self.count

Complexity

Time: O(n log n) | Space: O(n)