线段树入门：区间更新

区间更新若对区间的每个点都进行更新则时间复杂度较高可以引入懒操作。对 区间进行更新例如将 区间的所有元素都更新为 步骤如下。1若当前节点的区间被查询区间 覆盖则仅对该节点进行更新并做懒标记表示该节点已被更新对该节点的子节点暂不更新。2判断是在左子树中查询还是在右子树中查询。在查询过程中若当前节点带有懒标记则将懒标记下传给子节点 将当前节点的懒标记清除将子节点更新并做懒标记继续查询。3在返回时更新最值。区间更新的代码实现如下void lazy(int x,int v){ t[x].valv; //更新最值 t[x].lazyv; //做懒标记 } void pushdown(int x){ if(t[x].lazy){ lazy(2*k,t[x].lazy); lazy(2*k1,t[x].lazy); t[x].lazy-1; } } void update(int x,int l,int r,int v){ //将[l,r]区间所有元素更新为v if(t[x].llt[x].rr){ //找到该区间 lazy(x,v); //更新并做懒标记 return; } if(t[x].lazy!-1) //懒标记下传 pushdown(x); int mid(t[x].lt[x].r)1; if(lmid) update(x*2,l,r,v); if(rmid) update(x*21,l,r,v); t[x].valmin(t[x*2].val,t[x*21].val); }例如当我们用 这一组数创建线段树之后对 区间更新为 如图所示另外带有懒标记的区间查询和普通的区间查询不同在查询过程中若遇到有节点带有懒标记则下传懒标记继续查询。代码实现如下int query(int x,int l,int r){ if(t[x].llt[x].rr){ //当前区间被查询区间完全覆盖直接返回 return t[x].val; } if(t[x].lazy!-1) pushdown(x); //下传懒标记 int mid(t[x].lt[x].r)1; int resinf; //设定一个非常大的值 if(lmid) //在左区间查询 resmin(res,query(x*2,l,r)); if(rmid) //在右区间查询 resmin(res,query(x*21,l,r)); return res; }