Count of Range Sum

Problem: Count of Range Sum

We can use merge-sort to solve this problem. First we get accumulated sum at each position. During merging, we get range sum by subtracting sum of left part from sum of right part. If the sum does not lies in the boundaries, we adjust pointers. We make one pointer align to a position where we can get a smallest potential range sum and another to a position where we can get a largest possible sum.

Code in Python:

class Solution(object):
    def countRangeSum(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        sums = [0]
        for num in nums:
            sums.append(sums[-1] + num)

        def sort(l, r):
            mid = (l + r) / 2
            if mid == l:
                return 0
            count = sort(l, mid) + sort(mid, r)
            i = j = mid
            for left in sums[l:mid]:
                while i < r and sums[i] - left < lower: i += 1
                while j < r and sums[j] - left <= upper: j += 1
                count += j - i
            sums[l:r] = sorted(sums[l:r])
            return count

        return sort(0, len(sums))