线段树理论基础
一。基本概念
线段树（segment tree）是一种二叉搜索树，它的每一个结点对应着一个区间[L,R],叶子节点对应的是一个单位区间，即L==R。
对于一个非叶子结点[L,R],它的左儿子所表示的区间为[L,(L+R)/2],右儿子表示的区间为[(L+R)/2+1,R].根据定义，线段树是一棵平衡二叉树，它的叶子结点的数目为N，即整个区间的长度。
例如
区间【1，10】的线段树如图所示。
由于线段树是一棵平衡二叉树，所以它的高度为log级别，这是线段树时间复杂度良好的一个基础。
线段树用途很广，它主要用于进行区间更新和查询操作。这里的更新和查询一般至少有一个是指区间的更新和查询。由于更新和查询的种类数数不胜数，这也决定了线段树的灵活性，针对不同的问题，线段树的处理方式不同。
下面举一个简单的例子：
维护一个数列，每次进行两种操作：
1）修改一个元素。
2）查询一段区间的最大值。
这是经典的RMQ（range minimun/maximun query,区间最值查询）问题，用线段树该如何解决？题目既有更新，又有查询。
更新是点的更新，查询是区间查询。可以首先对原序列建立一颗线段树，然后对于更新操作，则对线段树的相应结点进行更新，对于查询操作则进行查询。
具体操作如下：每个结点维护所代表区间的左右端点和该区间的最值，建树的时候如果到叶子结点，那么这个结点的最值就是对应位置的数列的值，否则递归地建立左子树和右子树，然后将当前结点的区间最值设置为自己左子树和右子树最值的较大值。
如果是修改操作，则从根结点开始修改，一直修改到叶子结点，同时对路径上相应结点的最值进行更新。
如果是查询操作，则从根节点开始查询：如果查询区间在该结点的左子树内，则查询左子树；如果查询区间在右子树内，
则查询右子树，否则查询左子树相应区间的部分和右子树相应区间的部分，并将两者最大值返回。
二。"懒操作"
通常题目中会遇到对区间进行更新的操作，这时就体现线段树对区间操作的优越性。如果更新的区间完全覆盖线段树一个结点
所代表的区间时，就可以仅对该结点进行更新，并且做标记，表示这个结点更新过，然后对这个结点的子结点就不再更新，虽然这个子节点也在更新范围内。等到查询的时候再去更新它，不用就不更新。
一个区间被更新后，以后都可以不再查询这个区间或者其子区间。如果后边有关于这个区间或者子区间的查询，则一定会查询到做了标记的区间，说明区间被修改过，而他的子区间还没有被修改过（懒标记），就把这个标记传递给子区间，然后继续询问这个结点的子区间即可。
三。线段树的基本操作
#define MAXN 100
struct Node{
int l,r,mx;//l,r表示左右区间，mx表示最值 ，视题目而定
}tr[MAXN*4];//开四倍空间，至于为什么看上面的线段树的图或自己画
建树：
void build (int d,int l,int r)
{
tr[d].l=l; tr[d].r=r;
if(l==r)
{
tr[d].mx=b[l]; return;//叶子结点直接赋值，假设b数组是原数列
//记得return
} }
int mid=(l+r)/2,lc=d*2,rc=d*2+1;
build(lc,l,mid);
build(rc,mid+1,r);//递归建立左右子树
tr[d].mx=max(tr[lc].mx,tr[rc].mx); //最值等于两个孩子的最大值
}
查询:
int query(int d,int l,int r)//查询【l,r】的最值
{
if(tr[d].l==l&&tr[d].r==r){
return tr[d].mx; }
int mid=(l+r)/2,lc=d*2,rc=d*2+1;
if(r<=mid) return query(lc,l,mid);
else if(l>mid) return query(rc,mid+1,r);
else return max(query(lc,l,mid),query(rc,mid+1,r));
} }
更新：
void modify(int d,int pos,int v)//将pos处的元素换成v
{
if(tr[d].l==tr[d].r&&tr[d].l==pos){
tr[d].mx=v; return; }
int mid=(tr[d].l+tr[d].r)/2,lc=d*2,rc=d*2+1;
if(pos<=mid)modify(lc,pos,v);
else modify(rc,pos,v);
tr[d].mx=max(tr[lc].mx,tr[rc].mx);
}