带lazy标记的线段树

线段树的lazy操作

以POJ 2777 Count Color为例。

线段树，是一个满的二叉树，每次每一个子节点都是父节点的一半。所以二叉树的每个节点都维护了一个区间。可是实现快速的查询。
对于更新来讲的话，如果每次都更新到最下面的节点，会非常的耗时间。所以假如更新到某个节点的时候，而这个节点的左右段和要更新的最有端点一致的话，就可以仅更新该节点，并在他的子节点上面（两个）加上一个lazy-tag，不再往子节点更新值。如果以后更新到加lazy-tag标记的结点时，则需要把这个标记的值更新下去，并且在他的子节点跟新lazy-tag标记，并取消这个节点的lazy-tag。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define inf 0x3f3f3f
#define MAXN 100100

struct tree
{
    int l;
    int r;
    int colr;
    bool lazy;//lazy是lazy-tag
};
tree t[MAXN*4];
int L,T,O;
int cc;
int x,y,c;
void Swap()
{
    int temp=x;
    x=y;
    y=temp;
}
void Build(int l,int r,int index)
{
    t[index].l=l;
    t[index].r=r;
    t[index].colr=1;
    t[index].lazy=0;//lazy=0，说明当前结点没有lazy标记。
    if(l==r)
        return;
    int mid=(l+r)>>1;
    Build(l,mid,index<<1);
    Build(mid+1,r,index<<1|1);
}
void inse(int l,int r,int index,int cl)
{
    if(t[index].l==l && t[index].r==r)
    {
        t[index].colr=(1<<(cl-1));
        t[index].lazy=1;//更新到相应节点的时候，加上lazy-tag
        return;
    }
    if(t[index].lazy) //如果当前的节点有lazy标记，则
    {
        t[index].lazy=0;//1，需要取消lazy标记，
        t[index<<1].lazy=1;//2，往子节点传递lazy标记
        t[index<<1|1].lazy=1;
        t[index<<1].colr=t[index].colr;//3，并传递值
        t[index<<1|1].colr=t[index].colr;
    }
    int mid=(t[index].l+t[index].r)>>1;
    if(r<=mid)
        inse(l,r,index<<1,cl);
    else if(l>mid)
        inse(l,r,index<<1|1,cl);
    else
    {
        inse(l,mid,index<<1,cl);
        inse(mid+1,r,index<<1|1,cl);
    }
    t[index].colr=t[index<<1].colr | t[index<<1|1].colr;//往上更新值。
}
void quer(int l,int r,int index)
{
	//如果遇见带lazy标记的节点，只需要返回当前的节点的值就行了，
    if(t[index].lazy || (t[index].l==l && t[index].r==r) )
    {
        cc|=t[index].colr;
        return;
    }
    int mid=(t[index].l+t[index].r)>>1;
    if(r<=mid)
        quer(l,r,index<<1);
    else if(l>mid)
        quer(l,r,index<<1|1);
    else
    {
        quer(l,mid,index<<1);
        quer(mid+1,r,index<<1|1);
    }
}
int main()
{
    while(scanf("%d%d%d",&L,&T,&O)!=EOF)
    {
        char ss;
        Build(1,L,1);
        while(O--)
        {

            scanf(" %c",&ss);
            if(ss=='C')
            {
                scanf("%d%d%d",&x,&y,&c);
                if(x>y)
                    Swap();
                inse(x,y,1,c);
            }
            else
            {
                int ans=0;
                scanf("%d%d",&x,&y);
                if(x>y)
                    Swap();

                cc=0;
                quer(x,y,1);
                for(int i=0; i<T; i++)
                {
                    if(cc&(1<<i))
                        ans++;
                }
                printf("%d
",ans);
            }
        }
    }
    return 0;
}