【算法基础】前缀和

### 具体做法：

首先做一个预处理，定义一个`sum[]`数组，`sum[i]`代表`a`数组中前`i`个数的和。

### 求前缀和运算：

```c
const int N=1e5+10;
int sum[N],a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
for(int i=1;i<=n;i++)
{ 
    sum[i]=sum[i-1]+a[i];   
}
```

### 然后查询操作：

```c
 scanf("%d%d",&l,&r);
 printf("%d\n", sum[r]-sum[l-1]);
```

对于每次查询，只需执行`sum[r]-sum[l-1]` ，时间复杂度为`O(1)`

### 原理

`sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r];`
`sum[l-1]=a[1]+a[2]+a[3]+a[l-1];`
`sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r];`

### 图解

![](https://blog.fivk.cn/usr/uploads/2021/11/1931462236.png)

这样，对于每个询问，只需要执行 `sum[r]-sum[l-1]`。输出原序列中从第l个数到第r个数的和的时间复杂度变成了`O(1)`。

![](https://blog.fivk.cn/usr/uploads/2021/11/4254195108.png)

### AC代码

- 不滚动

```cpp
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int a[N],sum[N];
int main()
{
    int n,m;
    cin>>n>>m;
  
    for (int i = 1; i <= n; i++)
    	cin >> a[i];
  
    for(int i=1;i<=n;i++)
        sum[i] = a[i] + sum[i-1];

int l,r;
    cin>>l>>r;
    cout<<sum[r]-sum[l-1]<<endl;
    return 0;
}
```

- 滚动

```c
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int sum[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        sum[i]=x+sum[i-1];
    }
    int l,r;
    cin>>l>>r;
    cout<<sum[r]-sum[l-1]<<endl;
    return 0;
}
```

最后修改：2022 年 01 月 05 日