## 题目描述：

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`.

## 解题思路：

### O(n * logn)解法：

```1. 预处理前n项和数组sums

2. 将sums数组离散化（排序+去重）得到数组osums

3. 遍历sums，记sumi = sums[i]
用二分查找得到[sumi - upper, sumi - lower]的离散化下标[left, right]
用树状数组统计范围[left, right]内的元素个数，并累加至最终结果ans
若lower <= sumi <= upper，额外地令ans+1
将sumi的离散化下标记入树状数组```

```对于数组sums中的每一个元素sumi，统计出现在sumi左侧，并且数值在[sumi - upper, sumi - lower]范围内的元素个数。

## Python代码：

``````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
``````

```Line 21~24 in merge sort is O(n), so the total cost T(n) = 2*T(n/2) + (n/2)^2 = O(n^2).
Using binary search to accelerate would improve T(n) = 2*T(n/2) + (n/2)*log(n/2) = O(n*(log n)^2).```

## Python代码：

``````class Solution(object):
def countRangeSum(self, nums, lower, upper):
"""
:type nums: List[int]
:type lower: int
:type upper: int
:rtype: int
"""
size = len(nums)
sums = [0] * (size + 1)
for x in range(1, size + 1):
sums[x] += nums[x - 1] + sums[x - 1]
INF = max(sums)

def mergeSort(lo, hi):
if lo == hi: return 0
mi = (lo + hi) / 2
cnt = mergeSort(lo, mi) + mergeSort(mi + 1, hi)
x = y = lo
for i in range(mi + 1, hi + 1):
while x <= mi and sums[i] - sums[x] >= lower:
x += 1
while y <= mi and sums[i] - sums[y] > upper:
y += 1
cnt += x - y
part = sums[lo : hi + 1]

l, h = lo, mi + 1
for i in range(lo, hi + 1):
x = part[l - lo] if l <= mi else INF
y = part[h - lo] if h <= hi else INF
if x < y: l += 1
else: h += 1
sums[i] = min(x, y)
return cnt

return mergeSort(0, size)
``````

Pingbacks已关闭。

1. 小贤爱coding 发布于 2016年1月14日 10:09 #

楼主，关于fenwick tree的解法，有几个不明白的地方，求解释：
1） 为什么是基于sums做循环 ？ for sumi in sums:
2） ft.add(bisect.bisect_right(osums, sumi), 1) 的时候，不需要判断一下是否满足 lower upper的条件，再加1 么？

能否请楼主注解一下代码和算法思路？

2. 在线疯狂 发布于 2016年1月14日 20:46 #

我添加了一些说明，不知道能否看明白。

3. 大睿-SCTrojan 发布于 2016年3月20日 14:08 #

我有一个问题：在Count of Smaller after Self中我们去重排序之后，又将其映射到[1,n]范围中，这道题有映射过程吗？

4. 大睿-SCTrojan 发布于 2016年3月21日 05:47 #

花了一个上午总算把BIT解法想明白了，实际上是做了映射的，binary search的过程就是查找映射区间的过程是吗？我按照你的思路写了一个C++的：https://github.com/ZengruiWang/Leetcode-Google/blob/master/327.%20Count%20the%20Range%20Sum%20-%20BIT.cpp

5. guang 发布于 2016年4月9日 17:20 #

Line 21~24 in merge sort is O(n), so the total cost T(n) = 2*T(n/2) + (n/2)^2 = O(n^2).
Using binary search to accelerate would improve T(n) = 2*T(n/2) + (n/2)*log(n/2) = O(n*(log n)^2).

6. 在线疯狂 发布于 2016年4月10日 01:03 #

That's right! Thank you for the reminder! I have added that to the blog post :D