前缀和与差分

核心理解

前缀和把“每次重新累加一段区间”变成一次减法：sum(l, r) = prefix[r] - prefix[l - 1]。差分正好反过来：如果要让 [l, r] 全部加 x，只需在差分数组的 l 加 x、r + 1 减 x，最后还原一次即可。

• 前缀和适合：数组不修改、反复查询区间和。
• 差分适合：大量区间加、最后统一得到数组。
• 两者都以 1 为起点，prefix[0]、diff[n + 1] 要预留。

模板代码

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n + 2), prefix(n + 2), diff(n + 2);

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

    // 区间和：prefix[r] - prefix[l - 1]
    // 区间加 x：diff[l] += x, diff[r + 1] -= x
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            long long x;
            cin >> x;
            diff[l] += x;
            diff[r + 1] -= x;
        } else {
            cout << prefix[r] - prefix[l - 1] << '\n';
        }
    }

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

注意：上面的前缀和查询对应初始数组；如果操作中同时要求“区间加后再查询”，应改用双树状数组或线段树。