好久沒(méi)寫過(guò)算法了，添一個(gè)吧，寫一個(gè)線段樹(shù)的入門知識(shí)，比較大眾化。
上次在湖大，其中的一道題數(shù)據(jù)很強(qiáng)，我試了好多種優(yōu)化都TLE，相信只能用線段樹(shù)才能過(guò)。回來(lái)之后暗暗又學(xué)了一次線段樹(shù)，想想好像是第三次學(xué)了，像網(wǎng)絡(luò)流一樣每學(xué)一次都有新的體會(huì)。
把問(wèn)題簡(jiǎn)化一下：
在自然數(shù)，且所有的數(shù)不大于30000的范圍內(nèi)討論一個(gè)問(wèn)題：現(xiàn)在已知n條線段，把端點(diǎn)依次輸入告訴你，然后有m個(gè)詢問(wèn)，每個(gè)詢問(wèn)輸入一個(gè)點(diǎn)，要求這個(gè)點(diǎn)在多少條線段上出現(xiàn)過(guò)；
最基本的解法當(dāng)然就是讀一個(gè)點(diǎn)，就把所有線段比一下，看看在不在線段中；
每次詢問(wèn)都要把n條線段查一次，那么m次詢問(wèn)，就要運(yùn)算m*n次，復(fù)雜度就是O(m*n)
這道題m和n都是30000，那么計(jì)算量達(dá)到了10^9；而計(jì)算機(jī)1秒的計(jì)算量大約是10^8的數(shù)量級(jí)，所以這種方法無(wú)論怎么優(yōu)化都是超時(shí)
-----
因?yàn)閚條線段是固定的，所以某種程度上說(shuō)每次都把n條線段查一遍有大量的重復(fù)和浪費(fèi)；
線段樹(shù)就是可以解決這類問(wèn)題的數(shù)據(jù)結(jié)構(gòu)
舉例說(shuō)明：已知線段[2,5] [4,6] [0,7]；求點(diǎn)2,4,7分別出現(xiàn)了多少次
在[0,7]區(qū)間上建立一棵滿二叉樹(shù)：（為了和已知線段區(qū)別，用【】表示線段樹(shù)中的線段）
【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】
每個(gè)節(jié)點(diǎn)用結(jié)構(gòu)體：
struct line
{
int left,right;//左端點(diǎn)、右端點(diǎn)
int n;//記錄這條線段出現(xiàn)了多少次，默認(rèn)為0
}a[16];
和堆類似，滿二叉樹(shù)的性質(zhì)決定a[i]的左兒子是a[2*i]、右兒子是a[2*i+1];
然后對(duì)于已知的線段依次進(jìn)行插入操作：
從樹(shù)根開(kāi)始調(diào)用遞歸函數(shù)insert
void insert(int s,int t,int step)//要插入的線段的左端點(diǎn)和右端點(diǎn)、以及當(dāng)前線段樹(shù)中的某條線段
{
if (s==a[step].left && t==a[step].right)
{
a[step].n++;//插入的線段匹配則此條線段的記錄+1
return;//插入結(jié)束返回
}
if (a[step].left==a[step].right) return;//當(dāng)前線段樹(shù)的線段沒(méi)有兒子，插入結(jié)束返回
int mid=(a[step].left+a[step].right)/2;
if (mid>=t) insert(s,t,step*2);//如果中點(diǎn)在t的右邊，則應(yīng)該插入到左兒子
else if (mid<s) insert(s,t,step*2+1);//如果中點(diǎn)在s的左邊，則應(yīng)該插入到右兒子
else//否則，中點(diǎn)一定在s和t之間，把待插線段分成兩半分別插到左右兒子里面
{
insert(s,mid,step*2);
insert(mid+1,t,step*2+1);
}
}
三條已知線段插入過(guò)程：
[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
插入過(guò)程結(jié)束，線段樹(shù)上的記錄如下（紅色數(shù)字為每條線段的記錄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
詢問(wèn)操作和插入操作類似，也是遞歸過(guò)程，略
2——依次把【0,7】 【0,3】 【2,3】 【2,2】的記錄n加起來(lái)，結(jié)果為2
4——依次把【0,7】 【4,7】 【4,5】 【4,4】的記錄n加起來(lái)，結(jié)果為3
7——依次把【0,7】 【4,7】 【6,7】 【7,7】的記錄n加起來(lái)，結(jié)果為1
不管是插入操作還是查詢操作，每次操作的執(zhí)行次數(shù)僅為樹(shù)的深度——logN
建樹(shù)有n次插入操作，n*logN，一次查詢要logN，m次就是m*logN；總共復(fù)雜度O(n+m)*logN，這道題N不超過(guò)30000，logN約等于14，所以計(jì)算量在10^5～10^6之間，比普通方法快了1000倍；
這道題是線段樹(shù)最基本的操作，只用到了插入和查找；刪除操作和插入類似，擴(kuò)展功能的還有測(cè)度、連續(xù)段數(shù)等等，在N數(shù)據(jù)范圍很大的時(shí)候，依然可以用離散化的方法建樹(shù)。
湖大的那道題目繞了個(gè)小彎子，alpc12有詳細(xì)的題目和解題報(bào)告，有興趣的話可以看看http://www.shnenglu.com/sicheng/archive/2008/01/09/40791.html
線段樹(shù)的經(jīng)典題目就是poj1177的picturehttp://acm.pku.edu.cn/JudgeOnline/problem?id=1177