【文章內(nèi)容簡(jiǎn)介】 9 前面所涉及的線段樹不可比的。但本節(jié)的統(tǒng)計(jì)方法也存在缺陷，它似乎不太容易推廣到其他問(wèn)題。仔細(xì)研究過(guò)線段樹會(huì)知道它能夠支持很多特殊的統(tǒng)計(jì)問(wèn)題。這些將會(huì)通過(guò)實(shí)踐體現(xiàn)出來(lái)。下面再介紹一些其他的實(shí)現(xiàn)方法。 三 在二叉排序樹上實(shí)現(xiàn)統(tǒng)計(jì) 前面已經(jīng)講過(guò)，線段樹 經(jīng)過(guò)左右分割以后實(shí)際上具有二叉排序樹的性質(zhì)。另一方面，前面也說(shuō)明過(guò)，線段樹的建立方式非常適用于處理線段，對(duì)于點(diǎn)的問(wèn)題，可以推廣應(yīng)用，例如例一，但是總有些大材小用的感覺(jué)。一方面，在線段樹上需要設(shè)立過(guò)多的指針來(lái)指向左子樹和右子樹；另一方面，結(jié)點(diǎn)用于表示區(qū)間，處理點(diǎn)的時(shí)候，不需要保留這樣的區(qū)間。線段樹上的一個(gè)結(jié)點(diǎn)分裂為兩個(gè)半?yún)^(qū)間的時(shí)候?qū)嶋H上是通過(guò)一個(gè)中間點(diǎn)來(lái)分割的，那么在點(diǎn)的統(tǒng)計(jì)問(wèn)題中，只要保留這樣的分割點(diǎn)就可以了。 構(gòu)造可用于統(tǒng)計(jì)的靜態(tài)二叉排序樹 對(duì)于處理點(diǎn)的問(wèn)題，只要建立一棵二叉排序樹，使得要處理 的點(diǎn)在這棵樹上都能夠找到相應(yīng)的節(jié)點(diǎn)。同時(shí)由二叉樹的性質(zhì)：左子樹上的所有點(diǎn)的值都比根小，右子樹上的所有的點(diǎn)的值都比根大，我們利用這一點(diǎn)把線段樹的優(yōu)點(diǎn)繼承過(guò)來(lái)。首先要對(duì)所有要處理的點(diǎn)建立一棵可用以靜態(tài)統(tǒng)計(jì)的二叉排序樹作為模板。例如對(duì)于集合 {3， 4， 5， 8， 19， 23， 6}，可以建立一棵包含 7 個(gè)點(diǎn)的二叉排序統(tǒng)計(jì)樹： 6 3 8 4 5 23 19 注意到每個(gè)節(jié)點(diǎn)上所標(biāo)的就是它對(duì)應(yīng)的點(diǎn)值。 建立二叉統(tǒng)計(jì)樹的第一步，是把所有要處理的點(diǎn)坐標(biāo)離散化，形成一個(gè)排序的映射，例如我們稱為 X 映射，并且 設(shè)其中一共有 n 個(gè)不同的對(duì)象。例如在上例中， X={3， 4， 5， 6， 8， 19， 23}， n=7。 現(xiàn)在要把 X 映射中的點(diǎn)值填入到樹中，使它有上面的構(gòu)造。這里我們選擇靜態(tài)結(jié)構(gòu)作為對(duì)二插樹的支持。將二叉樹的結(jié)點(diǎn)從上到下，從左到右進(jìn)行編號(hào)，并令根結(jié)點(diǎn)的編號(hào)為 1。即上圖中對(duì)應(yīng)的編號(hào)應(yīng)該是： 二分法與統(tǒng)計(jì)問(wèn)題 江蘇淮陰中學(xué) 李睿 10 1 4 3 2 5 7 6 這與靜態(tài)堆的實(shí)現(xiàn)是十分類似的。對(duì)于任何一個(gè)編號(hào)為 i 的結(jié)點(diǎn)，它的左兒子編號(hào)自然為 i*2，右二子編號(hào)為 i*2+1。現(xiàn)在要把 X 的映射填入到數(shù)組 V 中去。V[1..n]應(yīng)該保存相應(yīng)位置上 的點(diǎn)值。 注意到對(duì) V 對(duì)應(yīng)的二叉樹進(jìn)行中序遍歷的結(jié)果就對(duì)應(yīng) X 中的映射，所以可以通過(guò)遞歸的方法建立 V： 這個(gè)過(guò)程即對(duì) V 先序遍歷。 如果對(duì)二叉樹先序遍歷的過(guò)程熟悉，也可以不采用遞歸過(guò)程。只要從先序遍歷的第一個(gè)結(jié)點(diǎn)開(kāi)始，每次找到它的后繼。第一個(gè)結(jié)點(diǎn)顯然是二叉樹最下面一層的最左邊的結(jié)點(diǎn)。如果有 n 個(gè)結(jié)點(diǎn)，首先通過(guò)下面這個(gè)過(guò)程找到第一個(gè)結(jié)點(diǎn)： 然后我們可以通過(guò)下面這個(gè)過(guò)程對(duì) V 賦值： p ← 0 作為 X 映射中的指針 procedure BUILD(ID:integer) ID 是 V 結(jié)點(diǎn) 的下標(biāo) begin if (ID*2≤ n) then BUILD(ID*2)。 p← p+1 V[ID]=X[p] if (ID*2+1≤ n) then BUILD(ID*2+1)。 end 在主程序中調(diào)用 BUILD(1) function first:integer begin level ← 1, tot = 2 while (tot1n) do begin level← level+1 tot← tot*2 end return s div 2 end 二分法與統(tǒng)計(jì)問(wèn)題 江蘇淮陰中學(xué) 李睿 11 從構(gòu)造的方法可以看出，這是一棵近似滿 二叉樹，因此它也是一棵平衡樹，它的深度為 logn。 進(jìn)行統(tǒng)計(jì)的方法分析 在這棵樹中，對(duì)于任何將要處理的一個(gè)點(diǎn)，它具有值 value，我們根據(jù) value很容易在樹中找到相應(yīng)的結(jié)點(diǎn)。例如我們要?jiǎng)討B(tài)維護(hù)點(diǎn)的個(gè)數(shù)，類似例一中提到的，我們?cè)跇涞拿總€(gè)結(jié)點(diǎn)上設(shè)一個(gè) SUM，表示以該結(jié)點(diǎn)為根的二叉樹上的點(diǎn)的總數(shù)。最初 SUM[i]=0。插入一個(gè)點(diǎn)有如下過(guò)程： 我們可以在 logn 時(shí)間內(nèi)動(dòng)態(tài)維護(hù) SUM,其過(guò)程與 value 的查找是同步的。 這個(gè) SUM 的設(shè)立比較普通。有些特殊的設(shè)定，就比較有大的 作用。比如我們?cè)诿總€(gè)結(jié)點(diǎn)上設(shè)一個(gè) LESS,表示值小于等于根結(jié)點(diǎn)值的總數(shù)，即根上的點(diǎn)以及左子樹上的點(diǎn)的總數(shù)。那么插入時(shí)有： procedure BUILD begin now ← first p← 0 for i ← 1 to n do begin p← p+1,V[now]← X[p] if (now*2+1≤ n) then begin now← now*2+1 while (now*2≤ n) now← now*2 end else begin while (now 是奇數(shù) ) now← now div 2 now← now div 2 end end end procedure INSERT(value) begin now ← 1 repeat SUM[now]← SUM[now]+1 if (V[now]=value) break if (V[now]value) now← now*2 else now← now*2+1 until false end 二分法與統(tǒng)計(jì)問(wèn)題 江蘇淮陰中學(xué) 李睿 12 這個(gè)過(guò)程與前一個(gè)大同小異。實(shí)際上 LESS[I]=SUM[I]SUM[I*2+1]。舉這個(gè)例子在于說(shuō)明利用二叉排序樹的結(jié)構(gòu)，是很容易結(jié)合具體的問(wèn)題進(jìn)行變化的。 我們對(duì)其變化，甚至也可以利用來(lái)解決例二。只要將剛才 LESS 的定義作一點(diǎn)變化，令它為根及其左樹上所有點(diǎn)上的權(quán)和。如果要在 a[x]上增加 A。可以很容易得到： 同樣也很方便，另外 如果要求 SUM(1,x)的值，只要根據(jù)這樣一個(gè)函數(shù)： 可以發(fā)現(xiàn)這幾個(gè)過(guò)程基本相似，這種實(shí)現(xiàn)對(duì)例二解決的效率并不亞于第二節(jié)procedure INSERT1(value) begin now ← 1 repeat if (value=V[now]) then LESS[now]← LESS[now]+1 if (V[now]=value) break if (V[now]value) now← now*2 else now← now*2+1 until false end procedure INSERT2(x,A) begin now ← 1 repeat if (x=V[now]) then LESS[now]← LESS[now]+A if (V[now]=x) break if (V[now]x) now← now*2 else now← now*2+1 until false end function SUM(x):longint begin ans ← 0 now ← 1 repeat if (V[now]=x) ans← ans+LESS[now] if (V[now]=x) break if (V[now]x) now← now*2 else now← now*2+1 until false return ans end 二分法與統(tǒng)計(jì)問(wèn)題 江蘇淮陰中學(xué) 李睿 13 中介紹的方法，而且它對(duì)內(nèi)存的消耗也是 1 個(gè)單一的數(shù)組，可以很容易地推廣到二維解決 MOBILES 的問(wèn)題，最后主要的內(nèi)存消耗也是 4Mb 的靜態(tài)數(shù)組，而它的效率也是較高的。用二叉排序樹來(lái)實(shí)現(xiàn)，其思路和線段樹是一樣的，因?yàn)槎弑举|(zhì)上是相似的。 這種方法經(jīng)常被應(yīng)用到離散化的統(tǒng)計(jì)問(wèn)題中，尤其是平面問(wèn)題的統(tǒng)計(jì)。 一個(gè)較復(fù)雜的例子 [例三 ]采礦 (KOP) 金礦的老 師傅年底要退休了。經(jīng)理為了獎(jiǎng)賞他的盡職盡責(zé)的工作，決定送他一塊長(zhǎng)方形地。長(zhǎng)度為 S，寬度為 W。老師傅可以自己選擇這塊地。顯然其中包含的采金點(diǎn)越多越好。你的任務(wù)就是計(jì)算最多能得到多少個(gè)采金點(diǎn)。如果一個(gè)采金點(diǎn)的位置在長(zhǎng)方形的邊上，它也應(yīng)當(dāng)被計(jì)算在內(nèi)。 任務(wù)： 讀入采金點(diǎn)的位置。計(jì)算最大的價(jià)值。 輸入： 文件 的第一行是 S 和 W， (1=s,w=10 000)。他們分別平行于 OX 坐標(biāo)和 OY 坐標(biāo)，指明了地域的尺寸。接下來(lái)一行是整數(shù) n (1=n=15 000)，表示采金點(diǎn)的總數(shù)。然后是 n 行，每行兩個(gè)整 數(shù)，給出了一個(gè)采金點(diǎn)的坐標(biāo)。坐標(biāo)范圍是 (30 000=x,y=30 000)。 輸出： 一個(gè)整數(shù)，最多的采金點(diǎn)數(shù)。 樣例輸入 1 2 12 0 0 1 1 2 2 3 3 4 5 5 5 4 2 1 4 0 5 5 0 2 3 3 2 樣例輸出 4 分析： 題目中的樣例實(shí)際上對(duì)應(yīng)了下圖： 二分法與統(tǒng)計(jì)問(wèn)題 江蘇淮陰中學(xué) 李睿 14