对于求数组 $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$ )，那么我们考虑去优化他；

这里我们会用到类似高中学过的数列知识，我们需要构造一个新数组 $S[n]$，$S[n]$ 所表示的是数组 $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]$ 时导致的数组下标越界问题，具体看下面代码实现；
3. 凡是涉及到加和的，一定小心爆 $int$;

参考答案：

#include<iostream>

using namespace std;

const int N = 200010;
int n, m;
int a[N], s[N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

    while (m--)
    {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}