线段树002-区间修改

接下来讲解一下区间修改：

在线段树001-概述中讲了单点修改，现在又增加了一种操作将区间x~y的值修改为v;

比如在下面这个图中我要将1~5区间的值全都改为v;

正常人的思维是把1~5这个区间的修改看成对点1,2,3,4,5的单点修改；但这样的复杂度是nlog(n)是比较高的；

我们换一种想法，在修改区间的时候我们仍然像区间查询一样自上而下的寻找要修改的区间。那么我们最后

找到区间是1~3和4~5这两个区间。

我们把代表这两个区间的节点的值进行修改；这样一来我们就完成了区间修改；

但是这样就会出现新的问题，我只是修改了这两个节点的值，那么如果我要查找2~5区间的值的加和，按照区间查询的步骤

我最后查找的区间分别是2~2,3~3,4~5。可以发现只有4~5这个节点的值是正确的，2~2,3~3这两个节点的值在区间修改的时候

没有被修改。所以这样查询出来的值是错误的；

如何解决这个问题呢，我们发现区间修改所带来的问题指挥影响区间查询，所以我们可以修改一下区间查询的逻辑。

我们在修改区间的同时把这个区间打一下标记，说明这个区间的子区间是没有被修改的，在区间查询的时候，如果

当前区间被标记过，我们就修改这个区间的子区间，并把这个标记下移到这个区间的子区间。这样我们就解决了区间修改

的问题了；

代码如下：

#include<stdio.h>
#include<string.h>
#define mmset(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int INF = 1005;
int sum[INF << 2],mark[INF<<2];   //mark是用来标记的树 

void PushUp(int rt)  //向上更新 
{
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
	return ;
}

void PushDown(int l,int r,int rt)  //将标记向下推移并修改儿子的值 
{
	if(mark[rt] >= 0) 
	{
		mark[rt<<1] = mark[rt];
		mark[rt<<1|1] = mark[rt];
		mark[rt] = -1;
		int m = (r + l) / 2;
		sum[rt<<1] = (m - l + 1) * mark[rt<<1];
		sum[rt<<1|1] = (r - m) * mark[rt<<1|1];
	}
	return  ;
}

void update(int L,int R,int c,int l,int r,int rt)  //区间更新 
{
	if(L <= l && r <= R)
	{
		mark[rt] = c;
		sum[rt] = (r - l + 1) * c;
	}
	else
	{
		PushDown(l,r,rt);
		int m = (l + r) / 2;
		if(L <= m) 
		update(L,R,c,lson);
		if(R > m)
		update(L,R,c,rson);
		PushUp(rt);
	}
}
int query(int L,int R,int l,int r,int rt)  //区间查询 
{
	if(L <= l && R >= r)
	{
		return sum[rt];
	}
	else
	{
		PushDown(l,r,rt);  //在向下查询的时候先更新儿子的值并将标记向下推 
		int sumAdd = 0;
		int m = (l + r) / 2;
		if(L <= m)
		sumAdd += query(L,R,lson) ;
		if(R > m)
		sumAdd += query(L,R,rson);
		return sumAdd;
	}

} 

这里有道区间修改的题，感兴趣的可以做一下

线段树(区间修改+区间求和)