package com.jiucaiyuan.net.question;



/**

 * <pre>

 * 一个数组arr的小和=所有位置上的值，左侧比概述小的和，就是该数组的小和

 * 本示例是解法2

 *

 * 解法1.暴力解题，循环处理所有数组的数，找到左侧比所处理的数小的加入结果和中

 *      时间复杂度O(N^2)

 *

 * 解法2.转化为循环数组所有数，找出右侧比他大，即产生当前数加入到小和中

 *      求右边比arr[i]大，可以转化为归并思路处理

 *      划分左右两个进行排序，然后merge，在merge过程中，如果右侧比左侧大，则累计小和，否则直接合并，最后的累计值即是小和

 *   时间复杂度O(N*logN)

 * </pre>

 *

 * @Author jiucaiyuan  2022/3/29 22:57

 * @mail services@jiucaiyuan.net

 */



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);

    }



    /*

     * 合并arr[l,mid] 和 arr[mid+1,r] 两个数组

     */

    private static int merge(int[] arr, int l, int mid, int r) {

        int sum = 0;

        //合并后的数组

        int[] temp = new int[r - l + 1];

        int i = 0;

        int p1 = l;

        int p2 = mid + 1;

        //两个数组都有数时

        while (p1 <= mid && p2 <= r) {

            //相等不计算小和

            if (arr[p1] < arr[p2]) {

                sum += arr[p1] * (r - p2 + 1);

                temp[i++] = arr[p1++];

            } else {

                temp[i++] = arr[p2++];

            }

        }

        //前半段数组长

        while (p1 <= mid) {

            temp[i++] = arr[p1++];

        }

        //后半段数组长

        while (p2 <= r) {

            temp[i++] = arr[p2++];

        }

        //把合并后的temp数组复制到arr中

        for (int index = 0; index < temp.length; index++) {

            arr[l + index] = temp[index];

        }

        return sum;

    }



    public static void main(String[] args) {

        int[] arr = {1, 3, 4, 2, 5, 1};

        System.out.println(smallSum(arr));

    }

}