数据结构-线段树

# 数据结构-线段树 **参考资料** > 暂无 线段树是所有 RMQ 中最常用的数据结构。 功能：区间修改区间查询。不止最值、求和。只要可递推的值都可以构造线段树。 如果区间大小为 $n$，线段树有 $cnt$ 个节点，那么 $2n-1\le cnt<4n$。 **节点** 对于每个节点 $x$，和堆类似，父亲节点为 $x>>1$（即 $x/2$ 下取整的位运算方法，位运算方便而且快），左儿子为 $x<<1$（即 $2x$），右儿子为 $x<<1|1$（即 $2x+1$）。 同时每个节点对应一段区间，所以叫线段树。节点 $1$ 对应的区间为 $1\sim n$。设一个节点对应的区间为 $l\sim r$，那么它的左儿子对应的区间就是 $l\sim mid$，其中 $mid=(l+r)>>1$，右儿子区间为 $mid+1\sim r$。如果一个节点对应单点区间，就没有儿子。 同时每个节点对应一个值，即该区间的 RMQ 值。如果是求最值问题，就表示该区间最大值；如果是求和问题，就表示该区间的和。 **操作（单点修改区间查询）** 一个线段树是求和还是求最值或者求别的东西，取决于 $pushup(k)$ 函数，其中 $k$ 为节点编号，时间复杂度 $O(1)$。 ```cpp void pushup(int k){v[k]=max(v[k<<1],v[k<<1|1]);}//求最大值 ``` 根据原序列构造初始的线段树用 $build()$ 函数，单点节点上的值就为单点的值，递归从下到上构造，时间复杂度 $O(n\log n)$。 ```cpp void build(int k=1,int l=1,int r=n){//表示外部应用默认k=1,l=1,r=n if(l==r){v[k]=a[l];return;} //单点节点 build(k<<1,l,mid),build(k<<1|1,mid+1,r); //递归构造 pushup(k); //递推 } ``` 先讲单点修改（加上 $y$），只需与 $build()$ 函数类似的递归操作即可，如果到达单点节点，就修改，不走那些跟查询单点没关系的区间、别忘了修改完后也要递推，时间复杂度 $O(\log n)$。 ```cpp void fix(int x,int y,int k=1,int l=1,int r=n){ if(l==x&&r==x){v[k]+=y;return;} //单点修改 if(mid>=x) fix(x,y,k<<1,l,mid); //递归左儿子 else fix(x,y,k<<1|1,mid+1,r); //递归右儿子 pushup(k);//递推 } ``` 区间查询，如果单前节点在查询区间内，就返回值。否则，递归左儿子右儿子，递推得区间查询值。时间复杂度 $O(\log n)$，因为只会走相关的 $\log n$ 个节点。 ```cpp int fmax(int x,int y,int k=1,int l=1,int r=n){ if(x<=l&&r<=y) return v[k]; //在查找区间内，返回值 int res=0; if(mid>=x) res=max(res,fmax(x,y,k<<1,l,mid)); if(mid