用处
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数；
结构
线段树是建立在线段的基础上，每个结点都代表了一条线段[a,b]。
长度为1的线段称为元线段。
非元线段都有两个子结点，左结点代表的线段为[a,(a + b) / 2]，右结点代表的线段为[((a + b) / 2）+1,b]。
长度范围为[1,L] 的一棵线段树的深度为log (L) + 1。
这个显然，而且存储一棵线段树的空间复杂度为O(L）。
线段树支持最基本的操作为插入和删除一条线段。
下面以插入为例，详细叙述，删除类似。
将一条线段[a,b] 插入到代表线段[l,r]的结点p中，如果p不是元线段，那么令mid=（l+r）/2。
如果b<mid，那么将线段[a,b] 也插入到p的左儿子结点中，如果a>mid，那么将线段[a,b] 也插入到p的右儿子结点中。
插入（删除）操作的时间复杂度为O（logn）。
操作
单点查询；
单点修改；
区间求和；
区间修改；
区间操作可以用lazy优化时间复杂度。
变种
zkw线段树
怎么说呢，zkw线段树是一种简洁优美快速的非递归版线段树。
(因为我感觉zkw线段树完全可以取代普通线段树，所以就详细些。)
线段树的堆形构造：
线段树的堆式储存
我们来转成二进制看看
小学生问题:找规律
规律是很显然的
- 一个节点的父节点是这个数左移1，这个位运算就是低位舍弃，所有数字左移一位
- 一个节点的子节点是这个数右移1，是左节点，右移1+1是右节点
- 同一层的节点是依次递增的，第n层有2^(n-1)个节点
- 最后一层有多少节点，值域就是多少(这个很重要)
区间最小值
建叶节点
for(m=1;m<=n+1;m<<=1); for(int i=1;i<=n;i++) scanf("%d",t+m+i);
建非叶节点
void build_min(){for(int i=m-1;i>0;i--) t[i]=min_(t[i<<1],t[i<<1|1]);}
查找区间最小值
int search_min(int l,int r,int ret){ for(l+=m,r+=m;r-l!=1;l>>=1,r>>=1){ if(~l&1) ret=min_(ret,t[l^1]); if(r&1) ret=min_(ret,t[r^1]); } return ret; }
成功解决区间最小值问题；
标记问题
标记永久化；
永久化的标记就是值；
——zkw
同样的区间改值；
同样的标记位置；
不用下传！
由底向上；
遇到标记按规则变动；
例题
致敬：http://blog.csdn.NET/qq_18455665/article/details/50989113 (gdl,so http://blog.csdn.net/keshuqi/article/details/52205884)
可持久化线段树