检查了好久都没发现错误。。。
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=4e5+5;
int tag[N],d[N],res,sz,numl,numr,k;//d为区间和
void _add(int x)
{
tag[x]+=k;
d[x]+=(k<<sz);
return;
}
void update(int x)
{
d[x]=d[x<<1]+d[1<<1|1]+(tag[x]<<sz);
return;
}
void adds(int l,int r)
{
l+=res,r+=res;
sz=0;
_add(l);
if(l!=r)
{
_add(r);
while((l^1)!=r)
{
if(!(l&1)) _add(l^1);
if(r&1) _add(r^1);
++sz;
l>>=1;
update(l);
r>>=1;
update(r);
}
}
while(l>>=1)
{
++sz;
update(l);
}
return;
}
int getsum(int l,int r)
{
l+=res,r+=res;
int k=d[l];
numl=sz=1;
if(l!=r)
{
k+=d[r];
numr=1;
while((l^1)!=r)
{
if(!(l&1)) {
k+=d[l^1];
numl+=sz;
}
if(r&1){
k+=d[r^1];
numr+=sz;
}
sz<<=1;
l>>=1;
r>>=1;
k+=tag[l]*numl+tag[r]*numr;
}
numl+=numr;
}
while(l>>=1) k+=tag[l]*numl;
return k;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin>>n>>m;
for(res=1;res<n;res<<=1);
res-=1;
for(int i=1;i<=n;++i) cin>>d[i+res];
for(int i=(n+res)>>1;i;--i) d[i]=d[i<<1]+d[i<<1|1];
while(m--)
{
int opt,l,r;
cin>>opt>>l>>r;
if(opt==1)
{
cin>>k;
adds(l,r);
}
else cout<<getsum(l,r)<<'\n';
}
return 0;
}