動機

使用divide and conquer的時機是?

Problem

Given an integer array nums and two integers lower and upper, 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 inclusive, where i <= j.

 

Example 1:

Input: nums = [-2,5,-1], lower = -2, upper = 2Output: 3Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.

Example 2:

Input: nums = [0], lower = 0, upper = 0Output: 1

 

Constraints:

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • -105 <= lower <= upper <= 105
  • The answer is guaranteed to fit in a 32-bit integer.
(i > j，i是現在算到的prefix sum)
lower <= sum[i]-sum[j] <= upper
-sum[i]+lower <= -sum[j] <= -sum[i]+upper
sum[i]-lower > sum[j] > sum[i]-upper

這樣就變成只要找有沒有sum[j]就好，那個數要怎麼辦? 回想LC315，sorted list的index，就是前面有幾個比自己小

因此，把兩個位置相減就是我們要的

from sortedcontainers import SortedList
class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        # lower <= sum[i]-sum[j] <= upper
        # -sum[i]+lower <= -sum[j] <= -sum[i]+upper
        # sum[i]-lower > sum[j] > sum[i]-upper
        sums = SortedList()
        sums.add(0)
        total = 0
        ret = 0
        for n in nums:
            total += n
            ret += (bisect_right(sums,total-lower) - bisect_left(sums,total-upper))
            sums.add(total)
        return ret

Sol2: divide and conquer

divide and conquer時如果分成左右兩邊，右邊的index都會比左邊大，所以可以直接在右邊找有沒有符合的

如果只是要找個數，利用右邊的index都會比左邊大的特點，就可以用divide and conquer

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        if not nums:
            return 0
        self.lower, self.upper = lower, upper
        self.sums = [0]
        self.nums = nums
        for i in range(len(nums)):
            self.sums.append(nums[i]+self.sums[i])
        return self.diq(0,len(nums)+1)
    def diq(self,l,r):
        if (r-l) <= 1:
            return 0
        
        mid = l + (r-l) // 2
        ret = self.diq(l,mid) + self.diq(mid,r)
        i,j = mid, mid
        for k in range(l,mid):
            # lower <= sum[i]-sum[j] <= upper
            while (j < r) and ((self.sums[j] - self.sums[k]) < self.lower):
                j += 1
            while (i < r) and ((self.sums[i] - self.sums[k]) <= self.upper):
                i += 1
            ret += (i-j)
        self.sums[l:r] = sorted(self.sums[l:r]) # 我懶得用merge
        return ret

case study: binary index tree

因為這裡要算的是range count，剛好是bit的守備範圍(range中的count總數)，只要有一個range被碰到，update時count就可以一路更新上去

也因為要看被碰到的range，所以不能只算prefix sum，要連同扣過上下限的prefix sum一起看，這樣如果落在上下限的prefix sum時才會被更新到

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, x, delta):
        while x <= self.n:
            self.tree[x] += delta
            x += x & -x
    
    def query(self, x):
        res = 0
        while x > 0:
            res += self.tree[x]
            x -= x & -x
        return res

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        if not nums:
            return 0
        presum = 0
        values = set([0])
        for x in nums:
            presum += x
            values.add(presum)
            values.add(presum - lower)
            values.add(presum - upper)
        # mapping sparse ordered values to 1 ~ n
        x2i = {x: i + 1 for i, x in enumerate(sorted(set(values)))}
        bit = BIT(len(x2i))
        bit.update(x2i[0], 1) # should add the sum of empty prefix array
        res = cur = 0
        # calculate the pairs on flight
        for i, x in enumerate(nums):
            cur += x
            l = bit.query(x2i[cur - upper] - 1)
            r = bit.query(x2i[cur - lower])
            res += r - l 
            bit.update(x2i[cur], 1)
        return res