思路与算法

令差分d[i]=a[i]-a[i-1]，区间加x等价于d[l]+=x、d[r+1]-=x。前r项的和为Σ(i≤r)(r-i+1)d[i]=r*Σd[i]-Σ(i-1)d[i]。用两棵树状数组分别维护d[i]与(i-1)d[i]，据此前缀公式求区间和。初始化时把各a[i]作为单点区间加，操作沿用相同函数。

正确性说明

差分的前缀还原出每项值，区间两端的差分改动恰好让区间内元素统一增加x、区间外不变。交换有限求和次序得到前缀和恒等式，两棵BIT的前缀查询分别给出该式两部分，所以前缀值准确。区间[l,r]再用prefix(r)-prefix(l-1)，因而所有更新和查询都符合协议，负数增量也满足同一线性关系。

复杂度

初始化两棵数组O(n)，逐个单点加入O(n log n)，q次操作O(q log n)，总时间O((n+q)log n)，空间O(n)，两份long long数组约16MB。包括加权差分在内用64位；n,q≤10^6、|a|,|x|≤10^6，整个区间和绝对值不超过10^18+10^12，仍在signed64内。

易错点

不是单点修改或区间赋值，操作1表示区间每项加x。r=n时r+1超出BIT有效长度，更新循环直接结束即可。必须算l-1前缀、并把乘法先提升为long long。库内J0344只有10万且限定正数，本题百万规模并允许负数，作为完整范围版本保留。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct BIT {
    int n;
    vector<long long> a;
    BIT(int n) : n(n), a(n + 1) {
    }
    void add(int x, long long v) {
        for (; x <= n; x += x & -x)
            a[x] += v;
    }
    long long sum(int x) {
        long long s = 0;
        for (; x; x -= x & -x)
            s += a[x];
        return s;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    BIT a(n), b(n);
    auto add = [&](int l, int r, long long x) {
        a.add(l, x);
        a.add(r + 1, -x);
        b.add(l, x * (l - 1));
        b.add(r + 1, -x * r);
    };
    auto prefix = [&](int r) {
        return r * a.sum(r) - b.sum(r);
    };
    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        add(i, i, x);
    }
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            add(l, r, x);
        } else
            cout << prefix(r) - prefix(l - 1) << '\n';
    }
}