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

题目链接：https://www.acwing.com/problem/content/description/244/

思路

维护了两个差分树状数组，差分树状数组的区间查询其实就是求一个近似半矩阵的区域，通过近似补矩阵的方法，就可以通过两个比较好算的两个求和，让两个和做差得到真正的区间和

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N,M;
int arr[maxn];
ll tr1[maxn],tr2[maxn];

int lowbit(int x){
    return x&-x;
}
void add(ll tr[],int idx,ll v){
    for(int i = idx;i<=N;i += lowbit(i)) tr[i] += v;
}
ll pre_sum(ll tr[],int r){
    ll sum = 0;
    for(int i = r;i>=1;i -= lowbit(i)) sum += tr[i];
    return sum;
}
ll query(int l,int r){
    ll sumr = pre_sum(tr1,r)*(r+1) - pre_sum(tr2,r);
    ll suml = pre_sum(tr1,l-1)*(l) - pre_sum(tr2,l-1);
    return sumr - suml;
}
int main(){
    // debug;
    ios;
    cin>>N>>M;
    for(int i = 1;i<=N;i++) cin>>arr[i];
    for(int i = 1;i<=N;i++){
        ll ca = arr[i] - arr[i-1];
        add(tr1,i,ca);
        add(tr2,i,ca*i);
    }
    while(M--){
        string op;int l,r,d;
        cin>>op;
        if(op == "Q"){
            cin>>l>>r;
            cout<<query(l,r)<<endl;
        }else{
            cin>>l>>r>>d;
            add(tr1,l,d);add(tr1,r+1,-d);
            add(tr2,l,l*d);add(tr2,r+1,-(r+1)*(ll)d);
        }
    }
    return 0;
}