AcWing 795. 前缀和【c++详细题解】

水深无声 2021-09-03 06:32 466阅读 0赞

## 前缀和 ##

--------------------

**题目**

输入一个长度为n的整数序列。

接下来再输入m个询问，每个询问输入一对l, r。

对于每个询问，输出原序列中从第l个数到第r个数的和。

**输入格式**  
第一行包含两个整数n和m。

第二行包含n个整数，表示整数数列。

接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。

**输出格式**  
共m行，每行输出一个询问的结果。

**数据范围**  
1≤l≤r≤n,  
1≤n,m≤100000,  
−1000≤数列中元素的值≤1000  
**输入样例：**  
5 3  
2 1 3 6 4  
1 2  
1 3  
2 4  
**输出样例：**  
3  
6  
10

**具体做法：**

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

**求前缀和运算：**

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

**然后查询操作：**

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]`;

**图解**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]  
这样，对于每个询问，`只需要执行 sum[r]-sum[l-1]`。输出原序列中从第`l`个数到第r个数的和的时间复杂度变成了`O(1)`。

我们把它叫做**一维前缀和**。

**总结：**  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1][]

### [前缀和与差分的个人心得总结][Link 1] ###

**AC代码**

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/79c31599239546f39c746df83c023015.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/f11b15e9c7e343b9b06fbdc23cd95a25.png
[Link 1]: https://blog.csdn.net/weixin_45629285/article/details/111146240