树状数组 POJ-3468 A Simple Problem with Integers

题目链接：[ POJ - 3468 ]

题目大意

给一个长度为n的数列，有Q次操作Q代表查询区间 a b之间的累加和，操作C代表将a-b区间的所有数加上c

题解

树状数组模板题，此题建立完整的一维树状数组板子

代码如下

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<vector>
using namespace std;

typedef long long ll;

ll n, m, k;

inline ll lowbit(ll x)
{
    return x & -x;
}

struct BIT {
    ll a[500050];
    void add(ll x, ll v) {
        for (x; x > 0; x -= lowbit(x))
            a[x] += v;
    }
    void addinv(ll x, ll v) {
        for (ll i = x; i <= n; i += lowbit(i))
            a[i] += x * v;
    }
    ll Sum(ll x) {
        ll res = 0;
        for(x; x <= n; x += lowbit(x))
            res += a[x];
        return res;
    }
    ll Suminv(ll x) {
        ll res = 0;
        for (x; x > 0; x -= lowbit(x))
            res += a[x];
        return res;
    }
}bit, bitinv;

ll sum(ll x)
{
    if (x)
        return bit.Sum(x) * x + bitinv.Suminv(x - 1);
    else
        return 0;
}

void add(ll l, ll r, ll c)
{
    bit.add(r, c);
    bitinv.addinv(r, c);
    if (l > 1) {
        bit.add(l - 1, -c);
        bitinv.addinv(l - 1, -c);
    }
}

int main(void)
{
    scanf("%lld%lld", &n, &m);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", &k);
        add(i, i, k);
    }
    getchar();

    char ch;
    ll l, r, c;
    while (m--) {
        scanf("%c %lld %lld", &ch, &l, &r);
        if (ch == 'Q')
            printf("%lld\n", sum(r) - sum(l - 1));

        if (ch == 'C') {
            scanf("%lld", &c);
            add(l, r, c);
        }
        getchar();
    }

    return 0;
}