动态开结点线段树板子。
#include<cstdio>
using namespace std;
typedef long long ll;
ll sumv[400005],delta[400005];
int lc[400005],rc[400005],tot,root;
void newnode(int &rt){
rt=++tot;
lc[rt]=rc[rt]=0;
sumv[rt]=delta[rt]=0;
}
void buildtree(int &rt,int l,int r){
if(!rt){
newnode(rt);
}
if(l==r){
scanf("%I64d",&sumv[rt]);
return;
}
int m=(l+r>>1);
buildtree(lc[rt],l,m);
buildtree(rc[rt],m+1,r);
sumv[rt]=sumv[lc[rt]]+sumv[rc[rt]];
}
void pushdown(int rt,int size)
{
if(!lc[rt]){
newnode(lc[rt]);
}
if(!rc[rt]){
newnode(rc[rt]);
}
if(delta[rt]){
delta[lc[rt]]+=delta[rt];
delta[rc[rt]]+=delta[rt];
sumv[lc[rt]]+=delta[rt]*(ll)(size-(size>>1));
sumv[rc[rt]]+=delta[rt]*(ll)(size>>1);
delta[rt]=0;
}
}
void update(int ql,int qr,ll v,int &rt,int l,int r){
if(!rt){
newnode(rt);
}
if(ql<=l && r<=qr){
delta[rt]+=v;
sumv[rt]+=v*(ll)(r-l+1);
return;
}
pushdown(rt,r-l+1);
int m=(l+r>>1);
if(ql<=m){
update(ql,qr,v,lc[rt],l,m);
}
if(m<qr){
update(ql,qr,v,rc[rt],m+1,r);
}
sumv[rt]=sumv[lc[rt]]+sumv[rc[rt]];
}
ll query(int ql,int qr,int rt,int l,int r){
if(!rt){
return 0;
}
if(ql<=l && r<=qr){
return sumv[rt];
}
pushdown(rt,r-l+1);
int m=(l+r>>1);
ll res=0;
if(ql<=m){
res+=query(ql,qr,lc[rt],l,m);
}
if(m<qr){
res+=query(ql,qr,rc[rt],m+1,r);
}
return res;
}
int n,m;
int main(){
int op,x,y;
ll z;
// freopen("luogu3372.in","r",stdin);
scanf("%d%d",&n,&m);
buildtree(root,1,n);
for(int i=1;i<=m;++i){
scanf("%d%d%d",&op,&x,&y);
if(op==1){
scanf("%lld",&z);
update(x,y,z,root,1,n);
}
else{
printf("%lld\n",query(x,y,root,1,n));
}
}
return 0;
}