卖萌的弱渣

I am stupid, I am hungry.

Count of Range Sum

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:

A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:

Given nums = [-2, 5, -1], lower = -2, upper = 2,

Return 3.

The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

Solution

此题太难

(Count-of-Range-Sum.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution(object):
    def countRangeSum(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        sums = nums[:]
        for x in range(1, len(sums)):
            sums[x] += sums[x-1]
        # 排序
        osums = sorted(set(sums))
        ft = FenwickTree(len(osums))
        ans = 0
        for sumi in sums:
            left = bisect.bisect_left(osums, sumi-upper)
            right = bisect.bisect_right(osums, sumi-lower)
            ans += ft.sum(right) - ft.sum(left) + (lower <= sumi <= upper)
            ft.add(bisect.bisect_right(osums, sumi), 1)
        return ans


class FenwickTree(object):
    def __init__(self, n):
        # 数组的长度
        self.n = n
        self. sums = [0]*(n+1)

    def add(self, x, val):
        while x <= self.n:
            self.sums[x] += val
            x += self.lowbit(x)

    def lowbit(self, x):
        return x & -x

    def sum(self, x):
        res = 0
        while x > 0:
            res += self.sums[x]
            x -= self.lowbit(x)
        return res