线段树（P3372）

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long int ll;
const int maxn=1e6+10;
ll a[maxn],tap[maxn<<2],ans[maxn<<2];
ll ls(ll x){
    return x<<1;
}
ll rs(ll x){
    return x<<1|1;
}
void add(ll p){
    ans[p]=ans[ls(p)]+ans[rs(p)];
}
void f(ll l,ll r,ll p,ll k){
    tap[p]+=k;
    ans[p]+=k*(r-l+1);
}
void top(ll p,ll l,ll r){
    ll mod=(l+r)/2;
    f(l,mod,ls(p),tap[p]);
    f(mod+1,r,rs(p),tap[p]);
    tap[p]=0;
}
ll sum(ll l,ll r,ll sl,ll sr,ll p){
    ll su=0,mod=(l+r)/2;
    if(sl<=l&&sr>=r)return ans[p];
    top(p,l,r);
    if(mod>=sl)su+=sum(l,mod,sl,sr,ls(p));
    if(mod<sr)su+=sum(mod+1,r,sl,sr,rs(p));
    return su;
}
void push(ll l,ll r,ll sl,ll sr,ll p,ll k){
    if(sl<=l&&sr>=r){
        ans[p]+=k*(r-l+1);
        tap[p]+=k;
        return ;
    }
    ll mod=(l+r)/2;
    top(p,l,r);
    if(mod>=sl)push(l,mod,sl,sr,ls(p),k);
    if(mod<sr)push(mod+1,r,sl,sr,rs(p),k);
    add(p);
}
void build(ll l,ll r,ll p){
    tap[p]=0;
    ll mod=(l+r)/2;
    if(l==r){ans[p]=a[r];return ;}
    build(l,mod,ls(p));
    build(mod+1,r,rs(p));
    add(p);
}
int main(){
    int n,m,s,l,r;ll k;
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,n,1);
    for(int i=0;i<m;i++){
        scanf("%d",&s);
        if(s==1){
            scanf("%d%d%lld",&l,&r,&k);
            push(1,n,l,r,1,k);
        }
        else{
            scanf("%d%d",&l,&r);
            printf("%lld\n",sum(1,n,l,r,1));
        }
    }

    return 0;
}