C++求小和问题_求数列的小和c++

一个数组每个数左边比它大的数进行相加，遍历完数组即为小和

#include <iostream>
#include <vector>
 
using namespace std;
 
int merge(vector<int>& s, int l, int mid, int r) {
    int p1 = l;
    int p2 = mid + 1;
    int i = 0;
    int res = 0;
    vector<int> help(r - l + 1);
    while (p1 <= mid && p2 <= r) {
        res += s[p1] < s[p2] ? s[p1] * (r - p2 + 1) : 0;
        help[i++] = s[p1] <= s[p2] ? s[p1++] : s[p2++];
    }
 
    while (p1 <= mid) {
        help[i++] = s[p1++];
    }
    while (p2 <= r) {
        help[i++] = s[p2++];
    }
 
    for (i = 0; i < r - l + 1; i++) {
        s[l + i] = help[i];
    }
 
    return res;
}
 
int smallSum(vector<int>& s, int l, int r) {
    if (l == r) {
        return 0;
    }
    int mid = l + (r - l) / 2;
    return smallSum(s, l, mid) + smallSum(s, mid + 1, r) + merge(s, l, mid, r);
}
 
int main() {
    vector<int> s = {1, 2, 3, 4};
    cout << smallSum(s, 0, s.size() - 1);
}

过程为计算每个数的右边有几个数比它大，该数乘以数量即为该数的小和