- #include
- #include
- #include
- using namespace std;
- #define maxn 1000001
- #define ll long long
- ll a[maxn],f[maxn<<2],tag[maxn<<2];
- ll n,m,k,c,x,y;
- void push_up(ll x){
- f[x]=f[x<<1]+f[x<<1|1];
- }
- void push_down(ll p,ll l,ll r){
- ll mid=(l+r)>>1,ls=p<<1,rs=p<<1|1,k=tag[p];
- tag[p]=0;tag[ls]+=k;tag[rs]+=k;
- f[ls]+=(mid-l+1)*k;f[rs]+=(r-mid)*k;
- }
- void build(ll p,ll l,ll r){
- if(l==r){
- f[p]=a[l];return;
- }
- ll mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);
- push_up(p);
- }
- void update(ll l,ll r,ll nl,ll nr,ll p,ll k){
- if(l>=nl&&r<=nr){
- f[p]+=(r-l+1)*k;tag[p]+=k;return;
- }
- push_down(p,l,r);
- ll mid=(l+r)>>1;
- if(mid>=nl) update(l,mid,nl,nr,p<<1,k);
- if(mid<nr) update(mid+1,r,nl,nr,p<<1|1,k);
- push_up(p);
- }
- ll query(ll l,ll r,ll ql,ll qr,ll p){
- if(l>=ql&&r<=qr) return f[p];
- push_down(p,l,r);
- ll ans=0,mid=(l+r)>>1;
- if(mid>=ql) ans+=query(l,mid,ql,qr,p<<1);
- if(mid<qr) ans+=query(mid+1,r,ql,qr,p<<1|1);
- return ans;
- }
- int main(){
- scanf("%lld%lld",&n,&m);
- for(int i=1;i<=n;i++) scanf("%lld",a+i);
- build(1,1,n);
- for(int i=1;i<=m;i++){
- scanf("%lld",&c);
- if(c==1){
- scanf("%lld%lld%lld",&x,&y,&k);update(1,n,x,y,1,k);
- }
- else{
- scanf("%lld%lld",&x,&y);printf("%lld\n",query(1,n,x,y,1));
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3010818.html