对于求数组 $a[ n ]$ 中某一个区间 $[ L , R ]$的和，我们很容易可以想到，

for(int i = L;i <= R; ++i ) sum += a[i];

但是这样写时间复杂度为 $O(n)$，如果题目还要求 $n$ 次查询，时间复杂度就来到了 $O(n^2)$ , 对于 $10^5$ 的数据，很明显 $10^{10}>10^8$ 会超时, ( 多嘴一句，$c++$ $1$ 秒钟不要超过 $10^8$ )，那么我们考虑去优化他；

这里我们会用到类似高中学过的数列知识，我们需要构造一个新数组 $Sn$，$Sn$ 所表示的是数组 $a[n]$ 前 $n$ 项的和，便于理解，我使用下面几个等式当作例子；

$s[0] = 0；$

$s[1] = a[1]；$

$s[2] = a[1] + a[2]；$

$S[L]=a[1]+a[2]+a[3]+a[4]+... ... a[L]；$

$S[R]=a[1]+a[2]+a[3]+a[4]+... ... a[R]$

$S[n]=a[1]+a[2]+a[3]+a[4]+... ... a[n];$

这样我们在求某一个区间 $[ L , R ]$的和时，就不必费时 $O(n)$ 去跑一边 for(int i = L;i <= R; ++i ) sum += a[i];，可以直接用构造好的 $S[n]$ 数组直接 $S[R]-S[L-1]$ 便可在 $O(1)$ 的时间快速计算出数组 $[L,R]$ 区间和；

这里有两点需要特别注意

1. 是减去 $S[L-1]$ 不是 $S[L]$, 因为区间$[L,R]$ 包含第 $L$ 项；
2. 还有构建数组 $S[n]$ 时, $a[n]$ 数组下标要从 $1$ 开始，这避免了求 $S[1]$ 导致的数组下标越界问题，具体看下面代码实现；

参考答案：

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
LL a[N], s[N];
LL n, m;
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lld", &a[i]);
        s[i] += s[i - 1] + a[i];
    }
    while (m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%lld\n", s[r] - s[l - 1]);
    }
    return 0;
}