这篇lazy讲的很棒：

https://www.douban.com/note/273509745/

if(tree[rt].l == l && r == tree[rt].r)

这里就是用到Lazy思想的关键时刻 正如上面说提到的，这里首先更新该节点的sum[rt]值，

然后更新该节点具体每个数值应该加多少即add[rt]的值，

注意此时整个函数就运行完了，直接return，而不是还继续向子节点继续更新，

这里就是Lazy思想，暂时不更新子节点的值。

那么什么时候需要更新子节点的值呢？

答案是在某部分update操作的时候需要用到那部分没有更新的节点的值的时候，

这时就掉用PushDown()函数更新子节点的数值。

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+10;

struct asd{

    int left,right;

    int ad;

    int w;

};

asd q[N*4];

void build(int num,int L,int R)

{

    q[num].left=L;

    q[num].right=R;

    if(L==R)

    {

        q[num].w=q[num].ad=0;

        return;

    }

    build(2*num,L,(L+R)/2);

    build(2*num+1,(L+R)/2+1,R);

    q[num].w=q[num].ad=0;

}

int ss(int num)

{

    return q[num].right-q[num].left+1;

}

void Pushdown(int num)

{

    if(q[num].ad)

    {

        q[num*2].w+=q[num].ad*(ss(2*num));

        q[num*2+1].w+=q[num].ad*(ss(2*num+1));

        q[num*2].ad+=q[num].ad;

        q[num*2+1].ad+=q[num].ad;

        q[num].ad=0;

    }

}

void Pushup(int num)

{

    q[num].w=q[2*num].w+q[2*num+1].w;

}

void update(int num,int s,int t)

{

    if(s==q[num].left&&q[num].right==t)

    {

        q[num].w+=t-s+1;

        q[num].ad+=1;

        return;

    }

    if(q[num].left==q[num].right)

        return;

    Pushdown(num);

    int mid=(q[num].right+q[num].left)/2;

    if(mid>=t)

        update(2*num,s,t);

    else if(mid<s)

        update(2*num+1,s,t);

    else

    {

        update(2*num,s,mid);

        update(2*num+1,mid+1,t);

    }

    Pushup(num);

}

int query(int num,int s,int t)

{

    if(s==q[num].left&&q[num].right==t)

        return q[num].w;

    Pushdown(num);

    int ans=0;

    int mid=(q[num].right+q[num].left)/2;

    if(mid>=t)

        ans+=query(2*num,s,t);

    else if(mid<s)

        ans+=query(2*num+1,s,t);

    else

        ans+=query(2*num,s,mid)+query(2*num+1,mid+1,t);

    return ans;

}

int main()

{

    int n;

    while(~scanf("%d",&n)&&n)

    {

        int x,y;

        build(1,1,n);

        for(int i=1;i<=n;i++)

        {

            scanf("%d%d",&x,&y);

            update(1,x,y);

        }

        for(int i=1;i<=n;i++)

        {

            if(i>1) printf(" ");

            printf("%d",query(1,i,i));

        }

        puts("");

    }

    return 0;

}

/*

6

1 6

1 6

1 6

1 3

2 5

3 6

*/