ZKW线段树

#include <bits/stdc++.h>
using namespace std;
long long tree[400005],flag[400005],deep;
long long firstbit(int x){
int ans=0;
    x++;
    while(x){
        ans++;
        x>>=1;
    }
    return 1<<ans;
}
long long query(int lc,int rc){
long long l=lc+deep-1,r=rc+deep+1,j=rc-lc+1,ans=0,lv=0,rv=0;
    for(int p=1;l^r^1;p<<=1,l>>=1,r>>=1){
        ans+=flag[l]*lv;ans+=flag[r]*rv;
        if(~l&1){
            ans+=tree[l^1];lv+=p;
        }
        if( r&1){
            ans+=tree[r^1];rv+=p;
        }
    }
    ans+=flag[l]*lv;ans+=flag[r]*rv;
    for(l>>=1;l;l>>=1)
        ans+=flag[l]*j;
    return ans;
}
void update(int w,int v){
    for(tree[w+=deep]+=v,w>>=1;w;w>>=1)
        tree[w]+=v;
}
void update(int lc,int rc,int v){
int l=lc+deep-1,r=rc+deep+1,val=v*(rc-lc+1),lv=0,rv=0;
    for(int p=v;l^r^1;p<<=1,l>>=1,r>>=1){
        tree[l]+=lv;tree[r]+=rv;
        if(~l&1){
            flag[l^1]+=v;tree[l^1]+=p;lv+=p;
        }
        if( r&1){
            flag[r^1]+=v;tree[r^1]+=p;rv+=p;
        }
    }
    tree[l]+=lv;tree[r]+=rv;
    for(l>>=1;l;l>>=1)
        tree[l]+=val;
}
int main(){
int n,flag,k;
    ios::sync_with_stdio(false);
    cin>>n>>k;
    deep=firstbit(n);
    for(int i=1;i<=n;i++)
        cin>>tree[deep+i];
    for(int i=deep-1;i;i--)
        tree[i]=tree[i<<1]+tree[i<<1|1];
    while(k){
        k--;
        cin>>flag;
        if(flag==1){
            int a,b,c;
            cin>>a>>b>>c;
            update(a,b,c);
        }
        else if(flag==2){
            int a,b;
            cin>>a>>b;
            cout<<query(a,b)<<endl;
        }
        else {
            int a,b;
            cin>>a>>b;
            update(a,b);
        }    
    }
    return 0;
}