线段树入门：区间更新

区间更新

若对区间的每个点都进行更新，则时间复杂度较高，可以引入懒操作。

对 区间进行更新，例如将 区间的所有元素都更新为 ，步骤如下。

（1）若当前节点的区间被查询区间 覆盖，则仅对该节点进行更新并做懒标记，表示该节点已被更新，对该节点的子节点暂不更新。

（2）判断是在左子树中查询还是在右子树中查询。在查询过程中，若当前节点带有懒标记，则将懒标记下传给子节点 （将当前节点的懒标记清除，将子节点更新并做懒标记），继续查询。

（3）在返回时更新最值。

区间更新的代码实现如下：

void lazy(int x,int v){ t[x].val=v; //更新最值 t[x].lazy=v; //做懒标记 } void pushdown(int x){ if(t[x].lazy){ lazy(2*k,t[x].lazy); lazy(2*k+1,t[x].lazy); t[x].lazy=-1; } } void update(int x,int l,int r,int v){ //将[l,r]区间所有元素更新为v if(t[x].l>=l&&t[x].r<=r){ //找到该区间 lazy(x,v); //更新并做懒标记 return; } if(t[x].lazy!=-1) //懒标记下传 pushdown(x); int mid=(t[x].l+t[x].r)>>1; if(l<=mid) update(x*2,l,r,v); if(r>mid) update(x*2+1,l,r,v); t[x].val=min(t[x*2].val,t[x*2+1].val); }

例如当我们用 这一组数创建线段树之后，对 区间更新为 ，如图所示：

另外，带有懒标记的区间查询和普通的区间查询不同，在查询过程中若遇到有节点带有懒标记，则下传懒标记，继续查询。

代码实现如下：

int query(int x,int l,int r){ if(t[x].l>=l&&t[x].r<=r){ //当前区间被查询区间完全覆盖，直接返回 return t[x].val; } if(t[x].lazy!=-1) pushdown(x); //下传懒标记 int mid=(t[x].l+t[x].r)>>1; int res=inf; //设定一个非常大的值 if(l<=mid) //在左区间查询 res=min(res,query(x*2,l,r)); if(r>mid) //在右区间查询 res=min(res,query(x*2+1,l,r)); return res; }