#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,a[N];
int add[N*4];//账本
long long sum[N*4];//a[k]的区间和
void build(int k,int l,int r)//建树
{
if(l==r)
{
sum[k]=a[l];
return;
}
int mid=(l+r)/2;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
sum[k]=sum[k*2]+sum[k*2+1];
}
void Add(int k,int l,int r,int v)//区间加值并更新
{
add[k]+=v;
sum[k]+=(long long)v*(r-l+1);
}
void pushdown(int k,int l,int r,int mid)//标记下放
{
if(add[k]==0)
return;
Add(k*2,l,mid,add[k]);
Add(k*2+1,mid+1,r,add[k]);
add[k]=0;
}
long long query(int k,int l,int r,int x,int y)//询问
{
if(l>=x && r<=y)
return sum[k];
int mid=(l+r)/2;
long long res=0;
pushdown(k,l,r,mid);
if(x<=mid)
res+=query(2*k,l,mid,x,y);
if(mid<y)
res+=query(2*k+1,mid+1,r,x,y);
return res;
}
void modify(int k,int l,int r,int x,int y,int v)//区间加v
{
if(l>=x && r<=y)
return Add(k,l,r,v);
int mid=(l+r)/2;
pushdown(k,l,r,mid);
if(x<=mid)
modify(2*k,l,mid,x,y,v);
if(mid<y)
modify(2*k+1,mid+1,r,x,y,v);
sum[k]=sum[2*k]+sum[2*k+1];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",a+i);
build(1,1,n);
while(m--)
{
int A,B,C,OP;
scanf("%d",&OP);
if(OP==1)
{
scanf("%d%d%d",&A,&B,&C);
modify(1,1,n,A,B,C);
}
if(OP==2)
{
scanf("%d%d",&A,&B);
printf("%lld\n",query(1,1,n,A,B));
}
}
return 0;
}
标签:洛谷,int,sum,mid,long,add,Add,P3372,模板 From: https://www.cnblogs.com/zhouzhihao/p/16708798.html