小和问题（C++实现）

归并求小和  在数组中求小和，既要排好序，也要求小和
小和：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和

用归并来实现

例子
[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
 

代码如下：

#include
#include

using namespace std;



int process(vector& arr, int L, int R);
int merge(vector& arr, int L, int M, int R);


int smallSum(vector& arr)//小和函数
{
    if (arr.empty())
    {
        return 0;
    }

    return process(arr, 0, arr.size() - 1);
}

int process(vector& 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);
           //小和等于左边排好序求小和+右边排好序求小和+merge求小和的结果
}

int merge(vector& arr,int L,int M,int R)
{
    vectorhelp;//创建一个辅助数组
    help.resize(R - L + 1);//开辟和arr一样的大小
    int i = 0, p1 = L, p2 = M + 1, res = 0;//res来接收小和 
    while (p1 <= M && p2 <= R)
    {
        res += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;//小和+=
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];//用一个临时数组来排序
    }
    while (p1 <= M)//如果右边临界了，把左边加入到辅助数组中
    {
        help[i++] = arr[p1++];
    }
    while (p2 <= R)//如果左边临界了 把右边加入到辅助数组中，上下只会中一个情况
    {
        help[i++] = arr[p2++];
    }
    for (int k = 0; k < help.size(); k++)//把临时数组倒回原数组
    {
        arr[L + k] = help[k];
    }
    return res;//返回小和
}


int main()
{

    //测试
    vectorv;
    v.push_back(1);
    v.push_back(3);
    v.push_back(4);
    v.push_back(2);
    v.push_back(5);
   

       

    cout << smallSum(v) << endl;//输出v数组的小和

    for (vector::iterator it = v.begin(); it != v.end(); it++)//输出排好序的数组
    {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}