【正文】 二分法與統(tǒng)計問題 江蘇淮陰中學(xué) 李睿 1 二分法與統(tǒng)計問題 淮陰中學(xué) 李睿 [關(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)，同時也可以擴 充到其他方面。然后將介紹 IOI2022 中涉及的一種特殊的統(tǒng)計方法。接著將會介紹一種與線段樹有所不同的構(gòu)造模式，它的形式是二叉排序樹，將會發(fā)現(xiàn)這種方法是十分靈活的，進一步，我們將略去對它的構(gòu)造，在有序表中進行虛實現(xiàn)。 目錄 一 線段樹 線段樹的構(gòu)造思想 線段樹處理數(shù)據(jù)的基本方法 應(yīng)用的優(yōu)勢 轉(zhuǎn)化為對點的操作 二 一種解決動態(tài)統(tǒng)計的靜態(tài)方法 問題的提出 數(shù)據(jù)結(jié)構(gòu)的構(gòu)造和設(shè)想 此種數(shù)據(jù)結(jié)構(gòu)的維護 應(yīng)用的分析 三 在二叉排序樹上實現(xiàn)統(tǒng)計 構(gòu)造可用于統(tǒng)計的靜態(tài)二叉排序樹 進行統(tǒng)計的方法分析 一個較復(fù)雜的例子 四 虛二叉樹 虛二叉樹實現(xiàn)的形態(tài) 一個具體的例子 最長單調(diào)序列的動態(tài)規(guī)劃優(yōu)化問題 二分法與統(tǒng)計問題 江蘇淮陰中學(xué) 李睿 2 [正文 ] 一 線段樹 在一類問題中，我們需要經(jīng)常處理可以映射在一個坐標軸上的一些固定線段，例如說映射在 OX 軸上的線段。由于線段是可以互相覆蓋的，有時需要動態(tài)地取線段的并，例如取得并區(qū)間的總長度，或者并區(qū)間的個數(shù)等等。一個線段是對應(yīng)于一個區(qū)間的，因此線段樹也可以叫做區(qū)間樹。 線段樹的構(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]的線段樹： [1 ,1 0 ] [1 ,5 ] [5 ,1 0 ] [1 ,3 ] [3 ,5 ] [5 ,7 ] [7 ,1 0 ] [1 ,2 ] [2 ,3 ] [3 ,4 ] [4 ,5 ] [5 ,6 ] [6 ,7 ] [7 ,8 ] [8 ,1 0 ] [8 ,9 ] [9 ,1 0 ] 線段樹是一棵二叉樹，樹中的每一個結(jié)點表示了一個區(qū)間 [a,b]。每 一個葉子節(jié)點上 a+1=b,這表示了一個初等區(qū)間。對于每一個內(nèi)部結(jié)點 ba1，設(shè)根為 [a,b]的線段樹為 T(a,b),則進一步將此線段樹分為左子樹 T(a,(a+b)/2),以及右子樹T((a+b)/2,b),直到分裂為一個初等區(qū)間為止。 線段樹的平分構(gòu)造，實際上是用了二分的方法。線段樹是平衡樹，它的深度為 lg(ba)。 如果采用動態(tài)的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)線段樹，結(jié)點的構(gòu)造可以用如下數(shù)據(jù)結(jié)構(gòu)： 其中 B 和 E 表示了該區(qū)間為 [B,E]； Count 為一個計數(shù)器，通常記錄覆蓋到此區(qū)間的線段的個數(shù)。 LeftChild 和 RightChild 分別是左右子樹的根。 或者為了方便，我們也采用靜態(tài)的數(shù)據(jù)結(jié)構(gòu)。用數(shù)組 B[]， E[]， C[]， LSON[]，Type Tnode=^Treenode。 Treenode=record B,E:integer。 Count:integer。 LeftChild,Rightchild:Tnode。 End。 二分法與統(tǒng)計問題 江蘇淮陰中學(xué) 李睿 3 RSON[]。設(shè)一棵線段樹的根為 v。那么 B[v],E[v]就是它所表示區(qū)間的界。 C[v]仍然用來作計數(shù)器。 LSON[v]， RSON[v]分別表示了它的左兒子和右兒子的根編號。 注意，這只是線段樹的基本結(jié)構(gòu)。通常利用線段樹的時候需要在每個結(jié)點上增加一些特殊的數(shù)據(jù)域，并且它們是隨線段的插入刪除進行動態(tài)維護的。 這因題而異，同時又往往是解題的靈魂。 線段樹 處理數(shù)據(jù)的基本方法 線段樹的最基本的建立，插入和刪除的過程，以靜態(tài)數(shù)據(jù)結(jié)構(gòu)為例。 建立線段樹（ a,b） : 設(shè)一個全局變量 n，來記錄一共用到了多少結(jié)點。開始 n=0 將區(qū)間 [c,d]插入線段樹 T(a,b),并設(shè) T(a,b)的根編號為 v： 對于此算法的解釋：如果 [c， d]完全覆蓋了當(dāng)前線段，那么顯然該結(jié)點上的procedure BUILD(a,b) begin n ← n+1 v ← n B[v]← a E[v]← b C[v]← 0 if b – a1 then begin LSON[v]← n+1 BUILD(a,? ?2/)( ba? ) RSON[v]← n+1 BUILD(? ?2/)( ba? ,b) end end procedure INSERT(c,d。v) begin if c≤B[v] and E[v]≤ d then C[v] ← C[v]+1 else if c? ?2/])[][( vEvB ? then INSERT(c,d。LSON[v])。 if d? ?2/])[][( vEvB ? then INSERT(c,d。RSON[v])。 end 二分法與統(tǒng)計問題 江蘇淮陰中學(xué) 李睿 4 基數(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： 特別注意 ：只有曾經(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]。 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ù)等等。這里不再深入列舉。 應(yīng)用的優(yōu)勢 線段樹的構(gòu)造主要是對區(qū)間線段的處理，它往往被應(yīng)用于幾何計算問題中。比如說處理一組矩形問題時，可以用來求矩形并圖后的輪廓周長和面積等等，比普通的離散化效率更高。這些應(yīng)用可以在相關(guān)資料中查到。這里不作深入。 轉(zhuǎn)化為對點的操作 線段樹處理的是區(qū)間線段的問題，有些統(tǒng)計問題處理的往往是點的問題。而點也是可以理解為特殊的區(qū)間的。這時往往將線段樹的構(gòu)造進行變形，也就是說procedure DELETE(c,d。v) begin if c≤B[v] and E[v]≤ d then C[v] ← C[v]1 else if c? ?2/])[][( vEvB ? then DELETE(c,d。LSON[v])。 if d? ?2/])[][( vEvB ? then DELETE(c,d。RSON[v])。 end 二分法與統(tǒng)計問題 江蘇淮陰中學(xué) 李睿 5 可以轉(zhuǎn)化為記錄點的結(jié)構(gòu)。 變形： 將線 段樹上的初等區(qū)間分裂為具體的點，用來計數(shù)。即不存在 (a,a+1)這樣的區(qū)間，每個點分裂為 a 和 a+1。同時按照區(qū)間的中點分界時，點要么落在左子樹上，要么落在右子樹上。如下圖： [1 ,1 0 ] [1 ,4] [5 ,1 0 ] [1 ,2] [3 ,4] [5 ,7] [8 ,1 0 ] [1 ] [2 ] [3 ] [4 ] [5 ， 6] [7 ] [8 ,9 ] [1 0 ] [8 ] [5 ] [6 ] [9 ] 原線段數(shù)記錄基數(shù)的 C[v]這時就可以用來計算落在定區(qū)間內(nèi)的點個數(shù)了。原搜索路徑也發(fā)生了改變，不存在“跨越”的情況。同時插入每個點的時候都必須深入到葉結(jié)點，因此一般來說都要有 logn 的復(fù)雜度。 應(yīng)用這樣的線段樹一方面是方便計數(shù)。另一方面由于它實際上是排序二叉樹，所以容易找出最大和 最小來。下面就看一個找最大最小的例子。 [例一 ]PROMOTION 問題（ POI0015） 問題大意： 一位顧客要進行 n（ 1≤ n≤ 5000）天的購物，每天他會有一些帳單