好久没写过算法了，添一个吧，写一个线段树的入门知识，比较大众化。

上次在湖大，其中的一道题数据很强，我试了好多种优化都TLE，相信只能用线段树才能过。回来之后暗暗又学了一次线段树，想想好像是第三次学了，像网络流一样每学一次都有新的体会。

把问题简化一下：

在自然数，且所有的数不大于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的picturehttp://acm.PKU.edu.cn/JudgeOnline/problem?id=1177