问题：
给定一个数组，求连续元素之和在给定范围[lower, upper]之间的，连续idx为(i～j)元素组个数。
Note: A naive algorithm of O(n2) is trivial. You MUST do better than that. Example: Input: nums = [-2,5,-1], lower = -2, upper = 2, Output: 3 Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2. Constraints: 0 <= nums.length <= 10^4
解法：
解法类似 315. Count of Smaller Numbers After Self
解法一：FenwickTree
- 只是需要多求一步presum->sum，作为处理对象。
- 对前缀和数组，进行sort->sortsum，来确定在FenwickTree中的idx。
- FenwickTree记录对应相同sum值的个数（出现频率）。
然后对原顺序的sum，逐一读入，
每个sum[i]中，在FenwickTree中，寻找sum[i]-upper ~ sum[i]-lower 范围内共有多少个，res追加。
然后把当前sum[i]找到idx，插入FenwickTree中，累计count+1。
代码参考：
1 class FenwickTree { 2 public: 3 FenwickTree(int n):tree(n+1, 0) {} 4 void update(int i, int delta) { 5 while(i<tree.size()) { 6 tree[i]+=delta; 7 i+=lowbit(i); 8 } 9 } 10 int getPresum(int i) { 11 int sum=0; 12 while(i>0){ 13 sum+=tree[i]; 14 i-=lowbit(i); 15 } 16 return sum; 17 } 18 private: 19 vector<int> tree; 20 int lowbit(int x) { 21 return x&(-x); 22 } 23 }; 24 25 class Solution { 26 public: 27 int countRangeSum(vector<int>& nums, int lower, int upper) { 28 int cursum=0; 29 int res=0; 30 vector<long long> sum(nums.size()+1,0); 31 for(int i=0; i<nums.size(); i++){ 32 sum[i+1]=sum[i]+nums[i]; 33 } 34 vector<long long> sortsum(sum); 35 sort(sortsum.begin(), sortsum.end()); 36 37 FenwickTree ftree(sum.size()); 38 for(int i=0; i<sum.size(); i++){ 39 int idx_low = distance(sortsum.begin(), lower_bound(sortsum.begin(),sortsum.end(),sum[i]-upper)); 40 int idx_upper = distance(sortsum.begin(), upper_bound(sortsum.begin(),sortsum.end(),sum[i]-lower)); 41 res+=(ftree.getPresum(idx_upper)-ftree.getPresum(idx_low)); 42 43 int idx = distance(sortsum.begin(), lower_bound(sortsum.begin(),sortsum.end(),sum[i])); 44 ftree.update(idx+1, 1); 45 } 46 return res; 47 } 48 };
解法二：mergeSort
同上，先求得presum->sum，作为处理对象。
在mergeSort的同时，
对已经排序好的前后两个数列
- start ~ mid
- mid+1 ~ end
遍历第一个数列（start ~ mid）的每一个sum[p]
在后一个数列（mid+1 ~ end）中，
- 找sum[m]，（使sum[m]不断增大）一直找到使得：sum[m]-sum[p] >= lower
- 找sum[n]，（使sum[n]不断增大）一直找到使得：sum[n]-sum[p] > upper
若不满足（sum[m]-sum[p] < lo sum[n]-sum[p] <= up），则一直++，直到找到停止while循环。
那么m-n的个数=要求的对于sum[p]满足条件的个数。
1 int m=mid+1, n=mid+1; 2 for(int p = start; p <= mid; p++) { 3 while(m<=end && sum[m]-sum[p]<lo) m++; 4 while(n<=end && sum[n]-sum[p]<=up) n++; 5 res += (n-m); 6 }
♻️ 优化：这里随着下一个sum[p]是增大的，那么上次找到的临界值m和n，不需要从头再算一次，直接从上一次的临界值继续尝试增大即可。
累计后，将两个数列merge排序。
代码参考：
1 class Solution { 2 public: 3 int countRangeSum(vector<int>& nums, int lower, int upper) { 4 int res=0; 5 lo = lower; 6 up = upper; 7 sum.resize(nums.size()+1,0); 8 for(int i=0; i<nums.size(); i++){ 9 sum[i+1]=sum[i]+nums[i]; 10 } 11 res = mergeSort(0, sum.size()-1); 12 return res; 13 } 14 int mergeSort(int start, int end) { 15 int res = 0; 16 if(end<=start) return res; 17 int mid = start + (end - start) / 2; 18 res += mergeSort(start, mid); 19 res += mergeSort(mid+1, end); 20 res += merge(start, mid, end); 21 return res; 22 } 23 int merge(int start, int mid, int end) { 24 int res = 0; 25 int m=mid+1, n=mid+1; 26 for(int p = start; p <= mid; p++) { 27 while(m<=end && sum[m]-sum[p]<lo) m++; 28 while(n<=end && sum[n]-sum[p]<=up) n++; 29 res += (n-m); 30 } 31 vector<long long> tmp(end-start+1, 0); 32 int p=start, q=mid+1; 33 int i=0; 34 while(p<=mid && q<=end){ 35 if(sum[p]<sum[q]) tmp[i++] = sum[p++]; 36 else tmp[i++] = sum[q++]; 37 } 38 while(p<=mid) tmp[i++] = sum[p++]; 39 while(q<=end) tmp[i++] = sum[q++]; 40 copy(tmp.begin(), tmp.end(), sum.begin()+start); 41 42 return res; 43 } 44 private: 45 int lo; 46 int up; 47 vector<long long> sum; 48 };