python/TangDou/AcWing/SegmentTree/ZKW/P3372_4.cpp

#include <iostream>
using namespace std;
const int N = 1000010;
typedef long long LL;

int n, m; // n个元素，m次操作
int a[N]; //原始数组

LL tr1[N], tr2[N]; //① 保存基底数组为原数组差分数组的树状数组 ② i*b[i]的前缀和数组

//树状数组模板
#define lowbit(x) (x & -x)

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr1[i] += c, tr2[i] += x * c;
}

LL sum(int x) {
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += (x + 1) * tr1[i] - tr2[i];
    return res;
}

//快读
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int main() {
    n = read(), m = read();
    int x, y, d, op;
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        add(i, a[i] - a[i - 1]); //保存基底是差分数组的树状数组
    }

    while (m--) {
        op = read(), x = read(), y = read();
        if (op == 1) {
            d = read();
            add(x, d), add(y + 1, -d); //维护差分
        } else                         //查询
            printf("%lld\n", sum(y) - sum(x - 1));
    }
    return 0;
}