线段树，顾名思义，就是指一个个线段组成的树。
线段树的定义就是：
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。
——摘自百度百科
如图，这就是一棵线段树：
那么线段树有哪些神奇的性质呢？
1.它是一棵满二叉树
2.每一个节点(一段区间)是它的两个子节点的并或最大值(RMQ)。
3.(因为线段树是满二叉树)树的空间复杂度是O(4N)；
线段树例题
线段树的树结构：
此处我用一个一维的数组seg[node]表示节点为node所划分到的区间的值。
线段树的建树：
因为线段树是一棵满二叉树，所以可以采用递归的方式来实现储存。
void build(int l,int r,int node)
{
if(l==r)seg[node]=a[l];//a[i]表示读入数列的第i个数
else
{
int mid=(l+r)>>;
build(l,mid,node*);
build(mid+,r,node*+);
up(node);//见下
}
return ;
}
Bulid
此处需要介绍一个up(node)函数。
这是用于对这个节点的区间值进行更新。
void up(int node){seg[node]=seg[node*]+seg[node*+];}
Up
建完树，但我们还需要做一些其他的操作，比如说区间查询(区间求和)或区间修改等。
所以我们就先介绍区间查询。
//L、R：目前访问区间的左右节点，ql，qr：查询区间的左右节点，node：当前节点的编号。
int query(int l,int r,int ql,int qr,int node)
{
if(l>=ql&&r<=qr)return seg[node];//①
else
{
int mid=(l+r)>>;
down(mid-l+,r-mid,node);//②
int ans=;
if(ql<=mid)ans+=query(l,mid,ql,qr,node*);//③
if(qr>mid) ans+=query(mid+,r,ql,qr,node*+);
return ans;
}
}
Query
①：因为线段树的节点表示一段区间，所以只要找到访问区间在查询区间内，就可以直接返回这段区间的值，不需要继续递归下去。
②：
{
这是个需要介绍的东西 称为Lazy标记。这是个很重要的东西，线段树的核心之一。
此处需要开一个add[node]数组，表示下标为node的节点需要加上add[node]的Lazy标记。这样就可以完成下放标记的任务。
void down(int l,int r,int node)
{
if(add[node]!=)//KC
{
add[node*]+=add[node];//向左子树下放标记
add[node*+]+=add[node];
seg[node*]+=add[node]*l;//④
seg[node*+]+=add[node]*r;
add[node]=;
}
return ;
}
Down
④：此处的l为上query函数的mid-l+1，为node节点的左子树的区间长度。之所以把 node左子树+Lazy标记*左子树区间长度 是因为每一个叶节点都需要加上此节点的Lazy标记。r处同上。
}
③：这需要解决的是为什么ql≤mid就可以直接ans+=query(node*2)。这主要是因为我们接下去寻找的是当前L~Mid区间里的在查询范围内的节点，因为ql≤mid无非就两种情况，l＜ql或l≥ql且r在此情况下都大于等于ql，又因为每次return回来的一定是查询区间范围内的值，所以只要ql≤mid就可以了。qr>mid同上。
下面是区间修改;
//v为区间内修改(增加或减少)的值
void change(int l,int r,int ql,int qr,int node,int v)
{
if(l>=ql&&r<=qr)
{
seg[node]+=v*(r-l+);//①
add[node]+=v;//①
return ;
}
else
{
int mid=(l+r)>>;
down(mid-l+,r-mid,node);
if(ql<=mid)change(l,mid,ql,qr,node*,v);
if(qr>mid) change(mid+,r,ql,qr,node*+,v);
up(node);//②
}
}
Change