本文共 2178 字，大约阅读时间需要 7 分钟。

懒惰标记实际上就是让子节点暂时处于不更新状态，用到的时候再更新，如本题中的visit[]就是懒惰标记，例如总长度是1-10，我们现在要想更新1-6，（将1-6的值都加3）那么update()会先找1-10，发现不合适，再找他的左右孩子，发现1<5，说明1-6的区间在1-10的左孩子中，同时6>5，1-6也在1-10的右孩子中，这样依次去找1-6在的区间。但是找到1-5的时候，我们发现整个1-5都在1-6中间，也就是说这一段都要更新，那么我们将1-5的sum值更新了，同时用visit[rt]+=3记录下来1-5中的数字现在每个都 要加的数字，但是1-5下边还有1-3,4-5,3-3,4-4,5-5，这些我们就可以不用更新，因为这些我们暂时还用不到，假如现在又要将1-5区间的值都加5，那么visit[rt]+=5,此时就是8了，但是还是不用更新他的子节点，假如我们现在要用到1-3区间了，我们就可以一次性给1-3区间加上8，而不用先加3，再加5，这样懒惰标记就使得每次的递归都少了好多，

可以参考

线段树成段更新的代码poj 3468

#include
   
    #include
    
     #include
     
      using namespace std;#define N 100005#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define ll long longll sum[N*4];int visit[N*4];void pushUp(int rt){    sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void build(int l,int r,int rt){    visit[rt]=0;    if(l==r)    {        scanf("%lld",&sum[rt]);        return ;    }    int m=(l+r)>>1;    build(lson);    build(rson);    pushUp(rt);}void pushDown(int rt,int d){    if(visit[rt]!=0)    {    //注意将懒惰标记的值传给子孩子       visit[rt<<1]+=visit[rt];       visit[rt<<1|1]+=visit[rt];        sum[rt<<1|1]+=(ll)(d>>1)*visit[rt];//注意后边乘可能超整形，强制类型转换（ll），即AC        sum[rt<<1]+=(ll)(d-(d>>1))*visit[rt];        visit[rt]=0;    }}void update(int L,int R,int c,int l,int r,int rt){    if(L<=l && R>=r)    {        visit[rt]+=c;        sum[rt]+=(r-l+1)*c;        return ;    }    pushDown(rt,r-l+1);    int m=(l+r)>>1;    if(L<=m)        update(L,R,c,lson);    if(R>m)        update(L,R,c,rson);    pushUp(rt);}ll query(int L,int R,int l,int r,int rt){    if(L<=l && R>=r)    {        return sum[rt];    }    //这时候就用到子区间了，更新    pushDown(rt,r-l+1);    int m=(l+r)>>1;    ll ret=0;    if(L<=m)        ret+=query(L,R,lson);    if(R>m)        ret+=query(L,R,rson);    return ret;}int main(){    int n,q,a,b,c;    char s[3];    scanf("%d%d",&n,&q);    build(1,n,1);    while(q--)    {        scanf("%s",s);        if(s[0]=='C')        {            scanf("%d%d%d",&a,&b,&c);            update(a,b,c,1,n,1);        }        else if(s[0]=='Q')        {            scanf("%d%d",&a,&b);            printf("%lld\n",query(a,b,1,n,1));        }    }    return 0;}/*10 1001 2 3 4 5 6 7 8 9 10C 1 6 3Q 1 1Q 1 2Q 4 4Q 1 10Q 1 5C 3 6 3Q 1 5*/
     
    
   

转载地址：http://bwcdi.baihongyu.com/