线段树入门：查询与更新操作

查询操作查询操作是线段树的核心操作之一。给定一个查询区间从根节点开始向下遍历线段树。如果当前节点表示的区间与查询区间完全重叠则返回当前节点存储的信息。如果当前节点表示的区间与查询区间没有重叠则返回一个特殊值表示没有找到符合条件的元素。如果当前节点表示的区间与查询区间部分重叠则判断是在左子树中查询还是在右子树中查询并继续向下遍历左/右子树。区间查询的代码实现如下int query(int x,int l,int r){ if(t[x].llt[x].rr){ //当前区间被查询区间完全覆盖直接返回 return t[x].val; } 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; }更新操作更新操作用于修改线段树中某个元素的值。从根节点开始向下遍历线段树找到需要修改的叶节点然后更新该节点存储的元素值同时需要更新所有祖先节点的信息。算法步骤如下。1若是叶子节点满足 且 则修改该节点的最值为 。2若是非叶子节点则判断是在左子树中更新还是在右子树中更新。3返回更新节点的值。单点更新操作代码实现如下void update(int x,int i,int v){ //将a[i]更新为v if(t[x].lt[x].rt[x].li){ t[x].valv; return; } int mid(t[x].lt[x].r)1; if(imid) update(x*2,i,v); else update(x*21,i,v); t[x].valmin(t[x*2].val,t[x*21].val); }