线段树及其懒标记

懒标记基本原则
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;
}

上一篇:Photoshop 一朵漂亮的喇叭花


下一篇:vSLAM学习笔记——四元数到其他旋转表示的转换