【深进1.例1】求区间和

chen_zhe · 2022-03-19 12:47:08 · 题解

【深进1.例1】求区间和

前缀和差分模板题。

我们定义一个数列 \{a_n\} 的前缀和为 S_n=\sum \limits_{i=1}^n a_i=a_1+a_2+\dots+a_n。

有了前缀和之后，我们可以使用差分来进行静态的区间求和。具体而言，对于一个区间 [l,r]，区间的和 a_l+a_{l+1}+\dots+a_r=S_r-S_{l-1}。

证明的话直接展开，S_r=a_1+a_2+\dots+a_{l-1}+a_{l}+a_{l+1}+\dots+a_r，S_{l-1}=a_1+a_2+\dots+a_{l-1}，这样 S_r-S_{l-1} 便等于 a_l+a_{l+1}+\dots+a_r，即所求的区间和了，预处理出前缀和，单次就是 O(1) 复杂度可以完成的事情了。

参考代码（std）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
#include <vector>

using namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m,a[100050],s[100050];

int main()
{
    n=read();
    for (int i=1;i<=n;i++)
        s[i]=s[i-1]+(a[i]=read());
    m=read();
    for (int i=1;i<=m;i++)
    {
        int l=read(),r=read();
        cout << s[r]-s[l-1] << endl;
    }
    return 0;
}