假设我们有一个大小为 N 的单索引整数数组 arr 并且我们想要计算：

对于 Q 个不同的对 (a,b) 满足1≤a≤b≤N。我们将使用以下示例与N = 6：

简单来说，对于每个查询，我们可以从索引 a 到索引 b遍历所有条目以将它们相加。因为我们有 Q 个查询，每个查询都需要O(N) 操作来计算总和，我们的总时间复杂度是 O(NQ)。对于大多数此类性质的问题，约束为 N，Q≤10^5，因此 NQ 大约为 10^10。这是不可接受的；大多数都会超过时间限制。

反而，我们可以使用前缀求和来处理这些数组求​​和查询。我们指定前缀和数组叫prefix。首先，因为我们对数组进行 1 索引，所以设置 prefix[0] = 0，然后对于索引 k 使得 1≤k≤n，定义前缀和数组如下：

这意味着前缀和数组的索引 k 处的元素存储了原始数组中从索引 1 到 k 的所有元素的总和。对于每个 1≤k≤n，这可以通过以下公式在 O(N) 中轻松计算：

在刚刚举的例子里，prefix就会变成这样：

 代码：

#include
using namespace std;
int main(){
    int n;
    cin>>n;
    int arr[n+1],prefix[n+1];
    arr[0] = 0;
    prefix[0] = 0;
    for(int k=1;k<=n;k++){
        cin>>arr[k];
        prefix[k] = prefix[k-1] + arr[k];
    }
    for(int k=1;k<=n;k++){
        cout< 
第一行输入n，再输入arr
 
效果：
 
 
 
 
完