前缀和

适用场景

多次询问某个区间 [l, r] 的和。如果每次都循环累加会太慢，就可以先预处理前缀和。

核心思想

s[i] 表示前 i 个数的总和，则区间 [l, r] 的和为 s[r] - s[l - 1]。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<long long> s(n + 1, 0);

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

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << '\n';
    }
    return 0;
}

常见错误

• s[0] 没有设置为 0。
• 下标从 1 开始和从 0 开始混用。
• 数据和可能很大，忘记使用 long long。