C++ 标准库中实现了前缀和函数 std::partial_sum,定义于头文件 <numeric> 中。 一个经典的例题: 暴力当然直接TLE 将上面代码的加起来的过程给优化一下,在输入阶段就将数组改写成前缀和的形式,输出的时候只要s[r]-s[l-1]就可以了 从一维扩展到二维,思考方式就多了 一个是基于容斥原理,什么是容斥原理?这涉及到数学上集合的概念了。先看下面的图: 现在给了A,B,C三个集合的元素数量,要求你求出至少在一个元素的数量,他不能是直接把三个集合的元素加起来,必须得把重复的元素给扣…