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