前置知识
创新互联公司2013年成立，先为策勒等服务建站，策勒等地企业，进行企业商务咨询服务。为策勒企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
二叉树
定义
基本操作复杂度： $ O(logn) $
线段树是一棵二叉树，每个节点表示序列上的一段区间，其中根节点表示区间[1,n]。
从根节点开始，只要区间长度不为1，就将区间划分为两半，并分给两个子节点。
若当前节点表示区间[l,r]，
当l≠r时，左孩子表示[l,(l+r)/2]，右孩子表示[(l+r)/2+1,r]；
当l=r时，该节点为叶子节点。
基本性质
性质1
线段树的总节点数为2n-1。
性质2
线段树的层数约为 $ log_{ 2 } n $ ，即每个叶节点到根节点的距离约为 \(log_{2}n\) 。
性质3
任何区间都可以用不超过 \(2log_{2}n\) 个节点组合而成。
编号
线段树的编号方式通常有两种：即2i和2i+1作i的孩子或按构建顺序编号。
存储
线段树的存储也有两种方式：多个数组或struct结构体。
以struct结构体数组为例:
（lc,rc分别为左右孩子的编号，sum为该区间的总和。
数组大小为序列长度两倍。
至于区间的左右端点[l,r]，可以存储，也可以递归时计算。
若需要节省空间，则不存储。）
构建
构建过程递归实现，
void build(int u,int l,int r)
（u为当前节点编号，l,r为区间端点）
从根节点开始构建，递归时计算并代入l,r，若l=r，该点为叶子节点，令sum=序列原值，否则，递归构建左右孩子，之后令sum=sum左孩子+sum右孩子。
在主程序中：
t=1;
build(1,1,n);
即可。
应用
单点修改
修改过程递归实现，
void update(int u,int l,int r,int x,int w)
（u当前节点编号,l和r为区间端点，x为要修改的位置，w为变化量）
从根节点开始修改，若当前点为叶子节点，使sum+=w并返回
否则判断x在左孩子还是右孩子，递归进行修改，之后令sum=左孩子sum+右孩子sum。
在主程序中调用：
update(1,1,n,x,y);
区间和查询
查询过程递归实现，
void query(int u,int l,int r,int ll,int rr)
（u为当前节点，l和r是区间端点，ll和rr分别为所查询区间的左右端点）
需要用外层定义变量ans储存答案。
从根节点开始，首先判断查询区间与节点区间是否完全重合，若重合，ans+=sum并返回，否则判断查询区间是否完全在左孩子或者右孩子，若是则递归查询。否则将查询区间拆分，两侧分别递归查询。
在主程序中：
ans=0;
query(1,1,n,x,y);
维护区间最大值/最小值
区间修改
我们在线段树的每个节点上再储存一个信息，称为“标记”，记为tag，表示该节点所包含的每个位置，都要再加上tag。
首先，像区间询问一样将区间对应到尽量少的节点上，
令它们
sum+=(r-l+1)*w;//增加的区间和
tag+=w;//增加标记
然后将sum信息向上pushup。
区间修改后的单点/区间查询
查询与之前类似，
查询过程递归实现，
void query(int u,int l,int r,int ll,int rr,int w)
但由于标记的出现，多了“下传标记”一步。
下传标记时，孩子的标记要叠加。
类似于pushup，标记下传的过程写入一个
void pushdown(int u,int l,int r)
注
一个节点上的tag一定已经计入自身的sum。
在修改和查询时，只要需要进入子节点，就一定要pushdown。
注意
当维护信息较多时，为简化代码，通常将类似于”a[u].sum=a[a[u].lc].sum+a[a[u].rc].sum”的上传信息的步骤写入void pushup(int u)并调用pushup(u);
并非原创，仅是整理，请见谅
本文题目：线段树
标题网址：
http://cdkjz.cn/article/dsoipoh.html
