线段树 Part_区间修改

引言

由上述区间查询可知，对于一个并没有与树中某一节点完全重合的区间我们可以用多个被该区间完全包含且互不重叠的节点表示，如下图：

修改的基本原理

对于某个需要修改的期间，由上，同理，我们可以将该区间拆为类似的节点，然后对每个节点依次修改，再依次向上完成更新，但是我们可以发现虽然我们找到了修改的办法，但是仍旧需要修改很多点，如下图：

这可一点都不友好，复杂度直逼O(2n) ,则我们并不能每一次都修改完所有的点，毕竟后面也不一定用，所以我们每次只更新最最少的点，剩下的要用时再更新，那么如何标记那些还没有更新的点呢？

Lazy标记

根据上述，我们可以发现若要更新某一区间，满足引言中的条件的节点的子节点一定更新，那么我们可以每次只更新到满足条件的节点就可以停止更新，并打上标记表示该节点的子节点尚未更新，如下图：

这样我们就可以节省修改所有标为绿色的节点的时间

定义

对于Lazy_tag[i]，其表示以 i 为根节点，它的所有子节点中 每一个值 尚未更新 的值

下移

当我们需要所以该节点的子节点时我们需要将 Lazy 标记 下移，即将该标记传给与其直接相连的子节点，并更新该子节点。

注意事项

由上述，由于标蓝色的已经修改过了，所以在下移 Lazy 标记时，不必再更新父亲节点

代码实现

CPP

void maketag(int u,int len,long long k){
	w[u]+=k*len;
	tag[u]+=k;
	return;
}

CPP

void low(int u,int l,int r){
	int m=(l+r)/2;
	maketag(u*2,m-l+1,tag[u]);
	maketag(u*2+1,r-m,tag[u]);
	tag[u]=0;
	return ;
}

CPP

void update(int u,int l,int r,int L,int R,long long k){
	if(check_y(l,L,r,R))
		maketag(u,r-l+1,k);
	else if(!check_n(l,L,r,R)){
		low(u,l,r);
		int m=(r+l)/2;
		update(u*2,l,m,L,R,k);
		update(u*2+1,m+1,r,L,R,k);
		plus_(u);
	}else return ;
}

线段树 Part_区间修改

文章操作

引言

修改的基本原理

Lazy标记

定义

下移

注意事项

代码实现

相关推荐

评论

线段树 Part_区间修改