懒标记基本原则:
1、如果当前区间被完全覆盖在目标区间里,讲这个区间的sum+k*(tree[i].r-tree[i].l+1)
2、如果没有完全覆盖,则先下传懒标记
3、如果这个区间的左儿子和目标区间有交集,那么搜索左儿子
4、如果这个区间的右儿子和目标区间有交集,那么搜索右儿子
代码示例:
//洛谷P3372
#include<iostream>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,m;
ll a[N];
struct Tree{
ll l,r;
ll sum; //维护值为区间和
ll lz;
}tr[N*4];
void pushup(int p){
tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
}
void pushdown(int p){
//消除懒标记
if(tr[p].lz){
tr[p<<1].lz+=tr[p].lz;
tr[p<<1|1].lz+=tr[p].lz;
tr[p<<1].sum+=(tr[p<<1].r-tr[p<<1].l+1)*tr[p].lz;
tr[p<<1|1].sum+=(tr[p<<1|1].r-tr[p<<1|1].l+1)*tr[p].lz;
tr[p].lz=0;
}
}
void build(int p,ll l,ll r){
//建树
tr[p]={l,r,0,0};
if(l==r){
tr[p]={l,r,a[r],0};
return ;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void modify(int p,ll l,ll r,ll v){
//使区间l到r之间每个元素都加上v
if(tr[p].l>=l&&tr[p].r<=r){
tr[p].sum+=(tr[p].r-tr[p].l+1)*v;
tr[p].lz+=v;//懒标记
return ;
}
pushdown(p);//pushdown更新修改后区间的值
ll mid=tr[p].l+tr[p].r>>1;
if(l<=mid) modify(p<<1,l,r,v);
if(r>mid) modify(p<<1|1,l,r,v);
pushup(p);
}
ll query(int p,ll l,ll r){
//查询区间l到r之间所有元素的和
if(tr[p].r<l||tr[p].l>r)
return 0;
if(tr[p].l>=l&&tr[p].r<=r)
return tr[p].sum;
pushdown(p);
ll res=0;
res+=query(p<<1,l,r);
res+=query(p<<1|1,l,r);
return res;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>a[i];
}
build(1,1,n);
while(m--){
int opt,left,right,k;
cin>>opt;
if(opt==1){
cin>>left>>right>>k;
modify(1,left,right,k);
}
else{
cin>>left>>right;
cout<<query(1,left,right)<<endl;
}
}
return 0;
}