二分法與統(tǒng)計(jì)問(wèn)題(線段樹(shù))

1、二分法與統(tǒng)計(jì)問(wèn)題 （ 線段樹(shù) ）OlCF -信息學(xué)奧林匹克綜合論壇 關(guān)鍵字 線段樹(shù) 二叉樹(shù) 二分法 摘要 我們經(jīng)常遇到統(tǒng)計(jì)的問(wèn)題。這些問(wèn)題的特點(diǎn)是，問(wèn)題表現(xiàn)得比較簡(jiǎn)單，一般 是對(duì)一定范圍內(nèi)的數(shù)據(jù)進(jìn)行處理， 用基本的方法就可以實(shí)現(xiàn)， 但是實(shí)際處理的規(guī) 模卻比較大， 粗劣的算法只能導(dǎo)致低效。 為了解決這種困難， 在統(tǒng)計(jì)中需要借助 一些特殊的工具， 如比較有效的數(shù)據(jù)結(jié)構(gòu)來(lái)幫助解決。 本文主要介紹的是分治的 思想結(jié)合一定的數(shù)據(jù)結(jié)構(gòu)， 使得統(tǒng)計(jì)的過(guò)程存在一定的模式， 以到達(dá)提高效率的 目的。首先簡(jiǎn)要介紹線段樹(shù)的基礎(chǔ)， 它是一種很適合計(jì)算幾何的數(shù)據(jù)結(jié)構(gòu)， 同時(shí) 也可以擴(kuò)充到其他方面。然后將介紹 lOl20

2、01 中涉及的一種特殊的統(tǒng)計(jì)方法。接著將會(huì)介紹一種與線段樹(shù)有所不同的構(gòu)造模式， 它的形式是二叉排序樹(shù)， 將會(huì) 發(fā)現(xiàn)這種方法是十分靈活的， 進(jìn)一步， 我們將略去對(duì)它的構(gòu)造， 在有序表中進(jìn)行 虛實(shí)現(xiàn)。目錄線段樹(shù)線段樹(shù)的構(gòu)造思想1.2線段樹(shù)處理數(shù)據(jù)的基本方法1.3應(yīng)用的優(yōu)勢(shì)1.4轉(zhuǎn)化為對(duì)點(diǎn)的操作一種解決動(dòng)態(tài)統(tǒng)計(jì)的靜態(tài)方法2.1 問(wèn)題的提出2.2 數(shù)據(jù)結(jié)構(gòu)的構(gòu)造和設(shè)想2.3 此種數(shù)據(jù)結(jié)構(gòu)的維護(hù)2.4 應(yīng)用的分析 三 在二叉排序樹(shù)上實(shí)現(xiàn)統(tǒng)計(jì)3.1 構(gòu)造可用于統(tǒng)計(jì)的靜態(tài)二叉排序樹(shù)3.2 進(jìn)行統(tǒng)計(jì)的方法分析3.3 一個(gè)較復(fù)雜的例子 四 虛二叉樹(shù)4.1 虛二叉樹(shù)實(shí)現(xiàn)的形態(tài)4.2 一個(gè)具體的例子4.3 最長(zhǎng)單調(diào)

3、序列的動(dòng)態(tài)規(guī)劃優(yōu)化問(wèn)題 正文 線段樹(shù)在一類問(wèn)題中，我們需要經(jīng)常處理可以映射在一個(gè)坐標(biāo)軸上的一些固定線 段，例如說(shuō)映射在 OX 軸上的線段。 由于線段是可以互相覆蓋的， 有時(shí)需要?jiǎng)討B(tài) 地取線段的并， 例如取得并區(qū)間的總長(zhǎng)度， 或者并區(qū)間的個(gè)數(shù)等等。 一個(gè)線段是 對(duì)應(yīng)于一個(gè)區(qū)間的，因此線段樹(shù)也可以叫做區(qū)間樹(shù)。1.1 線段樹(shù)的構(gòu)造思想線段樹(shù)處理的是一定的固定線段， 或者說(shuō)這些線段是可以對(duì)應(yīng)于有限個(gè)固定 端點(diǎn)的。處理問(wèn)題的時(shí)候，首先抽象出區(qū)間的端點(diǎn)，例如說(shuō)N個(gè)端點(diǎn)ti（1 <i < N）。那么對(duì)于任何一個(gè)要處理的線段（區(qū)間） a,b來(lái)說(shuō)，總可以找到 相應(yīng)的i,j ，使得ti=a,tj=b,

4、1 < i < j < N。這樣的轉(zhuǎn)換就使得線段樹(shù)上的區(qū)間表示為整數(shù)， 通過(guò)映射轉(zhuǎn)換，可以使得原問(wèn)題實(shí)數(shù)區(qū)間得到同樣的處理。下圖顯示了一個(gè)能夠表示 1 ， 10 的線段樹(shù)：線段樹(shù)是一棵二叉樹(shù)，樹(shù)中的每一個(gè)結(jié)點(diǎn)表示了一個(gè)區(qū)間a,b。每一個(gè)葉子節(jié)點(diǎn)上a+1=b,這表示了一個(gè)初等區(qū)間。對(duì)于每一個(gè)內(nèi)部結(jié)點(diǎn) b-a>1 ，設(shè)根為a,b的線段樹(shù)為T(a,b),則進(jìn)一步將此線段樹(shù)分為左子樹(shù)T(a,(a+b)/2),以及右子樹(shù)T(a+b)/2,b),直到分裂為一個(gè)初等區(qū)間為止。線段樹(shù)的平分構(gòu)造，實(shí)際上是用了二分的方法。線段樹(shù)是平衡樹(shù)，它的深度 為 Ig(b-a)如果采用動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)來(lái)

5、實(shí)現(xiàn)線段樹(shù)，結(jié)點(diǎn)的構(gòu)造可以用如下數(shù)據(jù)結(jié)構(gòu):TypeTno de=ATree no de;Tree no de=recordB,E:in teger;Count:i nteger;LeftChild,Rightchild:Tn ode;En d;其中B和E表示了該區(qū)間為B,E； Count為一個(gè)計(jì)數(shù)器，通常記錄覆蓋到此區(qū)間的線段的個(gè)數(shù)。LeftChild 和RightChild分別是左右子樹(shù)的根?；蛘邽榱朔奖?，我們也采用靜態(tài)的數(shù)據(jù)結(jié)構(gòu)。用數(shù)組 B，E，C，LSON ，RSON。設(shè)一棵線段樹(shù)的根為V。那么Bv,Ev 就是它所表示將區(qū)間c,d插入線段樹(shù)T(a,b), 并設(shè)T(a,b)的根編號(hào)為v區(qū)間

6、的界。Cv仍然用來(lái)作計(jì)數(shù)器。LSONv , RSONv分別表示了它的左兒子和右兒子的根編號(hào)。注意，這只是線段樹(shù)的基本結(jié)構(gòu)。通常利用線段樹(shù)的時(shí)候需要在每個(gè)結(jié)點(diǎn)上增加一些特殊的數(shù)據(jù)域，并且它們是隨線段的插入刪除進(jìn)行動(dòng)態(tài)維護(hù)的。這因題而異，同時(shí)又往往是解題的靈魂。1.2線段樹(shù)處理數(shù)據(jù)的基本方法線段樹(shù)的最基本的建立，插入和刪除的過(guò)程，以靜態(tài)數(shù)據(jù)結(jié)構(gòu)為例。建立線段樹(shù)（a,b ）:設(shè)一個(gè)全局變量n，來(lái)記錄一共用到了多少結(jié)點(diǎn)。開(kāi)始n=0p rocedure BUILD(a,b)beginn Jv JBvEvCvn+1/n記錄一共用到了多少結(jié)點(diǎn)nJ aJ bJ 0if b -a>1 thenbeginL

7、SONv J n+1 / 節(jié)點(diǎn)編號(hào)BUILD(a,里變化了RSONv J n+1/ 節(jié)點(diǎn)編號(hào)）/注意N在這endBUILD(，b)else if c<then DELETE(c,d;LSONv);procedure INSERT(c,d;v)beginelse if c<if c w Bv a nd Ev w d then Cv J Cv+1then INSERT(c,d;LSONv);if d>then INSERT(c,d;RSONv);end/如果跨區(qū)間了我們將看到兩次插入對(duì)于此算法的解釋：如果c ，d完全覆蓋了當(dāng)前線段，那么顯然該結(jié)點(diǎn)上的基數(shù)(即覆蓋線段數(shù))加1。否則

8、，如果c ，d不跨越區(qū)間中點(diǎn)，就只對(duì)左樹(shù)或者右樹(shù)上進(jìn)行插入。否則，在左樹(shù)和右樹(shù)上都要進(jìn)行插入。注意觀察 插入的路徑，一條待插入?yún)^(qū)間在某一個(gè)結(jié)點(diǎn)上進(jìn)行“跨越”，此后兩條子樹(shù)上都 要向下插入，但是這種跨越不可能多次發(fā)生。插入?yún)^(qū)間的時(shí)間復(fù)雜度是 O(logn)在線段上樹(shù)刪除一個(gè)區(qū)間與插入的方法幾乎是完全類似的:將區(qū)間c,d 刪除于線段樹(shù)T(a,b), 并設(shè)T(a,b)的根編號(hào)為vp rocedure DELETE(c,d;v)beginif c w Bv a nd Ev < d then Cv J Cv-1特別注意 ：只有曾經(jīng)插入過(guò)的區(qū)間才能夠進(jìn)行刪除。這樣才能保證線段樹(shù)的維護(hù)是正確的。例如，

9、在先前所示的線段樹(shù)上不能插入?yún)^(qū)間 1， 10 ，然 后刪除區(qū)間 2 ， 3 ，這顯然是不能得到正確結(jié)果的。線段樹(shù)的作用主要體現(xiàn)在可以動(dòng)態(tài)維護(hù)一些特征， 例如說(shuō)要得到線段樹(shù)上線 段并集的長(zhǎng)度，增加一個(gè)數(shù)據(jù)域 Mv ，討論： 如果 Cv>0,Mv = Ev-Bv; /yesCv=0 且 v 是葉子結(jié)點(diǎn)， Mv=0 ；Cv=0 且 v 是內(nèi)部結(jié)點(diǎn)， Mv=MLSONv+MRSONv;只要每次插入或刪除線段區(qū)間時(shí)，在訪問(wèn)到的結(jié)點(diǎn)上更新 M 的值，不妨稱之為UP DATA，就可以在插入和刪除的同時(shí)維持好 M。求整個(gè)線段樹(shù)的并集長(zhǎng) 度時(shí)，只要訪問(wèn) M ROOT 的值。這在許多動(dòng)態(tài)維護(hù)的題目中是非常有

10、用的， 它 使得每次操作的維護(hù)費(fèi)用只有 logn 。類似的，還有求并區(qū)間的個(gè)數(shù)等等。 這里不再深入列舉。1.3 應(yīng)用的優(yōu)勢(shì)線段樹(shù)的構(gòu)造主要是對(duì)區(qū)間線段的處理，它往往被應(yīng)用于幾何計(jì)算問(wèn)題中。比如說(shuō)處理一組矩形問(wèn)題時(shí)，可以用來(lái)求矩形并圖后的輪廓周長(zhǎng)和面積等等，比 普通的離散化效率更高。這些應(yīng)用可以在相關(guān)資料中查到。這里不作深入。1.4轉(zhuǎn)化為對(duì)點(diǎn)的操作線段樹(shù)處理的是區(qū)間線段的問(wèn)題，有些統(tǒng)計(jì)問(wèn)題處理的往往是點(diǎn)的問(wèn)題。而 點(diǎn)也是可以理解為特殊的區(qū)間的。 這時(shí)往往將線段樹(shù)的構(gòu)造進(jìn)行變形， 也就是說(shuō) 可以轉(zhuǎn)化為記錄點(diǎn)的結(jié)構(gòu)。變形:將線段樹(shù)上的初等區(qū)間分裂為具體的點(diǎn)，用來(lái)計(jì)數(shù)。即不存在（a,a+1） 這 樣的

11、區(qū)間，每個(gè)點(diǎn)分裂為a和a+1。同時(shí)按照區(qū)間的中點(diǎn)分界時(shí)，點(diǎn)要么落在 左子樹(shù)上，要么落在右子樹(shù)上。如下圖:原線段數(shù)記錄基數(shù)的Cv這時(shí)就可以用來(lái)計(jì)算落在定區(qū)間內(nèi)的點(diǎn)個(gè)數(shù)了。原搜索路徑也發(fā)生了改變，不存在“跨越”的情況。同時(shí)插入每個(gè)點(diǎn)的時(shí)候都必 須深入到葉結(jié)點(diǎn)，因此一般來(lái)說(shuō)都要有 log n的復(fù)雜度。應(yīng)用這樣的線段樹(shù)一方面是方便計(jì)數(shù)。另一方面由于它實(shí)際上是排序二叉 樹(shù)，所以容易找出最大和最小來(lái)。下面就看一個(gè)找最大最小的例子。例一 PROMOTION'可題（P010015）問(wèn)題大意:一位顧客要進(jìn)行n ( 1 < nW 5000 )天的購(gòu)物，每天他會(huì)有一些帳單。每天購(gòu)物以后， 他從以前的所

12、有帳單中挑出兩張帳單， 分別是面額最大的和面額 最小的一張， 并把這兩張帳單從記錄中去掉。 剩下的帳單留在以后繼續(xù)統(tǒng)計(jì)。 輸 入的數(shù)據(jù)保證，所有 n 天的帳單總數(shù)不超過(guò) 1000000 ，并且每份帳單的面額值 是 1 到 1000000 之間的整數(shù)。保證每天總可以找到兩張帳單。解決方法：這棵線段樹(shù)的范本題明顯地體現(xiàn)了動(dòng)態(tài)維護(hù)的特性，即每天都要插入一些面額隨機(jī)的帳單，同時(shí)還要找出最大和最小的兩張。 不妨建立前面所說(shuō)的線段樹(shù)，插入和刪除一份來(lái)說(shuō)，如果 CL如果 CRSON圍是 1， 1000000 ，即我們把所有面額的帳單設(shè)為一個(gè)點(diǎn)。帳單是顯然的。如何找到最大的帳單呢？顯然，對(duì)于一個(gè)樹(shù) vSONv

13、>0, 那么樹(shù) v 中的最小值一定在它的左子樹(shù)上。同樣，那么最大最小顯然對(duì)于v>0 ，它的最大值在右子樹(shù)上；否則，如果 CLSONv=0 的兩份帳單都在右子樹(shù)上。 所以線段樹(shù)的計(jì)數(shù)其實(shí)為我們提供了線索。一個(gè)特定面額來(lái)說(shuō)。它的插入，刪除，查找路徑是相同的，長(zhǎng)度為樹(shù)的深度，即log1000000=20 。如果總共有 N 張帳單，那么考慮極限時(shí)的復(fù)雜度為 N*20+n *20*2 。這比普通排序的實(shí)現(xiàn)要簡(jiǎn)單得多。 普通排序是 (N*n*20);本題還可以采取巧妙的辦法，線段樹(shù)不一定要存帳單的具體面額。由于我們 對(duì) 1000000 種面額都進(jìn)行了保存，所以線段樹(shù)顯得比較龐大。采取一種方法： 我們用 hash 來(lái)保存每一種面額的帳單數(shù)目， 然后對(duì)于一個(gè)具體的帳單， 例如面 額為 V ，我們?cè)诰€段樹(shù)中保存 V/100 的值，也就是說(shuō)，我們把連續(xù)的 100 種 面額的帳單看成是一組。由于 V 的