线段树模板

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5000005;
int t[N],a[N],n,m,lazy[N];
void pushup(int k)
{t[k]=t[k*2]+t[k*2+1];
}
void plusa(int l,int r,int k,int x)
{lazy[k]+=x;t[k]+=(r-l+1)*x;
}
void pushdown(int l,int r,int k)
{if(lazy[k]){int m=(l+r)/2;plusa(l,m,k*2,lazy[k]);plusa(m+1,r,k*2+1,lazy[k]);lazy[k]=0;}
}
void build(int k,int l,int r)
{if(l==r)t[k]=a[l];else{int m=(l+r)/2;build(k*2,l,m);build(k*2+1,m+1,r);pushup(k);}
}
void add(int L,int R,int x,int l,int r,int k)
{if(l>=L&&R>=r){plusa(l,r,k,x);return;}else{int m=(l+r)/2;pushdown(l,r,k);if(L<=m)add(L,R,x,l,m,k*2);if(R>m)add(L,R,x,m+1,r,k*2+1);pushup(k);}
}
int query(int L,int R,int l,int r,int k)
{if(L<=l&&r<=R)return t[k];int sum=0;int m=(l+r)/2;pushdown(l,r,k);if(L<=m)sum+=query(L,R,l,m,k*2);if(R>m)sum+=query(L,R,m+1,r,k*2+1);return sum;
} 
signed main()
{ios::sync_with_stdio(0);cin.tie(nullptr);cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];build(1,1,n);while(m--){int op,x,y;cin>>op>>x>>y;if(op==1){int k;cin>>k;add(x,y,k,1,n,1);}elsecout<<query(x,y,1,n,1)<<"\n";} return 0;
}