写在前面
看完labuladong的归并排序的应用后，准备稍稍总结下；来到题解区，翻了下三叶姐的题解（恐怖如斯，惊掉下巴~~）
- 原始数组：$nums[i]$，长度为 $n$
- 前缀和数组：$preSum[i]$，长度为 $n+1$
- 其中 $preSum[0]=0，preSum[i]=preSum[i-1]+nums[i-1]$
- 类似题目：
前缀和
题目要求的是求满足条件的区间和 $S[i,j]$ 的个数，其中区间和是闭区间。也就是说找到符合题意的 $i<j$，满足 $lower<=S[i,j]<=upper$。考虑使用前缀和来快速求解。
- 前缀和的使用
- 前缀和 $preSum$ 的数组长度是原始数组的长度加1，首位置位零；对于任意的 $preSum[j]-preSum[i]$ （$i<j$），能够包含所有的区间和情况。
- 题目只需要求解满足条件的个数，因此简单了很多，不必要纠结下标的具体位置。
- 因此问题就转换为，对于数组 $preSum$，求解符合题意的 $i,j$ 即可。
- $i<j$ 且 $preSum[j]-preSum[i]$ 在 $[lower,upper]$ 范围内。
归并排序
归并排序是对 $preSum$ 数组进行操作，对于每一次merge的操作，记录左侧（$i$ 的位置）与右侧（$j$ 的位置）符合条件的个数，要注意的是因为左右两侧都是排序好的部分，有时可以利用这个条件减少计算。
归并排序的使用
- 分而治之的思想，类似于二叉树的后序遍历，分解成子问题。
- 排序左侧，排序右侧，合并（merge）
合并左右
左右两侧都是已经排好序的数组，为了更好的合并，在开始前先复制拷贝一份
- 合并两个有序数组
- 双指针的思想，画出简图，更加容易理解
- 本题不需要记录下标的位置，因此合并或称较为简单，简单排序即可。
- 求解题目答案
- 这部分可以放在双指针合并的过程中，也可以放在前面，主要是看哪种方便高效且不易出错。
- 注意不要重复计算，边界条件，区间开闭情况等。
其他
对于 493. 翻转对 - 力扣（LeetCode） 问题，也仅仅是计数问题，不涉及元素下标问题，因此在合并排序时比较简单。
- 需要记录对应下标
- 315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）
- 返回值是一个数组，需要记录是右侧小于该元素的个数，但是排序会改变位置，因此需要同时记录元素值与位置（数对）。
vector<pair<int,int>> temp
数对的创建及使用
temp.push_back(make_pair(nums[i],i))temp[i].first；temp[i].second（元素值及其索引位置）
注意数据范围
- 不同题目的数据范围不一样，因此在创建新的数组保存变量时，注意数据类型的设置
- 类型强制转换：
(int) data，(long long) data
$\cdots$ end $\cdots$