模板 - 树状数组

区间加值，区间求和的树状数组，通过差分来实现。

并没有线段树那么通用。

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

ll bit[100005];
ll bit2[100005];

int n;

void add(int x, ll v) {
    for(; x <= n; x += x & -x)
        bit[x] += v;
}

ll sum(int x) {
    ll res = 0;
    for(; x; x -= x & -x)
        res += bit[x];
    return res;
}

void add2(int x, ll v) {
    for(; x <= n; x += x & -x)
        bit2[x] += v;
}

ll sum2(int x) {
    ll res = 0;
    for(; x; x -= x & -x)
        res += bit2[x];
    return res;
}

ll ans(int n) {
    return 1ll * (n + 1) * sum(n) - sum2(n);
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int m;
    scanf("%d%d", &n, &m);

    for(int i = 1, x, px = 0; i <= n; ++i) {
        scanf("%d", &x);
        add(i, x - px);
        add2(i, 1ll * i * (x - px));
        px = x;
    }

    for(int i = 1; i <= m; ++i) {
        char op[5];
        scanf("%s", op);
        if(op[0] == 'C') {
            int l, r, d;
            scanf("%d%d%d", &l, &r, &d);
            add(l, d);
            add2(l, l * d);
            add(r + 1, -d);
            add2(r + 1, 1ll * (r + 1) * -d);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", ans(r) - ans(l - 1));
        }
    }
}

模板 - 树状数组

原文：https://www.cnblogs.com/Inko/p/11585807.html