(树状数组)AcWing 243. 一个简单的整数问题2

AcWing 243. 一个简单的整数问题2

本题：

1. 区间加

2. 区间求和

   
   

维护两个前缀和：

1. b[i]的前缀和
2. b[i] * i的前缀和

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
LL a[N], tr1[N], tr2[N];
int d[N];

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

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

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

LL getsum(int x) {
    return 1ll * get(tr1, x) * (x + 1) - get(tr2, x);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++) {
        d[i] = a[i] - a[i - 1];
        add(tr1, i, d[i]), add(tr2, i, 1ll * i * d[i]);
    }

    string op;
    while (m--) {
        cin >> op;
        int l, r, v;

        if (op[0] == 'Q') {
            cin >> l >> r;
            printf("%lld\n", getsum(r) - getsum(l - 1));
        } else {
            cin >> l >> r >> v;
            add(tr1, l, v), add(tr1, r + 1, -v);
            add(tr2, l, l * v), add(tr2, r + 1, 1ll * -v * (r + 1));
        }
    }

    return 0;
}