Using partial_sum() with long long values

Question

I am solving a problem for which, I need to calculate the prefix and suffix sum values. When I do it this way:

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        long n=size(nums);
        vector<long long> left(n,0ll), right(n,0ll);
        
        partial_sum(begin(nums), end(nums), begin(left));
        partial_sum(rbegin(nums), rend(nums), rbegin(right));
        
        return 0;
    }
};

This works fine for smaller input values, but when the input is very large, I get an error:

Line 258: Char 43: runtime error: signed integer overflow: 2147453785 + 36049 cannot be represented in type 'int' (stl_numeric.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_numeric.h:267:43

However, the traditional for-loop works just fine for all the inputs, including the very large ones:

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        long n=size(nums);
        vector<long long> left(n,0ll), right(n,0ll);
        
        left[0]=nums[0];
        for(int i=1; i<n; i++) {
            left[i]=left[i-1]+nums[i];
        }
        
        right[n-1]=nums[n-1];
        for(int i=n-2; i>=0; i--) {
            right[i]=right[i+1]+nums[i];
        }

        return 0;
    }
};

What am I missing about the usage of partial_sum()?

Answer 1

std::partial_sum() is defined such that the accumulator type is that as the type of the input range element:

typename std::iterator_traits<InputIt>::value_type sum = *first;
...

This is also true for an overload that takes a custom binary operation. There is no simple way to override that type - you have to somehow modify the input range itself.

If you really want to use std::partial_sum(), you could either copy the input range into std::vector<long long> or transform it on-fly using boost::transform_iterator:

std::vector<int> in(5, INT_MAX);
std::vector<long long> out(in.size());

auto cast_to_long_long = [](int v){ return static_cast<long long>(v); };
auto first = boost::make_transform_iterator(in.begin(), cast_to_long_long);
auto last  = boost::make_transform_iterator(in.end(),   cast_to_long_long);

std::partial_sum(first, last, out.begin());

Demo

However, the simplest solution is to use std::inclusive_scan(), which accepts the initial value that determines the accumulator type:

std::inclusive_scan(in.begin(), in.end(), out.begin(), std::plus(), 0LL);

Demo