Tree Recovery 树状数组区间修改和求和

题目链接

下面的题解转于传送门
对于想要学习区间修改和单点输出的同学们可以去看这篇文章
  传送门

假设数组a是原数组，b是a的差分数组，由前缀和的定义，我们求前n个元素的和，即

详细过程如下：
a1 + a2 + ... + an = b1 + (b1 + b2) + ....+ (b1 + b2 + b3 + ... bn) ->n * b1 + (n - 1) * b2 + ... + bn

所以我们要先对原数组a进行差分，得到差分数组b，才对b[i]和b[i]*i分别维护一个树状数组tb和tc，
而l到r的和变为
[(r + 1) * sum(tb, r) - sum(tc, r)]-[(l + 1) * sum(tb, l) - sum(tc, l)]

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;
typedef __int128 LL;

const int maxn = 100000 + 5;
const int Mod = 1e9 + 7;

ll a[maxn],b[maxn],tb[maxn],tc[maxn];
//b为差分数组,tb为b[i] 要维护的树状数组,tc为要树状数组维护的b[i] * i;
int n,m;

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

void add(int x,ll v)
{
    ll val = x * v;
    for(int i = x; i <= n; i += lowbit(i)){
        tb[i] += v;
        tc[i] += val;
    }
}

void chafen_add(int l,int r,ll val)
{
    add(l,val);
    add(r + 1,-val);
}

ll Query(ll a[], int x)
{
    ll res = 0;
    for(int i = x; i > 0; i -= lowbit(i)){
        res += a[i];
    }
    return res;
}

ll Query_sum(int x)
{
    return (x + 1) * Query(tb,x) - Query(tc ,x);
}

ll Q_of_Q_sum(int l,int r)
{
    return Query_sum(r) - Query_sum(l - 1);
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        b[i] = a[i] - a[i - 1];
        add(i,b[i]);
    }
    char s[2];
    while(m--){
        cin>>s;
        if(s[0] == 'Q'){
            int l,r;
            cin>>l>>r;
            ll res = Q_of_Q_sum(l,r);
            cout<<res<<endl;
        }
        else{
            ll x,y,z;
            cin>>x>>y>>z;
            chafen_add(x,y,z);
        }
    }
}