看到一篇比較好的論文 轉(zhuǎn)給大家看其中的線段樹部分
二分法與統(tǒng)計問題
淮陰中學
李睿
[
關(guān)鍵字
]
??????
線段樹
二叉樹
二分法
?
[
摘要
]
??????
我們經(jīng)常遇到統(tǒng)計的問題。這些問題的特點是，問題表現(xiàn)得比較簡單，一般是對一定范圍內(nèi)的數(shù)據(jù)進行處理，用基本的方法就可以實現(xiàn)，但是實際處理的規(guī)模卻比較大，粗劣的算法只能導(dǎo)致低效。為了解決這種困難，在統(tǒng)計中需要借助一些特殊的工具，如比較有效的數(shù)據(jù)結(jié)構(gòu)來幫助解決。本文主要介紹的是分治的思想結(jié)合一定的數(shù)據(jù)結(jié)構(gòu)，使得統(tǒng)計的過程存在一定的模式，以到達提高效率的目的。首先簡要介紹線段樹的基礎(chǔ)，它是一種很適合計算幾何的數(shù)據(jù)結(jié)構(gòu)，同時也可以擴充到其他方面。然后將介紹
IOI2001
中涉及的一種特殊的統(tǒng)計方法。接著將會介紹一種與線段樹有所不同的構(gòu)造模式，它的形式是二叉排序樹，將會發(fā)現(xiàn)這種方法是十分靈活的，進一步，我們將略去對它的構(gòu)造，在有序表中進行虛實現(xiàn)。
?
目錄
一
線段樹
1.1
線段樹的構(gòu)造思想
1.2
線段樹處理數(shù)據(jù)的基本方法
1.3
應(yīng)用的優(yōu)勢
1.4
轉(zhuǎn)化為對點的操作
?
二
一種解決動態(tài)統(tǒng)計的靜態(tài)方法
2.1??
問題的提出
2.2
數(shù)據(jù)結(jié)構(gòu)的構(gòu)造和設(shè)想
2.3
此種數(shù)據(jù)結(jié)構(gòu)的維護
2.4
應(yīng)用的分析
?
三
在二叉排序樹上實現(xiàn)統(tǒng)計
3.1
構(gòu)造可用于統(tǒng)計的靜態(tài)二叉排序樹
3.2
進行統(tǒng)計的方法分析
3.3
一個較復(fù)雜的例子
?
四
虛二叉樹
4.1
虛二叉樹實現(xiàn)的形態(tài)
4.2
一個具體的例子
4.3
最長單調(diào)序列的動態(tài)規(guī)劃優(yōu)化問題
?
[
正文
]
一
線段樹
??????
在一類問題中，我們需要經(jīng)常處理可以映射在一個坐標軸上的一些固定線段，例如說映射在
OX
軸上的線段。由于線段是可以互相覆蓋的，有時需要動態(tài)地取線段的并，例如取得并區(qū)間的總長度，或者并區(qū)間的個數(shù)等等。一個線段是對應(yīng)于一個區(qū)間的，因此線段樹也可以叫做區(qū)間樹。
?
1.1
線段樹的構(gòu)造思想
??????
線段樹處理的是一定的固定線段，或者說這些線段是可以對應(yīng)于有限個固定端點的。處理問題的時候，首先抽象出區(qū)間的端點，例如說
N
個端點
ti(1
≤
i
≤
N)
。那么對于任何一個要處理的線段（區(qū)間）
[a,b]
來說，總可以找到相應(yīng)的
i,j
，使得
ti=a,tj=b,1
≤
i
≤
j
≤
N
。這樣的轉(zhuǎn)換就使得線段樹上的區(qū)間表示為整數(shù)，通過映射轉(zhuǎn)換，可以使得原問題實數(shù)區(qū)間得到同樣的處理。下圖顯示了一個能夠表示
[1
，
10]
的線段樹：
??????
線段樹是一棵二叉樹，樹中的每一個結(jié)點表示了一個區(qū)間
[a,b]
。每一個葉子節(jié)點上
a+1=b,
這表示了一個初等區(qū)間。對于每一個內(nèi)部結(jié)點
b-a>1
，設(shè)根為
[a,b]
的線段樹為
T(a,b),
則進一步將此線段樹分為左子樹
T(a,(a+b)/2),
以及右子樹
T((a+b)/2,b),
直到分裂為一個初等區(qū)間為止。
??????
線段樹的平分構(gòu)造，實際上是用了二分的方法。線段樹是平衡樹，它的深度為
lg(b-a)
。
?
??????
如果采用動態(tài)的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)線段樹，結(jié)點的構(gòu)造可以用如下數(shù)據(jù)結(jié)構(gòu)：
Type
?????? Tnode=^Treenode;
?????? Treenode=record
?????????????
B,E:integer;
?????????????
Count:integer;
?????????????
LeftChild,Rightchild:Tnode;
?????? End;
?
|
?
?
?
?
?
?
?
?
??????
其中
B
和
E
表示了該區(qū)間為
[B,E]
；
Count
為一個計數(shù)器，通常記錄覆蓋到此區(qū)間的線段的個數(shù)。
LeftChild
和
RightChild
分別是左右子樹的根。
??????
或者為了方便，我們也采用靜態(tài)的數(shù)據(jù)結(jié)構(gòu)。用數(shù)組
B[]
，
E[]
，
C[]
，
LSON[]
，
RSON[]
。設(shè)一棵線段樹的根為
v
。那么
B[v],E[v]
就是它所表示區(qū)間的界。
C[v]
仍然用來作計數(shù)器。
LSON[v]
，
RSON[v]
分別表示了它的左兒子和右兒子的根編號。
?
??????
注意，這只是線段樹的基本結(jié)構(gòu)。通常利用線段樹的時候需要在每個結(jié)點上增加一些特殊的數(shù)據(jù)域，并且它們是隨線段的插入刪除進行動態(tài)維護的。
這因題而異，同時又往往是解題的靈魂。
?
1.2
線段樹處理數(shù)據(jù)的基本方法
??????
線段樹的最基本的建立，插入和刪除的過程，以靜態(tài)數(shù)據(jù)結(jié)構(gòu)為例。
?
建立線段樹（
a,b
）
:
設(shè)一個全局變量
n
，來記錄一共用到了多少結(jié)點。開始
n=0
procedure
BUILD(a,b)
begin
n
←
n+1//n
記錄一共用到了多少結(jié)點
v
←
n
B[v]
←
a
E[v]
←
b
C[v]
←
0
if
b – a>1 then
begin
LSON[v]
←
n+1 //
節(jié)點編號
BUILD(a,) //
注意
N
在這里變化了
RSON[v]
←
n+1//
節(jié)點編號
BUILD(?,b)
end
end
|
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
將區(qū)間
[c,d]
插入線段樹
T(a,b),
并設(shè)
T(a,b)
的根編號為
v
：
?
procedure
INSERT(c,d;v)
begin
??????
if c≤B[v] and E[v]
≤
d then C[v]
←
C[v]+1
??????
else if
? c<?then INSERT(c,d;LSON[v]);
?????????????
if
? d>?then INSERT(c,d;RSON[v]);
end//
如果跨區(qū)間了
我們將看到兩次插入
|
?
?
?
?
?
?
?
?
?
??????
對于此算法的解釋：如果
[c
，
d]
完全覆蓋了當前線段，那么顯然該結(jié)點上的基數(shù)（即覆蓋線段數(shù)）加
1
。否則，如果
[c
，
d]
不跨越區(qū)間中點，就只對左樹或者右樹上進行插入。否則，在左樹和右樹上都要進行插入。注意觀察插入的路徑，一條待插入?yún)^(qū)間在某一個結(jié)點上進行“跨越”，此后兩條子樹上都要向下插入，但是這種跨越不可能多次發(fā)生。插入?yún)^(qū)間的時間復(fù)雜度是
O(logn)
。
?
在線段上樹刪除一個區(qū)間與插入的方法幾乎是完全類似的：
?
將區(qū)間
[c,d]
刪除于線段樹
T(a,b),
并設(shè)
T(a,b)
的根編號為
v
：
procedure
DELETE(c,d;v)
begin
??????
if c≤B[v] and E[v]
≤
d then C[v]
←
C[v]-1
??????
else if
? c<?then DELETE(c,d;LSON[v]);
?????????????
if
? d>?then DELETE(c,d;RSON[v]);
end
|
?
?
?
?
?
?
?
?
?
?
??????
特別注意
：只有曾經(jīng)插入過的區(qū)間才能夠進行刪除。這樣才能保證線段樹的維護是正確的。例如，在先前所示的線段樹上不能插入?yún)^(qū)間
[1
，
10]
，然后刪除區(qū)間
[2
，
3]
，這顯然是不能得到正確結(jié)果的。
?
??????
線段樹的作用主要體現(xiàn)在可以動態(tài)維護一些特征，例如說要得到線段樹上線段并集的長度，增加一個數(shù)據(jù)域
M[v]
，討論：
如果
C[v]>0,M[v] = E[v]-B[v];? //yes
C[v]=0
且
v
是葉子結(jié)點，
M[v]=0
；
C[v]=0
且
v
是內(nèi)部結(jié)點，
M[v]=M[LSON[v]]+M[RSON[v]];
?
??????
只要每次插入或刪除線段區(qū)間時，在訪問到的結(jié)點上更新
M
的值，不妨稱之為
UPDATA
，就可以在插入和刪除的同時維持好
M
。求整個線段樹的并集長度時，只要訪問
M[ ROOT]
的值。這在許多動態(tài)維護的題目中是非常有用的，它使得每次操作的維護費用只有
logn
。
??????
??????
類似的，還有求并區(qū)間的個數(shù)等等。這里不再深入列舉。
?
1.3
應(yīng)用的優(yōu)勢
??????
線段樹的構(gòu)造主要是對區(qū)間線段的處理，它往往被應(yīng)用于幾何計算問題中。比如說處理一組矩形問題時，可以用來求矩形并圖后的輪廓周長和面積等等，比普通的離散化效率更高。這些應(yīng)用可以在相關(guān)資料中查到。這里不作深入。
?
1.4
轉(zhuǎn)化為對點的操作
??????
線段樹處理的是區(qū)間線段的問題，有些統(tǒng)計問題處理的往往是點的問題。而點也是可以理解為特殊的區(qū)間的。這時往往將線段樹的構(gòu)造進行變形，也就是說可以轉(zhuǎn)化為記錄點的結(jié)構(gòu)。
變形：
??????
將線段樹上的初等區(qū)間分裂為具體的點，用來計數(shù)。即不存在
(a,a+1)
這樣的區(qū)間，每個點分裂為
a
和
a+1
。同時按照區(qū)間的中點分界時，點要么落在左子樹上，要么落在右子樹上。如下圖：
??????
原線段數(shù)記錄基數(shù)的
C[v]
這時就可以用來計算落在定區(qū)間內(nèi)的點個數(shù)了。原搜索路徑也發(fā)生了改變，不存在“跨越”的情況。同時插入每個點的時候都必須深入到葉結(jié)點，因此一般來說都要有
logn
的復(fù)雜度。
??????
應(yīng)用這樣的線段樹一方面是方便計數(shù)。另一方面由于它實際上是排序二叉樹，所以容易找出最大和最小來。下面就看一個找最大最小的例子。
?
[
例一
]PROMOTION
問題（
POI0015
）
問題大意：
??????
一位顧客要進行
n
（
1
≤
n
≤
5000
）天的購物，每天他會有一些帳單。每天購物以后，他從以前的所有帳單中挑出兩張帳單，分別是面額最大的和面額最小的一張，并把這兩張帳單從記錄中去掉。剩下的帳單留在以后繼續(xù)統(tǒng)計。輸入的數(shù)據(jù)保證，所有
n
天的帳單總數(shù)不超過
1000000
，并且每份帳單的面額值是
1
到
1000000
之間的整數(shù)。保證每天總可以找到兩張帳單。
解決方法：
??????
本題明顯地體現(xiàn)了動態(tài)維護的特性，即每天都要插入一些面額隨機的帳單，同時還要找出最大和最小的兩張。不妨建立前面所說的線段樹，這棵線段樹的范圍是
[1
，
1000000]
，即我們把所有面額的帳單設(shè)為一個點。插入和刪除一份帳單是顯然的。如何找到最大的帳單呢？顯然，對于一個樹
v
來說，如果
C[LSON[v]]>0,
那么樹
v
中的最小值一定在它的左子樹上。同樣，如果
C[RSON[v]]>0
，它的最大值在右子樹上；否則，如果
C[LSON[v]]=0
，那么最大最小的兩份帳單都在右子樹上。所以線段樹的計數(shù)其實為我們提供了線索。顯然對于一個特定面額來說。它的插入，刪除，查找路徑是相同的，長度為樹的深度，即
log1000000=20
。如果總共有
N
張帳單，那么考慮極限時的復(fù)雜度為
N*20+n*20*2
。這比普通排序的實現(xiàn)要簡單得多。普通排序是
(N*n*20);
??????
本題還可以采取巧妙的辦法，線段樹不一定要存帳單的具體面額。由于我們對
1000000
種面額都進行了保存，所以線段樹顯得比較龐大。采取一種方法：我們用
hash
來保存每一種面額的帳單數(shù)目，然后對于一個具體的帳單，例如面額為
V
，我們在線段樹中保存
V/100
的值，也就是說，我們把連續(xù)的
100
種面額的帳單看成是一組。由于
V
的范圍是
[1..1000000]
，所以線段樹中有
10000
個點。在找最大的數(shù)的時候，首先找到最小的組，然后在
hash
里對這個組進行搜索，顯然這個搜索的規(guī)模不會超過
100
。由于線段樹變小了，所以樹的深度只有
14
左右，整個問題的復(fù)雜度極限為
N*14+n*14*100*2
，對于問題的規(guī)模來說，仍然是高效率的。但這樣做比前種方法在一定程度上節(jié)省了空間。同時實際上也提醒了我們對線段樹應(yīng)該加以靈活的應(yīng)用。