使用partial_sum()处理long long值时为何出现整数溢出？

问题场景 #

计算前缀和与后缀和时，使用partial_sum()的实现在大规模输入下触发整数溢出错误，但传统for循环版本可正常运行。

出错的partial_sum实现代码 #

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

触发的错误信息 #

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

正常运行的for循环实现代码 #

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

误区解析 #

问题核心在于partial_sum()的类型推导规则：

• 默认情况下，partial_sum会使用输入序列的元素类型（这里是int）进行累加计算，哪怕输出目标是long long类型的容器。累加过程中，中间结果始终以int存储，当数值超过int的最大值时，直接触发溢出。
• 而for循环版本中，left[i]是long long类型，nums[i]会被隐式转换为long long后再与前一个long long类型的前缀和相加，整个累加过程都以long long类型执行，不会出现溢出。

修复后的partial_sum实现 #

要解决这个问题，需显式指定累加的类型，传入自定义加法函数确保中间结果用long long计算：

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        long n=size(nums);
        vector<long long> left(n,0ll), right(n,0ll);
        
        // 显式指定累加类型为long long
        partial_sum(begin(nums), end(nums), begin(left), 
            [](long long prev_sum, int curr_num) {
                return prev_sum + curr_num;
            });
        partial_sum(rbegin(nums), rend(nums), rbegin(right),
            [](long long prev_sum, int curr_num) {
                return prev_sum + curr_num;
            });
        
        return 0;
    }
};

内容的提问来源于stack exchange，提问作者J. Doe