树状数组

重点
1. 利用差分的思想，将区间修改转化成指令的单点修改
2. 通过公式变形，拆分出另一个前缀和数组
3. 树状数组的两种操作：单点修改，区间查询，维护前缀和数组

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 100010;
typedef long long LL;
int n, m;
LL tr1[N], tr2[N];
int a[N];

int lowbit(int x) {
    return x & -x;
}

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

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

LL f(int x) {
    return (LL)(x + 1) * sum(tr1, x) - sum(tr2, x);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        add(tr1, i, a[i] - a[i - 1]);
        add(tr2, i, (LL)i * (a[i] - a[i - 1]));
    }
    for (int i = 0; i < m; i++) {
        char s[2];
        int l, r, d;
        scanf("%s", s);
        if (s[0] == 'C') {
            scanf("%d%d%d", &l, &r, &d);
            add(tr1, l, d);
            add(tr1, r + 1, -d);
            add(tr2, l, (LL)l * d);
            add(tr2, r + 1, (LL)(r + 1) * -d);
        } else{
            scanf("%d%d", &l, &r);
            printf("%lld\n", f(r) - f(l - 1));
        }
    }

    return 0;
}