### 327.Count-of-Range-Sum

此题初看，立刻想到用累加和数组sums。任意某段区间(i,j)的和，等于sums[j]-sums[i-1]。不过即使这样，这道题仍需要o(n^2)的时间复杂度，因为要分别在sums中遍历符合要求的i,j两个元素。 

不过，这道题如果这样思考：确定了首元素i的位置，那么就需要在首元素之后在sums寻找一个尾元素j. 如果i之后的sums数组已经是有序的，那么j元素就可以通过二分法o(log(n))的时间复杂度完成寻找。要想做到i之后的元素有序，那么分治/归并排序的组合套路就呼之欲出。这和 315.Count of Smaller Numbers After Self 是一个思路。 

我在分析315的时候介绍过：分治法的最常见的应用就是与归并排序相结合。将数组对半划分为左右两部分，两部分各自排序，然后将两部分整体归并，在归并的过程中就可以解决一些问题（利用一侧或者两个序列是有序的这个性质）。 

对于本题：在每一轮，序列start~end对半分为两部分，左序列区间从start到mid，右序列区间从mid+1到end。两个部分各自递归调用分治排序的函数后，都变得有序。此时，对于左序列的任意nums[i]，都可以轻易在有序的右序列中用lower_bound找到sums[i]+lower和sums[i]+upper的位置（或者亲自写二分查找的代码），这两者之间的元素都是符合要求的，将其数目加入总和中。 

本题的另一个训练点就是对C++的STL里lower_bound的考察。如何写自定义比较函数是关键。我们需要在右序列中找到下限的位置，希望找到的位置在原序列中是大于等于sums[i]+lower的，所以自定义函数里要写a<b。另一方面，我们需要在右序列中找到上限的位置，希望找到的位置在原序列中是大于sums[i]+upper的，所以自定义函数里要写a<=b。最终pos2-pos1表示原序列里处于[sums[i]+lower,sums[i]+upper]闭区间的个数。 


[Leetcode Link](https://leetcode.com/problems/count-of-range-sum)