8.19 - hard - 66

327. Count of Range Sum

中午请人吃饭，结果吃多了，好困，有点坐不动了。这题有segment tree其实不是那么好做，答案的解释一大堆，决定放到明天去理解。今天的任务是做到hard70，大概是可以完成的。

class Solution(object):
    def merge(self, arr1, arr2):
        r, i, j = [], 0, 0
        while i < len(arr1) and j < len(arr2):
            if arr1[i] < arr2[j]:
                r.append(arr1[i])
                i += 1
            else:
                r.append(arr2[j])
                j += 1
        r += arr1[i:] + arr2[j:]
        return r

    def count(self, prefix, start, end, lower, upper):
        if start >= end:
            return 0

        mid = start + (end - start + 1 >> 1)
        count = sum([
            self.count(prefix, s, e, lower, upper)
            for s, e in ((start, mid - 1), (mid, end))
        ])

        l, r = mid, mid
        for i in xrange(start, mid):
            while l <= end and prefix[l] - prefix[i] < lower:
                l += 1
            while r <= end and prefix[r] - prefix[i] <= upper:
                r += 1
            count += r - l

        prefix[start:end + 1] = self.merge(
            prefix[start:mid], prefix[mid:end + 1])

        return count

    def countRangeSum(self, nums, lower, upper):
        n = len(nums)

        prefix = [0] * (n + 1)
        for i, v in enumerate(nums, 1):
            prefix[i] = prefix[i - 1] + v

        return self.count(prefix, 0, n, lower, upper)