在工作中我们经常需要对一些区间进行查询、更新或计算。例如我们可能需要找到一个数组中某个区间的最大值、最小值或求和。这些问题看似简单但在面对大规模数据或频繁的操作时传统的解决方法可能变得低效或不可行。线段树就可以很好地解决此类问题。今天我们就来聊聊线段树。线段树是什么一般来说线段树是一种二叉树每个节点表示一个区间。根节点表示整个查询区间而每个叶节点表示一个单独的元素。对于每个非叶节点它的左子节点表示左半部分的区间右子节点表示右半部分的区间。通过这种方式线段树将一个大区间划分成多个小区间从而可以高效地进行查询。我们可以在 C 程序中这样来定义线段树struct sgntree{ int l; //左区间位置 int r; //右区间位置 int val; //该区间内的最值 int lazy; //该区间的懒标记 }t[N];建立线段树在不同的场景下建立线段树的方法略有些差异。下列是建立线段树来求解区间查询最小值以及单点更新问题。线段树的建立过程可以通过递归算法实现。1若是叶子节点 则该节点的值就是对应位置的元素值2若是非叶子节点则递归创建左子树和右子树该节点的值就是左右子树的值的最小值。void build(int x,int l,int r){ t[x].ll; t[x].rr; if(lr){ //叶子结点 t[x].vala[l]; return; } int mid(lr)1; build(x*2,l,mid); build(x*21,mid1,r); t[x].valmin(t[x*2].val,t[x*21].val); }
