【算法&数据结构体系篇class04】：归并排序相关问题

比眉伴天荒 2024-03-27 17:36 58阅读 0赞

### 一、归并排序 ###

递归：二分数组分成左右数组，分别递归进行左右数组排序，然后再合并左右数组，整合排序

非递归：设置步长，步长按2倍增长循环遍历每次的数组找到合适的左右数组的边界。再进行合并

package class04;
    
    public class Class04 {
        // 递归方法实现
        public static void mergeSort1(int[] arr) {
            if (arr == null || arr.length < 2) {
                return;
            }
            process(arr, 0, arr.length - 1);
        }
    
    
        // 请把arr[L..R]排有序
        // l...r N
        // T(N) = 2 * T(N / 2) + O(N)
        // O(N * logN)
        public static void process(int[] arr, int L, int R) {
            //1.base 左右边界相等 即只有一个数，之间返回 不用处理
            if (L == R) return;
            //2.取中点
            int mid = L + ((R - L) >> 1);
            //3.递归左与右数组
            process(arr, L, mid);
            process(arr, mid + 1, R);
            //4.合并左右数组让整体有序 此时的左右数组都是已经各自排好序的了
            merge(arr, L, mid, R);
        }
    
        //合并左右已经排好序的左右子数组，并且把值赋给原数组
        public static void merge(int[] arr, int L, int M, int R) {
            //创建一个数组进行保存排好序的数据，长度要注意是当前合并两数组长度
            int[] help = new int[R - L + 1];
            //定义新存放数据的数据索引，以及左右子数组的首指针 用来遍历判断
            int index = 0;
            int p1 = L;
            int p2 = M + 1;
            //两指针两两判断，小的就插入数组，并且指针前移，直到有一个越界跳出
            while (p1 <= M && p2 <= R) {
                help[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
            }
            //跳出后，肯定存在一个指针还没遍历到尾部的，那么再将其剩余元素插入数组
            while (p1 <= M) {
                help[index++] = arr[p1++];
            }
            while (p2 <= R) {
                help[index++] = arr[p2++];
            }
            //开始赋值，注意是用申请的辅助数组 每次合并的数组都是插入这个数组
            for (int i = 0; i < help.length; i++) {
                arr[L + i] = help[i];
            }
        }
    
        // 非递归方法实现归并排序
        public static void mergeSort2(int[] arr) {
            if (arr == null || arr.length < 2) return;
            //定义一个步长变量，指左数组或右数组的步长，即组内元素个数 遍历完之后就让步长2倍增长
            int size = 1;
            int N = arr.length;
            //当步长长度不超过数组长度时则开始进行左右数组边界划分 并合并
            //size从1开始，左数组个数1 右也是1 假设N = 8 , 第一组索引为[0,1] 第二组索引[2,3]..
            //来到步长 2  左数组个数2 右也是2 共4个第一组索引[0,3]
            while (size < N) {
                //当前左组的第一个位置，一直都是从0开始的
                int L = 0;
                //开始按当前步长为1 开始进行后续每一组的遍历 直到越界
                while (L < N) {
                    //如果步长大于等于左边界到尾索引的长度 则直接退出当次步长 进入步长*2的外层遍历
                    if (size >= N - L) break;
                    //L加上步长还没到最后一个元素，则继续下面的判断中点和右组边界
                    int M = L + size - 1;
                    //右数组 就是从M+1....R,这里需要判断，从M中点加步长size会不会溢出数组尾索引，不会就
                    //直接M+size得到右数组的右边界。 否则就要取尾索引N-M-1
                    int R = M + Math.min(size, N - M - 1);
                    //找到了L R M 就调合并函数了
                    merge(arr, L, M, R);
                    //此时就把第一组索引是0,1 两个左右数组排序好了，接着要到下一组，l就从r+1开始
                    L = R + 1;
                }
                //这里到下次步长时要判断下，是否*2来到下次步长会不会溢出整数最大值
                //注意不能 = N/2退出，因为除法是向下取整，比如N=9,9/2=4,假设步长来到4，
                // 第一组 左[0,3] 右[4,7] 然后还最后[8] 前面逻辑是直接跳出不处理，
                // 就会漏了最后这个数没进行排序，所以不能== N/2退出
                if (size > N / 2) {
                    break;
                }
                //步长增长一倍 *2
                size <<= 1;
            }
        }
    
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            }
            return arr;
        }
    
        // for test
        public static int[] copyArray(int[] arr) {
            if (arr == null) {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                res[i] = arr[i];
            }
            return res;
        }
    
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
                return false;
            }
            if (arr1 == null && arr2 == null) {
                return true;
            }
            if (arr1.length != arr2.length) {
                return false;
            }
            for (int i = 0; i < arr1.length; i++) {
                if (arr1[i] != arr2[i]) {
                    return false;
                }
            }
            return true;
        }
    
        // for test
        public static void printArray(int[] arr) {
            if (arr == null) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // for test
        public static void main(String[] args) {
            int testTime = 500000;
            int maxSize = 100;
            int maxValue = 100;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
                int[] arr2 = copyArray(arr1);
    //            mergeSort1(arr1);
                mergeSort2(arr2);
    //            if (!isEqual(arr1, arr2)) {
    //                System.out.println("出错了！");
    //                printArray(arr1);
    //                printArray(arr2);
    //                break;
    //            }
            }
            System.out.println("测试结束");
        }
    }

### 二、求数组小和 ###

使用归并排序来解决小和问题

> 题意：  
> 在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小 和。 求数组小和。  
> 例子： \[1,3,4,2,5\]  
> 1左边比1小的数：没有  
> 3左边比3小的数：1  
> 4左边比4小的数：1、3  
> 2左边比2小的数：1  
> 5左边比5小的数：1、3、4、 2  
> 所以数组的小和为1+1+3+1+1+3+4+2=16

> \* 核心思路：归并排序，每次合并时，右数组元素r大于左数组元素l时 相当于r往右全部元素都是  
>  \* 大于l的，假设n个，将n\*l 得到当次合并 题目所需的 比较左边的比该元素小的总和，  
>  \* 因为是左边比自己小，那么就是从右数组来判断,注意再归并的时候，如果两指针大小相等，  
>  \* 注意是要移动右指针，不能移动左指针，因为要看右数组中有没有比左数组当前元素大的，  
>  \* 如果有要接着累计和，假设你跳过的是左指针，假设值是4, \[1,2,4,5\] \[3,4,5,6\],而右  
>  \* 数组中还有5，6是大于4的，跳过左边指针就会缺少两个4 = 总值少了8，所以相等时要右边  
>  \* 指针往前。

package class04;
    
    /**
     * 在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。
     * 例子： [1,3,4,2,5]
     * 1左边比1小的数：没有
     * 3左边比3小的数：1
     * 4左边比4小的数：1、3
     * 2左边比2小的数：1
     * 5左边比5小的数：1、3、4、 2
     * 所以数组的小和为1+1+3+1+1+3+4+2=16
     *
     * 核心思路：归并排序，每次合并时，右数组元素r大于左数组元素l时 相当于r往右全部元素都是
     *      大于l的，假设n个，将n*l 得到当次合并 题目所需的  比较左边的比该元素小的总和，
     *      因为是左边比自己小，那么就是从右数组来判断,注意再归并的时候，如果两指针大小相等，
     *      注意是要移动右指针，不能移动左指针，因为要看右数组中有没有比左数组当前元素大的，
     *      如果有要接着累计和，假设你跳过的是左指针，假设值是4, [1,2,4,5] [3,4,5,6],而右
     *      数组中还有5，6是大于4的，跳过左边指针就会缺少两个4 = 总值少了8，所以相等时要右边
     *      指针往前。
     */
    
    public class SmallSum {
        public static int smallSum(int[] arr){
            if(arr == null || arr.length <2) return 0;
            return process(arr,0,arr.length-1);
        }
    
        public static int process(int[] arr, int l ,int r){
            if(l == r) return 0;
            int mid = l + ((r-l)>>1);
            //依次返回递归左右数组和合并左右数组的总和
            return process(arr,l,mid)+
                    process(arr,mid+1,r)+
                     merge(arr,l,mid,r);
        }
        public static int merge(int[] arr,int l ,int m ,int r){
            int[] help = new int[r-l+1];
            int index = 0;
            int p1 = l ;
            int p2 = m+1;
            //需要多定义一个变量来保存小数和
            int ans = 0;
            while(p1 <= m && p2 <= r){
                ans += arr[p1] < arr[p2] ? (r-p2+1)*arr[p1]:0;
                help[index++] = arr[p1] < arr[p2]? arr[p1++]:arr[p2++];
            }
            while(p1<=m){
                help[index++] = arr[p1++];
            }
            while(p2<=r){
                help[index++] = arr[p2++];
            }
            for(int i = 0 ;i<help.length;i++){
                arr[l+i] = help[i];
            }
            return ans;
        }
    
        // for test
        public static int comparator(int[] arr) {
            if (arr == null || arr.length < 2) {
                return 0;
            }
            int res = 0;
            for (int i = 1; i < arr.length; i++) {
                for (int j = 0; j < i; j++) {
                    res += arr[j] < arr[i] ? arr[j] : 0;
                }
            }
            return res;
        }
    
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            }
            return arr;
        }
    
        // for test
        public static int[] copyArray(int[] arr) {
            if (arr == null) {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                res[i] = arr[i];
            }
            return res;
        }
    
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
                return false;
            }
            if (arr1 == null && arr2 == null) {
                return true;
            }
            if (arr1.length != arr2.length) {
                return false;
            }
            for (int i = 0; i < arr1.length; i++) {
                if (arr1[i] != arr2[i]) {
                    return false;
                }
            }
            return true;
        }
    
        // for test
        public static void printArray(int[] arr) {
            if (arr == null) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // for test
        public static void main(String[] args) {
            int testTime = 500000;
            int maxSize = 100;
            int maxValue = 100;
            boolean succeed = true;
            for (int i = 0; i < testTime; i++) {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
                int[] arr2 = copyArray(arr1);
                if (smallSum(arr1) != comparator(arr2)) {
                    succeed = false;
                    printArray(arr1);
                    printArray(arr2);
                    break;
                }
            }
            System.out.println(succeed ? "Nice!" : "Fucking fucked!");
        }
    
    }

### 三、求数组逆序对 ###

> 在一个数组中，  
> 任何一个前面的数a，和任何一个后面的数b，  
> 如果(a,b)是降序的，就称为逆序对  
> 返回数组中所有的逆序对

核心思路：利用归排序，左右数组递归合并累计逆序对，因为是左边数大于右边数，在合并函数中，遍历需要从数组的最右边界开始往左移，如果左侧指针p1大于右侧指针p2，那么就能得到p2往右的全部元素都是小于p1的 因为这个数组在合并前是排序好的了。 那么就得到p1 有 p2-m对 依次遍历

package class04;
    
    public class ReversePair {
        public static int reversePairNumber(int[] arr){
            if(arr ==null || arr.length < 2) return 0;
            return process(arr,0,arr.length-1);
        }
    
        // arr[L..R]既要排好序，也要求逆序对数量返回
        // 所有merge时，产生的逆序对数量，累加，返回
        // 左 排序 merge并产生逆序对数量
        // 右 排序 merge并产生逆序对数量
        public static int process(int[] arr,int l,int r){
            if(l == r)return 0;
            int m = l + ((r-l)>>1);
            return process(arr,l,m) +
                    process(arr,m+1,r)+
                    merge(arr,l,m,r);
        }
        public static int merge(int[] arr,int l ,int m ,int r){
            int[] help = new int[r-l+1];
            //计算的是左大右小，逆序，这里有个技巧就是索引指针要从最后一个元素开始，
            //也就是先放大的元素入数组，一旦左侧的值小于右侧的值，那么右侧往右全部
            //元素就是都小于当前左侧的，所以就能求出该左侧值有多少对逆序对了。
            int index = help.length-1;
            int p1 = m;
            int p2 = r;
            int ans = 0;
            while(p1 >=l && p2 >=m+1){
                //索引都从最右侧开始，即从大值开始比较，假设p1大于p2,那么就满足题目
                //所说的逆序对，左数大于右数，那此时m+1...p2整个区间元素从右往左是降序
                //所以全部元素都比p1小，那p1这个元素 就有 p2-(m+1) +1 对逆序对
                //如果p2大于p1 那就返回0，然后指针就要前移p2
                ans += arr[p1]>arr[p2]?p2-m:0;
                //p1大于p2 大数入数组，p1入并且前移 假设相等，就需要p2入，前移p2
                //因为这里假设是前移p1,也可能会漏了p1这个元素还有存在的逆序对
                help[index--] = arr[p1]>arr[p2]?arr[p1--]:arr[p2--];
            }
            while(p1 >= l){
                help[index--] = arr[p1--];
            }
            while(p2 >= m+1){
                help[index--] = arr[p2--];
            }
            //别忘了要把数组赋值到原数组
            for(int i = 0 ;i<help.length;i++){
                arr[l+i] = help[i];
            }
            return ans;
        }
    
        // for test
        public static int comparator(int[] arr) {
            int ans = 0;
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[i] > arr[j]) {
                        ans++;
                    }
                }
            }
            return ans;
        }
    
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            }
            return arr;
        }
    
        // for test
        public static int[] copyArray(int[] arr) {
            if (arr == null) {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                res[i] = arr[i];
            }
            return res;
        }
    
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
                return false;
            }
            if (arr1 == null && arr2 == null) {
                return true;
            }
            if (arr1.length != arr2.length) {
                return false;
            }
            for (int i = 0; i < arr1.length; i++) {
                if (arr1[i] != arr2[i]) {
                    return false;
                }
            }
            return true;
        }
    
        // for test
        public static void printArray(int[] arr) {
            if (arr == null) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // for test
        public static void main(String[] args) {
            int testTime = 500000;
            int maxSize = 100;
            int maxValue = 100;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
                int[] arr2 = copyArray(arr1);
                if (reversePairNumber(arr1) != comparator(arr2)) {
                    System.out.println("Oops!");
                    printArray(arr1);
                    printArray(arr2);
                    break;
                }
            }
            System.out.println("测试结束");
        }
    }

### 四、对于每个数num，求有多少个后面的数 \* 2依然<num，求总个数 ###

> 在一个数组中，  
> 对于每个数num，求有多少个后面的数 \* 2依然<num，求总个数  
> 比如：\[3,1,7,0,2\]  
> 3的后面有：1，0  
> 1的后面有：0  
> 7的后面有：0，2  
> 0的后面没有  
> 2的后面没有  
> 所以总共有5个

核心思路：还是用归并排序，这里就缺少像前面的题目求解时的隐藏的单调性特征，所以，我们在合并函数中，应该先单独遍历求符合右边的数\*2小于左边的数 ，得到后再返回结果，而合并两数组并且赋值给原数组的动作我们就拆分出来 ，因为如果在合并，左右指针前进的时候，你无法得到一个单调性特性，能一次判断出左侧的数，大于右侧一批元素的时候。

package class04;
    
    public class BiggerThanRightTwice {
        public static int reversePairs(int[] arr) {
            if(arr == null || arr.length <2)return 0;
            return process(arr,0,arr.length-1);
        }
    
        public static int process(int[] arr, int l, int r) {
            if(l == r) return 0;
            int mid = l + ((r-l)>>1);
            return process(arr,l,mid)+
                    process(arr,mid+1,r)+
                    merge(arr,l,mid,r);
        }
    
        public static int merge(int[] arr, int l, int m, int r) {
            //这个求解，需要和在合并的时候分开，因为要求小于当前值2倍这个取数是没有
            //单调性的，像前面的小数和 这些都有一个规律判断后面的元素就是符合的，而这个却没有
            //乘以2就不确定有单调性了
            //定义右数组的起始索引，判断索引走过多少个元素 就能得到左侧当前数有多少个符合元素
            int rWindow= m+1;
            int ans = 0;
            //遍历左数组的元素，依次与右数组中的元素判断，符合则索引前移
            for(int i =l ;i<=m;i++){
                //注意*2可能溢出，所以需要转long长整形
                while(rWindow<=r && (long)arr[i]> (long) arr[rWindow]*2){
                    rWindow++;
                }
                //跳出循环后，说明可以是越界了或者不符合条件。 而当前rWindow是不符合的元素，
                //真正符合的是从m+1 .... rWindow-1
                ans += rWindow-m -1;
            }
            int[] help = new int[r-l+1];
            int index = 0;
            int p1 = l;
            int p2 = m+1;
            while (p1<=m && p2<=r){
                help[index++] = arr[p1] <= arr[p2]? arr[p1++]:arr[p2++];
            }
            while(p1<=m){
                help[index++] = arr[p1++];
            }
    
            while(p2<=r){
                help[index++] = arr[p2++];
            }
            for(int i = 0;i<help.length;i++){
                arr[l+i] =help[i];
            }
            return ans;
        }
    
        // for test
        public static int comparator(int[] arr) {
            int ans = 0;
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[i] > (arr[j] << 1)) {
                        ans++;
                    }
                }
            }
            return ans;
        }
    
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
            }
            return arr;
        }
    
        // for test
        public static int[] copyArray(int[] arr) {
            if (arr == null) {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                res[i] = arr[i];
            }
            return res;
        }
    
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
                return false;
            }
            if (arr1 == null && arr2 == null) {
                return true;
            }
            if (arr1.length != arr2.length) {
                return false;
            }
            for (int i = 0; i < arr1.length; i++) {
                if (arr1[i] != arr2[i]) {
                    return false;
                }
            }
            return true;
        }
    
        // for test
        public static void printArray(int[] arr) {
            if (arr == null) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // for test
        public static void main(String[] args) {
            int testTime = 500000;
            int maxSize = 100;
            int maxValue = 100;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
                int[] arr2 = copyArray(arr1);
                if (reversePairs(arr1) != comparator(arr2)) {
                    System.out.println("Oops!");
                    printArray(arr1);
                    printArray(arr2);
                    break;
                }
            }
            System.out.println("测试结束");
        }
    
    }

### 五、327. 区间和的个数 ###

[327. 区间和的个数][327.]

![cb5736d0110856a1e76b9cb1a0478672.png][]

**核心思路：**

> 改写归并排序，根据题意求区间，可以设置一个前缀和数组，长度与题给数组一样，i索引存放数组中0-i区间元素和。在合并逻辑前找出当前左右数组符合该区间和的对数：  
> 在右数组中 m+1...r ，从左到右遍历元素，假设来到第一个arr\[m+1\] 值为x,是表示是0-m+1区间元素和，则以m+1位置为结尾的区间，比如0-m+1,1-m+1...等等多种区间，有多少个区间和是在题目要求的\[lower,upper\]范围上。为了结合归并排序的用法，我们换个逻辑，来判断这个区间：  
> 相当于求解在m+1 之前，即0...m区间多种区间前缀和中，有多少个前缀和是在\[x-upper,x-lower\]的，前后是一一对应的。

> 比如要求区间为\[10,40\] 假设右数组来到第17个即arr\[16\] 此时值为100 ，表示从0-16共17个元素和为100，求以arr\[16\]为结尾的区间有多少个区间和在10-40，也就是在arr\[0-15\]区间和为 \[100-40,100-10\] 即\[60,90\]的有多少个区间，因为前面的在\[60,90\]，那肯定存在一个后面的到17位置区间的和是在10-40的  
> 1.首先 -0 即全部前缀和，arr\[16\] 是不满足的因为和为100  
> 2接着-arr\[0\] arr\[0\] 假设为10，10不在60-90，arr\[1-16\]则为100-10=90，不在10-40,不满足  
> 3.接着-arr\[1\] 假设为70，在60-90，arr\[2-16\] 则为100-70=30，在10-40 满足 +1  
> 4.接着-arr\[2\] 假设为80，在60-90，arr\[3-16\] 则为20，在10-40 满足 +1.....

代码如下：

package class05;
    
    import java.util.Arrays;
    
    /**
     * 给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
     *
     * 区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
     * 示例 1：
     *
     * 输入：nums = [-2,5,-1], lower = -2, upper = 2
     * 输出：3
     * 解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
     */
    public class CountOfRangeSum {
    
        public static int countRangeSum(int[] nums, int lower, int upper) {
            if(nums == null || nums.length == 0) return 0;
            //根据题意，将数组转换成一个前缀和数组，即i位置值为0-i区间数据元素的和,注意要用long类型，累加防止整数溢出
            long[] sum = new long[nums.length];
            sum[0] = nums[0]; //先赋值第一个，第一个前缀和就是只有自己
            for(int i = 1;i<sum.length;i++){
                sum[i] = nums[i] + sum[i-1];
            }
            //归并排序传入的是前缀和数组，用来处理题意要求的区间
            return process(sum,0,sum.length-1,lower,upper);
        }
        public static int process(long[] arr,int l ,int r,int lower,int upper){
            //base case:左右索引相等，指向前缀和数组中同一个值，因为合并函数是严格确保了左右数组都有，所以这种特例会漏了
            // 需要单独处理。那么就表示，从0-l个元素区间的和，判断是否在区间内，在则返回1，递归中进行累加
            if(l == r){
                return arr[l] >= lower && arr[l] <= upper ? 1 :0;
            }
            int m = l + ((r-l)>>1);
            return process(arr,l,m,lower,upper) +
                    process(arr,m+1,r,lower,upper)+
                    merge(arr,l,m,r,lower,upper);
        }
        public static int merge(long[] arr,int l, int m, int r,int lower,int upper){
            //题意是找区间值符合[lower,upper]，那么意思就是在每个元素i往左的全部组合区间是否存在[lower,upper]，可以
            //转换成i元素之前的不包括i,的前缀和中，有多少个前缀和在[arr[i]-upper,arr[i]-lower]，
            //这样处理就能一次循环中得到右数组元素为结尾的在左数组区间，一共有多少个符合的前缀和。
            //合并前先判断 右数组[m+1,r]中从左往右每一个元素i，在左数组[l,m]中依次遍历匹配是否在左数组中存在有
            // [[arr[i]-upper,arr[i]-lower]的前缀和 有则获取
            int ans = 0;
            //区间是在左数组中找的 所以范围在l,m之间
            int windowL = l;
            int windowR = l;
            //外层遍历每个右数组元素
            for(int i = m+1;i<=r;i++){
                //根据前面提到的转换逻辑，定义出左数组的左右边界范围
                long max = arr[i] - lower;
                long min = arr[i] - upper;
                //内层遍历左数组的元素所以左右指针都是不超过m
                //这里遍历左指针是小于min  右指针是大于等于max 所以右指针跳出时是会多出一个不符合的值的，就是左闭右开
                while(windowR<=m && arr[windowR]<=max){
                    windowR++;
                }
                while(windowL<=m && arr[windowL]<min){
                    windowL++;
                }
    
                //遍历完之后就开始累计左右指针包含了多少个区间符合的 [windowL,windowR)
                ans += windowR - windowL;
            }
    
            //下面就是合并逻辑
            long[] help = new long[r-l+1];
            int index = 0;
            int p1 = l;
            int p2 = m+1;
            while(p1<=m&&p2<=r){
                help[index++] = arr[p1]<=arr[p2]? arr[p1++]:arr[p2++];
            }
            while(p1<=m){
                help[index++] = arr[p1++];
            }
            while(p2<=r){
                help[index++] = arr[p2++];
            }
            for(int i =0;i<help.length;i++){
                arr[l+i] = help[i];
            }
            return ans;
        }
    }

[327.]: https://leetcode.cn/problems/count-of-range-sum/description/
[cb5736d0110856a1e76b9cb1a0478672.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/946de7aae62f409899474e4f03beee13.png