一、归并排序的难题
题目名称：区间和个数
给定一个数组和一个范围，问这个数组有多少个子数组的值之和是在这个范围当中的。

给定一个数组arr，两个整数lower和upper，
返回arr中有多少个子数组的累加和在[lower,upper]范围上

可以转换为求出每个以每个下标结尾的数组，的值之和，是否在这个范围当中。
假设0 ~ i上整体累加和是x，求必须以i位置结尾的子数组的值之和中，有多少个在 [lower , upper] 上，等同于求i之前的所有前缀和中，有多少落在 [x - upper , x - lower] 上，

如果说有一个前缀和（也就是一个前缀数组的元素）在[x - upper , x - lower]上达标，
那么必定有一个以i结尾的子数组（指的是原数组的子数组）在[lower, upper]上达标，
这是一个互补的一一对应的关系；

证明：

问题转化为：在前缀和数组中，不断拿到每个元素，判断它之前的前缀和有多少个满足 [x - upper , x - lower] ，返回结果

归并的核心思想就是左组之于右组，是否满足一个什么条件
而这刚好契合上面的转化过后的问题：对于右组的某个元素而言，判断左组的元素是否处在一个范围，

但是右组的第二个元素不是应该判断以左组第一个元素到右组第一个元素这个范围上的值是否处在某个范围吗？
答：右组第一个元素之于右组第二个元素，在之前就已经被处理过了，所以在最后，也就是数组被分为两大左组
右组时，右组的元素全部都是一伙的，不会内斗的那种（直到整个数组变成了一个组，他们也不内斗了）

这个过程可以暴力求解，遍历左组中全部元素，看有多少满足 [x - upper , x - lower] ，

因为左右数组都是有序的，可以运用指针不回退的技巧，

int ans = 0;
int windowL = L;
int windowR = L;
// [windowL, windowR)
for (int i = M + 1; i <= R; i++) {
    long min = arr[i] - upper;
    long max = arr[i] - lower;
    while (windowR <= M && arr[windowR] <= max) {
        windowR++;
    }
    while (windowL <= M && arr[windowL] < min) {
        windowL++;
    }
    ans += windowR - windowL;

上述代码表示一个[windowL, windowR)区域，我想可能是因为几行代码共同决定了这个区域，所以现在还不太懂

[windowL, windowR)，右边是开区间，是因为在执行windowR那个while时，
只有windowR到达最后一个满足条件的下一个下标时才结束，所以windowR取不到
或者说最后的windowR满足的是
						arr[windowR] > max的最小值
						
而最后的windowL满足的是
						arr[windowL] >= min的最小值
所以是[windowL, windowR)

8.15更新：最好是用这种区域表示一个范围，如果换成别的表示区域方法比方说[windowL, windowR]而ans
变为ans += windowR - windowL + 1的话可能会出错，具体原因确实每太搞懂~

8.16更新：上面的理解其实不对，arr[windowR] <= max，windowR最终会超过满足条件的下标一位，
而windowL会抵达满足条件的第一位，所以才是[windowL, windowR)；
就是说最终归纳进来的数是
						[windowL, windowR - 1],
包含的数的个数有
				windowR  - 1 - windowL + 1 = windowR - windowL

而可以不回退的原因在于，右组是有序的，右组提供的范围，不管是上界还是下界都是在递增的，所以如果一个数不符合当前范围，就肯定不符合后面的数提供的范围了

把他俩直接相减的结果加起来，最后进行merge即可；

记忆点：
1.问题转化为前缀和相关
排队敬酒，看看前面有多少人
2.归并
一桌一起坐的人和另一桌一起坐的人齐同端起酒杯

每桌都有人排队敬酒，看看前面还有多少人，敬完后再一起

3.指针不回退
指着厕所在那边，踉跄但没有走三步退一步

二、荷兰国旗问题
选取数组的最后一个元素的值x作为划分值，排序成：小于x的放左边，等于x的放中间，大于x的放右边

						[  < x, = x, > x  ]

设置三个区域的两个划分轴，返回类型是以等于区域边界的两个元素组成的数组

int less = L - 1;/*小于区域的右边界*/
int more = R;/*大于区域的左边界*/
int index = L;

当前数等于划分值，当前数直接跳下一个
当前数小于划分值，当前数和小于区域的下一个数交换，当前数跳下一个，小于区域往右扩一位
当前数大于划分值，当前数和大于区域的左边界交换，当前数不变，大于区域往左缩一位

记忆点：
1.两座风车把整个平面区域分成三份，
2.中间养羊，直接跳
3.左边市场，交换、跳；右边养花，不动

三、随机快排
递归时在数组中随机选择一个数与最后一个数做交换

随机快排的时间复杂度可以收敛到O(N*logN)
空间复杂度可以收敛到logN

随机快排非递归版本：
在数组中随机选择一个数与最后一个数做交换，将大任务分成俩子任务，先压到栈里，当栈不为空时，荷兰国旗之后再进行子任务的划分，然后再压栈

先将两个大的子任务放在while外面进行压栈是为了保证栈的初始状态不为空；
非递归版本是自己申请栈，递归版本是利用系统提供的栈

记忆点：
随机：抽球
交换：球交换礼品