线段树区间更新

淩亂°似流年 2022-08-03 16:38 245阅读 0赞

线段树成段更新延迟标记理解

区间更新是指每次更新的时候更新的是一个区间里面的所有值，例如将区间\[l,r\]内的所有点都加或者减去一个数，或者替换成一个数字等等.因为区间更新每次更新的不止一个叶子节点，而叶子节点的值的更新肯定会影响到他的一系列的节点，所以假如每次都按照单点更新的思路将每一个叶子节点以及他的父节点都更新的话，那么工作量太大了并且时间肯定不会是log(n)会超时的。例如线段树总区间为\[1,10\]，也就是这个树：

![Center][]

现在我们要更新\[4,8\]内的叶子节点的值，那么总共要更新的节点就会非常多。为了解决这个可能会超时的做法，引入了线段树中的延迟标记，这也是线段树的精华部分。延迟标记：每个节点除了常规的lft，rht，value外在增加一个标记，这个标记用于记录这个节点是否进行了某种修改(这种修改操作会影响其子节点)，对于任意区间的修改，我们先按照区间查询的方式将其划分成线段树中的节点，然后修改这些节点的信息，并给这些节点标记上代表这种修改操作的标记。在修改和查询的时候，如果我们到了一个节点p，并且决定考虑其子节点，那么我们就要看节点p是否被标记，如果有，就要按照标记修改其子节点的信息，并且给子节点都标上相同的标记，同时消掉节点p的标记。这样一来成段更新的时候每次只需要更新有用的部分就可以了。

举例说明：当我们要将区间\[1,3\]的叶子节点的value增加2的时候，我们利用和区间查询一样的办法找到了区间\[1,3\]，这时候我们把区间\[1.3\]的value值加上区间长度len*\*2，然后把他的延迟标记记为2，这时候这一次的区间更新就完成了，不需要更新\[1,3\]的子节点。当我们然后继续要将区间\[3,5\]内的叶子节点value增加2，这时候查询到\[1,3\]的时候我们发现要用到他的字区间\[3,3\]并且\[1,3\]已经被标记了，这时候我们就要把\[1,3\]的标记向子节点传递，分别将他的字节点区间\[1,2\]的标记都记为2然后区间的value值加上区间长度len\**2（父区间的标记值）,然后将区间\[1,3\]的标记清0，然后将区间\[4,5\]按上面的方法更新一下就可以了。当区间更新的区间长度为1的时候就是单点更新，单点更新只是区间更新的特例。

\-hdu 1698 Just a Hook（成段更新）

\-题意：有t组测试数据，n为钩子长度（1<=n<=100000）,m为操作的次数。初始时，每个钩子的价值为1，操作由三个数字组成x,y,z表示把区间\[x,y\]的钩子变成的价值变成z（1代表铜，2银，3金）,最后求钩子的总长度。

思路：线段树的成段更新问题，重点是使用了延迟标记type，即每次成段更新的时候，类似与询问query函数，只更新到包含该区间的最大区间就可以了。

上面有详细讲解。也可以看代码注释。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <queue>
    #include <stack>
    using namespace std;
    
    int n,m;
    const int maxn = 100005;
    
    struct node
    {
        int lft,rht;
        int value,type;
        //flag为延迟标记符
        void fun(int temp)
        {
            type=temp;
            value=(rht-lft+1)*type;//直接将alue的值更改
            //有时候是需要累加的，或者累减的
        }
    }tree[maxn<<2];
    
    void rest(int ind)
    {
        //延迟操作
        if(tree[ind].type)
        {
            tree[ind*2].fun(tree[ind].type);
            //将节点ind的延迟标记type以及value传向儿子节点
            tree[ind*2+1].fun(tree[ind].type);
            tree[ind].type=0;//将该节点的延迟标记清0
        }
    }
    
    void build(int lft,int rht,int ind)
    {
        tree[ind].lft=lft;
        tree[ind].rht=rht;
        tree[ind].value=rht-lft+1;//初始叶子节点的值都为1
        tree[ind].type=0; //初始延迟标记，tree[ind].type=1也可以
        if(lft!=rht)
        {
            int mid = (tree[ind].lft+tree[ind].rht)/2;
            build(lft,mid,ind*2);
            build(mid+1,rht,ind*2+1);
        }
    }
    
    void updata(int st,int en,int ind,int type)
    {
        //参数多了一个，既是要操作的数字也起到延迟标记的作用
        int lft=tree[ind].lft;
        int rht=tree[ind].rht;
        if(st<=lft&&rht<=en)tree[ind].fun(type);
        //赋值type的同时更新alue的值
        else
        {
            rest(ind);
            //判断节点ind是否有延迟标记,有的话向下操作
            int mid = (tree[ind].lft+tree[ind].rht)/2;
            if(st<=mid)updata(st,en,ind*2,type);
            if(en>mid)updata(st,en,ind*2+1,type);
            tree[ind].value=tree[ind*2].value+tree[ind*2+1].value;
        }
    }
    
    int main()
    {
        int t,count=1;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&m);
            build(1,n,1);
            //cout<<tree[1].value<<endl;
            int a,b,c;
            while(m--)
            {
                scanf("%d%d%d",&a,&b,&c);
                updata(a,b,1,c);
                //cout<<tree[1].value<<endl;
            }
            printf("Case %d: The total value of the hook is %d.\n",count++,tree[1].value);
            //tree[1].value是区间内所有值的和
        }
        return 0;
    }

\-POJ 3468 A Simple Problem with Integers（成段更新）

题意：题目给你n个数,m个操作，接下来一行给你这n个数，接下的几行给出m个操作，Q a b 表示查询区间\[a,b\]里的数和和。U a b c 表示把区间\[a,b\]里的数都加上c。

同样使用延迟标记add。当add不等于0的时候，表示它以下所有区间都需要更新。因为我们没有去改变原始查询区间的区间端点，所以当找到一个区间小于等于查询区间的时候，标记它的延迟标记，返回。注意，因为有可能多次对同一个区间更新值，如果我们直接把标记add=增加值，就不能反应这种情况，所以是add+=增加值，还有，延迟标记也会超int。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    #define LL(x) (x<<1)
    #define RR(x) (x<<1|1)
    #define MID(a,b) (a+((b-a)>>1))
    const int N=100005;
    typedef long long LL;
    
    struct node
    {
    	int lft,rht;
    	LL sum,add;
    	int mid(){return MID(lft,rht);}
    	void fun(LL tmp)
    	{
    		add+=tmp;
    		sum+=(rht-lft+1)*tmp;
    	}
    };
    
    int y[N];
    
    struct Segtree
    {
    	node tree[N*4];
    	void relax(int ind)
    	{
    		if(tree[ind].add)
    		{
    			tree[LL(ind)].fun(tree[ind].add);
    			tree[RR(ind)].fun(tree[ind].add);
    			tree[ind].add=0;
    		}
    	}
    	void build(int lft,int rht,int ind)
    	{
    		tree[ind].lft=lft;	tree[ind].rht=rht;
    		tree[ind].sum=0;	tree[ind].add=0;
    		if(lft==rht) tree[ind].sum=y[lft];
    		else
    		{
    			int mid=tree[ind].mid();
    			build(lft,mid,LL(ind));
    			build(mid+1,rht,RR(ind));
    			tree[ind].sum=tree[LL(ind)].sum+tree[RR(ind)].sum;
    		}
    	}
    	void updata(int st,int ed,int ind,int add)
    	{
    		int lft=tree[ind].lft,rht=tree[ind].rht;
    		if(st<=lft&&rht<=ed) tree[ind].fun(add);
    		else
    		{
    			relax(ind);
    			int mid=tree[ind].mid();
    			if(st<=mid) updata(st,ed,LL(ind),add);
    			if(ed> mid) updata(st,ed,RR(ind),add);
    			tree[ind].sum=tree[LL(ind)].sum+tree[RR(ind)].sum;
    		}
    	}
    	LL query(int st,int ed,int ind)
    	{
    		int lft=tree[ind].lft,rht=tree[ind].rht;
    		if(st<=lft&&rht<=ed) return tree[ind].sum;
    		else
    		{
    			relax(ind);
    			int mid=tree[ind].mid();
    			LL sum1=0,sum2=0;
    			if(st<=mid) sum1=query(st,ed,LL(ind));
    			if(ed> mid) sum2=query(st,ed,RR(ind));
    			return sum1+sum2;
    		}
    	}
    }seg;
    int main()
    {
    	int n,m;
    	while(scanf("%d%d",&n,&m)!=EOF)
    	{
    		char str[5];
    		int a,b,c;
    
    		for(int i=1;i<=n;i++) scanf("%d",&y[i]);
    		seg.build(1,n,1);
    		while(m--)
    		{
    			scanf("%s",str);
    			if(str[0]=='Q')
    			{
    				scanf("%d%d",&a,&b);
    				printf("%lld\n",seg.query(a,b,1));
    			}
    			else
    			{
    				scanf("%d%d%d",&a,&b,&c);
    				seg.updata(a,b,1,c);
    			}
    		}
    	}
    	return 0;
    }

/*
    题意：对于长度为250000的区间，给了你四种操作：
    操作A，从st到ed这段区间内的数，分别加上1,2,...,st-ed+1。
    操作B，从st到ed这段区间内的数，分别加上，st-ed+1,st-ed,...,1。
    操作C，将st到ed这段区间内的数赋值成x。
    操作S，查询st到ed的这段区间内的数的总和。
    */
    
    /*
    对于有多种操作的区间更新线段树，首先是每种操作都要有自己的
    延迟标记符，其次是要弄清楚不同操作之间的顺序性以及联系等。
    比喻说这道题目，操作AB都是加一个等差数列可以看作是一个操作，
    操作C是将区间的值改为另一个数字，这两个操作同时要有延迟标记符。
    但是我们会注意到，当两个操作同时进行时，也就是一个区间这两种
    标记都有的时候，我们怎么向子区间传递呢。应该先传递操作C然后在
    传递操作AB。为什么呢，因为假如后传递C的话那他就会将AB的延迟
    标记符抹掉。或者我们考虑怎么样一个区间才可能同时出现两种标记符呢。
    肯定是先进行了C操作然后在进行AB操作的，因为C操作会将AB操作覆盖。
    */
    
    /*
    具体到这道题目，我们发现操作C比较简单常见，在这里就不多叙述。
    我们下面重点看看操作AB，AB操作都是等差数列，所以可以一起进行。
    对于操作AB，我们需要用到三个延迟标记符。
    在线段树的结点中记录了左端点要加的值add1，
    右端点要加的值add2，同时记录了这段区间内的公差step。
    容易得到，等差数列相加还是等差数列，所以可以对一个区间进行多次的AB操作。
    
    易错点：向子区间传递延时标记的时候，即add1和add2的时候，要分解成两个区间，
    设为(add1,mid1)，(mid2,add2)，通过(add1+add2)/2直接得到mid1，
    然后mid2再根据是递增或是递减相应的加一减一，这里的mid是错误的。
    实际上这里应该只有一个mid，(add1+add2+step)/2，
    这也是为什么在线段树的结点里添加公差step的原因。
    
    */
    
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    const int N=250005;
    typedef long long LL;
    
    struct node
    {
        bool flag;  //操作C的延时标记
    	int left,right;
    	LL add1,add2,step;  //操作A和B的标记，不好理解
    	 //代表的含义分别是左右端点和公差
        LL sum,valu;
        LL mid(){return left+(right-left)/2;}
        LL len(){return right-left+1;}
        void changeAB(LL a,LL b,LL k)
        {
            add1+=a;    add2+=b;    step+=k;
            sum+=(a+b)*len()/2;  //等差数列和
        }
        void changeC(LL a)
        {
            flag=1;     valu=a;
            add1=0;     add2=0;     step=0;
            sum=valu*len();
        }
    };
    
    struct Segtree
    {
    	node tree[N*4];
    	void down(int ind)
    	{
    		if(tree[ind].flag)
    		{
            //两种标记都有的时候，先进行C操作的传递过程
            //原因是假如先进行AB操作的话，那么c操作会将所有
            //数字强制转换为value，那么AB操作被覆盖了
    			tree[ind*2].changeC(tree[ind].valu);
    			tree[ind*2+1].changeC(tree[ind].valu);
    			tree[ind].flag=0;
    		}
    		if(tree[ind].add1||tree[ind].add2||tree[ind].step)
    		{
    		    //只要有一个不是0就说明了有AB操作的延时标记
    		    LL add1=tree[ind].add1,add2=tree[ind].add2;
    		    LL k=tree[ind].step;
    		    LL mid=add1+k*(tree[ind*2].len()-1);
    
    			tree[ind*2].changeAB(add1,mid,k);
    			tree[ind*2+1].changeAB(mid+k,add2,k);
    			tree[ind].add1=0;	tree[ind].add2=0;
    			tree[ind].step=0;
    		}
    	}
    	void build(LL left,LL right,LL ind)
    	{
    		tree[ind].left=left;	tree[ind].right=right;
    		tree[ind].add1=0;		tree[ind].add2=0;
    		tree[ind].sum=0;		tree[ind].valu=0;
    		tree[ind].step=0;
    		if(left!=right)
    		{
    			LL mid=tree[ind].mid();
    			build(left,mid,ind*2);
    			build(mid+1,right,ind*2+1);
    		}
    	}
    	void updataAB(LL be,LL end,LL ind,LL step)
    	{
    		LL left=tree[ind].left,right=tree[ind].right;
    		if(be<=left&&right<=end)
    		{
    		    LL st,ed;
    		    if(step>=0) {st=left-be+1;ed=right-be+1;}
    		    else {st=end-left+1;ed=end-right+1;}
    		    //子区间也是只记录端点的值
    		    tree[ind].changeAB(st,ed,step);
    		}
    		else
    		{
    			down(ind);
    			LL mid=tree[ind].mid();
    			if(be<=mid) updataAB(be,end,ind*2,step);
    			if(end>mid) updataAB(be,end,ind*2+1,step);
    			tree[ind].sum=tree[ind*2].sum+tree[ind*2+1].sum;
    		}
    	}
    	void updataC(LL be,LL end,LL ind,LL valu)
    	{
    		LL left=tree[ind].left,right=tree[ind].right;
    		if(be<=left&&right<=end) tree[ind].changeC(valu);
    		else
    		{
    			down(ind);
    			LL mid=tree[ind].mid();
    			if(be<=mid) updataC(be,end,ind*2,valu);
    			if(end>mid) updataC(be,end,ind*2+1,valu);
    			tree[ind].sum=tree[ind*2].sum+tree[ind*2+1].sum;
    		}
    	}
    	LL query(LL be,LL end,LL ind)
    	{
    		LL left=tree[ind].left,right=tree[ind].right;
    		if(be<=left&&right<=end) return tree[ind].sum;
    		else
    		{
    			down(ind);
    			LL mid=tree[ind].mid();
    			LL sum1=0,sum2=0;
    			if(be<=mid) sum1=query(be,end,ind*2);
    			if(end>mid) sum2=query(be,end,ind*2+1);
    			return sum1+sum2;
    		}
    	}
    }seg;
    
    int main()
    {
    
        int n;
        while(scanf("%d",&n)!=EOF)
        {
    		seg.build(1,N-5,1); //建立一棵树
    		for(int i=0;i<n;i++)
    		{
    			char str[10];
    			LL a,b,c;
    			scanf("%s",str);
    			if(str[0]=='A')
    			{
    				scanf("%lld%lld",&a,&b);
    				seg.updataAB(a,b,1,1);
    			}
    			else if(str[0]=='B')
    			{
    				scanf("%lld%lld",&a,&b);
    				seg.updataAB(a,b,1,-1);
    			}
    			else if(str[0]=='C')
    			{
    				scanf("%lld%lld%lld",&a,&b,&c);
    				seg.updataC(a,b,1,c);
    			}
    			else
    			{
    				scanf("%lld%lld",&a,&b);
    				printf("%lld\n",seg.query(a,b,1));
    			}
    		}
    	}
    	return 0;
    }

[Center]: /images/20220731/b1f76c0a30fe4cc383480fe69ef5370c.png