在自然数，且所有的数不大于30000的范围内讨论一个问题：现在已知n条线段，把端点依次输入告诉你，然后有m个询问，每个询问输入一个点，要求这个点在多少条线段上出现过；
最基本的解法当然就是读一个点，就把所有线段比一下，看看在不在线段中；
每次询问都要把n条线段查一次，那么m次询问，就要运算m*n次，复杂度就是O(m*n)
这道题m和n都是30000，那么计算量达到了10^9；而计算机1秒的计算量大约是10^8的数量级，所以这种方法无论怎么优化都是超时
-----
因为n条线段是固定的，所以某种程度上说每次都把n条线段查一遍有大量的重复和浪费；
线段树就是可以解决这类问题的数据结构
举例说明：已知线段[2,5] [4,6] [0,7]；求点2,4,7分别出现了多少次
在[0,7]区间上建立一棵满二叉树：（为了和已知线段区别，用【】表示线段树中的线段）
【0,7】
/ \
【0,3】 【4,7】
/ \ / \
【0,1】 【2,3】 【4,5】 【6,7】
/ \ / \ / \ / \
【0,0】 【1,1】【2,2】 【3,3】 【4,4】 【5,5】 【6,6】 【7,7】
每个节点用结构体：
struct line
{
int left,right;//左端点、右端点
int n;//记录这条线段出现了多少次，默认为0
}a[16];
和堆类似，满二叉树的性质决定a[i]的左儿子是a[2*i]、右儿子是a[2*i+1];
然后对于已知的线段依次进行插入操作：
从树根开始调用递归函数insert
void insert(int s,int t,int step)//要插入的线段的左端点和右端点、以及当前线段树中的某条线段
{
if (s==a[step].left && t==a[step].right)
{
a[step].n++;//插入的线段匹配则此条线段的记录+1
return;//插入结束返回
}
if (a[step].left==a[step].right) return;//当前线段树的线段没有儿子，插入结束返回
int mid=(a[step].left+a[step].right)/2;
if (mid>=t) insert(s,t,step*2);//如果中点在t的右边，则应该插入到左儿子
else if (mid<s) insert(s,t,step*2+1);//如果中点在s的左边，则应该插入到右儿子
else//否则，中点一定在s和t之间，把待插线段分成两半分别插到左右儿子里面
{
insert(s,mid,step*2);
insert(mid+1,t,step*2+1);
}
}
|
三条已知线段插入过程：
[2,5]
--[2,5]与【0,7】比较，分成两部分：[2,3]插到左儿子【0,3】，[4,5]插到右儿子【4,7】
--[2,3]与【0,3】比较，插到右儿子【2,3】；[4,5]和【4,7】比较，插到左儿子【4,5】
--[2,3]与【2,3】匹配，【2,3】记录+1；[4,5]与【4,5】匹配，【4,5】记录+1
[4,6]
--[4,6]与【0,7】比较，插到右儿子【4,7】
--[4,6]与【4,7】比较，分成两部分，[4,5]插到左儿子【4,5】；[6,6]插到右儿子【6,7】
--[4,5]与【4,5】匹配，【4,5】记录+1；[6,6]与【6,7】比较，插到左儿子【6,6】
--[6,6]与【6,6】匹配，【6,6】记录+1
[0,7]
--[0,7]与【0,7】匹配，【0,7】记录+1
插入过程结束，线段树上的记录如下（红色数字为每条线段的记录n）：
【0,7】
1
/ \
【0,3】 【4,7】
0 0
/ \ / \
【0,1】 【2,3】 【4,5】 【6,7】
0 1 2 0
/ \ / \ / \ / \
【0,0】 【1,1】 【2,2】 【3,3】 【4,4】 【5,5】 【6,6】 【7,7】
0 0 0 0 0 0 1 0
询问操作和插入操作类似，也是递归过程，略
2——依次把【0,7】 【0,3】 【2,3】 【2,2】的记录n加起来，结果为2
4——依次把【0,7】 【4,7】 【4,5】 【4,4】的记录n加起来，结果为3
7——依次把【0,7】 【4,7】 【6,7】 【7,7】的记录n加起来，结果为1
不管是插入操作还是查询操作，每次操作的执行次数仅为树的深度——logN
建树有n次插入操作，n*logN，一次查询要logN，m次就是m*logN；总共复杂度O(n+m)*logN，这道题N不超过30000，logN约等于14，所以计算量在10^5～10^6之间，比普通方法快了1000倍；
这道题是线段树最基本的操作，只用到了插入和查找；删除操作和插入类似，扩展功能的还有测度、连续段数等等，在N数据范围很大的时候，依然可以用离散化的方法建树。
湖大的那道题目绕了个小弯子，alpc12有详细的题目和解题报告，有兴趣的话可以看看http://www.cppblog.com/sicheng/archive/2008/01/09/40791.html
线段树的经典题目就是poj1177的picture
http://acm.pku.edu.cn/JudgeOnline/problem?id=1177
扩展：http://edu.codepub.com/2009/1125/18163.php
模板：
==================线段树模板==============================
//hdu 1166 hdu1754 hdu1698等可作为练习题
//下面的模板基于区间求和
int num[N];//原始数组,下标从1开始
struct Seg_Tree{
int lft,rgt,value; //左端点，右端点，端点值
int calmid() {
return (lft+rgt)>>1;
}
}tt[3*N];//线段树的结点
int build(int lft,int rgt,int idx) { //建树, 其中idx表示结点的编号，调用时可以build(1,n,1);表示根为1
tt[idx].lft = lft;
tt[idx].rgt = rgt;
if(lft == rgt) return tt[idx].value = num[lft];
int mid = (lft + rgt)>>1;
// @下面这句依具体的题目而更新
return tt[idx].value = build(lft,mid,2*idx) + build(mid+1,rgt,2*idx+1);
}
void update(int id,int x,int idx) { //更新树结点,其中id为要更新的结点，x为增加的值
tt[idx].value += x; // @此处依具体的题目而更新
if(tt[idx].lft == tt[idx].rgt) {
return ;
}
int mid = tt[idx].calmid();
if(id <= mid) {
update(id,x,2*idx);
} else {
update(id,x,2*idx+1);
}
}
/* 求区间最值的更新函数; 如果要成段更新的题目，则要传入区间的左右下标重写更新的询问函数
void update(int id,int x,int idx) {
if(tt[idx].lft == tt[idx].rgt){
tt[idx].value = x;
return ;
}
int mid = tt[idx].calmid();
if(id <= mid) {
update(id,x,2*idx);
} else {
update(id,x,2*idx+1);
}
tt[idx].value = max(tt[2*idx].value , tt[2*idx+1].value);
}*/
int query(int lft,int rgt,int idx) { //树求和 ，调用时idx为树根的编号
if(lft == tt[idx].lft && rgt == tt[idx].rgt) {
return tt[idx].value;
}
int mid = tt[idx].calmid();
if(rgt <= mid) {
return query(lft,rgt,2*idx);
} else if(mid < lft) {
return query(lft,rgt, 2*idx+1);
} else {
return query(lft,mid,2*idx) + query(mid+1,rgt,2*idx+1); // @此处依具体的题目而更新
}
}
应用：
线段树应用：
求面积:
1) 坐标离散化
2) 垂直边按x坐标排序
3) 从左往右用线段树处理垂直边
累计每个离散x区间长度和线段树长度的乘积
求周长:
1) 坐标离散化
2) 垂直边按x坐标排序, 第二关键字为入边优于出边
3) 从左往右用线段树处理垂直边
在每个离散点上先加入所有入边, 累计线段树长度变化值
再删除所有出边, 累计线段树长度变化值
4) 水平边按y坐标排序, 第二关键字为入边优于出边
5) 从上往下用线段树处理水平边
在每个离散点上先加入所有入边, 累计线段树长度变化值
再删除所有出边, 累计线段树长度变化值
//线段树扩展
//可以计算长度和线段数
//可以处理加入边和删除边不同的情况
//inc_seg和dec_seg用于加入边
//seg_len求长度,seg_cut求线段数
//t传根节点(一律为1)
//l0,r0传树的节点范围(一律为1..t)
//l,r传线段(端点)
#define MAXN 10000
struct segtree{
int n,cnt[MAXN],len[MAXN],cut[MAXN],bl[MAXN],br[MAXN];
segtree(int t):n(t){
for (int i=1;i<=t;i++)
cnt[i]=len[i]=cut[i]=bl[i]=br[i]=0;
};
void update(int t,int l,int r);
void inc_seg(int t,int l0,int r0,int l,int r);
void dec_seg(int t,int l0,int r0,int l,int r);
int seg_len(int t,int l0,int r0,int l,int r);
int seg_cut(int t,int l0,int r0,int l,int r);
};
int length(int l,int r){
return r-l;
}
void segtree::update(int t,int l,int r){
if (cnt[t]||r-l==1)
len[t]=length(l,r),cut[t]=bl[t]=br[t]=1;
else{
len[t]=len[t+t]+len[t+t+1];
cut[t]=cut[t+t]+cut[t+t+1];
if (br[t+t]&&bl[t+t+1])
cut[t]--;
bl[t]=bl[t+t],br[t]=br[t+t+1];
}
}
void segtree::inc_seg(int t,int l0,int r0,int l,int r){
if (l0==l&&r0==r)
cnt[t]++;
else{
int m0=(l0+r0)>>1;
if (l<m0)
inc_seg(t+t,l0,m0,l,m0<r?m0:r);
if (r>m0)
inc_seg(t+t+1,m0,r0,m0>l?m0:l,r);
if (cnt[t+t]&&cnt[t+t+1]){
cnt[t+t]--;
update(t+t,l0,m0);
cnt[t+t+1]--;
update(t+t+1,m0,r0);
cnt[t]++;
}
}
update(t,l0,r0);
}
void segtree::dec_seg(int t,int l0,int r0,int l,int r){
if (l0==l&&r0==r)
cnt[t]--;
else if (cnt[t]){
cnt[t]--;
if (l>l0)
inc_seg(t,l0,r0,l0,l);
if (r<r0)
inc_seg(t,l0,r0,r,r0);
}
else{
int m0=(l0+r0)>>1;
if (l<m0)
dec_seg(t+t,l0,m0,l,m0<r?m0:r);
if (r>m0)
dec_seg(t+t+1,m0,r0,m0>l?m0:l,r);
}
update(t,l0,r0);
}
int segtree::seg_len(int t,int l0,int r0,int l,int r){
if (cnt[t]||(l0==l&&r0==r))
return len[t];
else{
int m0=(l0+r0)>>1,ret=0;
if (l<m0)
ret+=seg_len(t+t,l0,m0,l,m0<r?m0:r);
if (r>m0)
ret+=seg_len(t+t+1,m0,r0,m0>l?m0:l,r);
return ret;
}
}
int segtree::seg_cut(int t,int l0,int r0,int l,int r){
if (cnt[t])
return 1;
if (l0==l&&r0==r)
return cut[t];
else{
int m0=(l0+r0)>>1,ret=0;
if (l<m0)
ret+=seg_cut(t+t,l0,m0,l,m0<r?m0:r);
if (r>m0)
ret+=seg_cut(t+t+1,m0,r0,m0>l?m0:l,r);
if (l<m0&&r>m0&&br[t+t]&&bl[t+t+1])
ret--;
return ret;
}
}