【正文】 過程?？梢酝ㄟ^下面這個函數(shù)來完成一個點(diǎn)事件的插入，并且維護(hù) SUM 和 MAXSUM 的特性。 得到大致算法如下： 將所有的點(diǎn)事件映射到 y 坐標(biāo)中，最多有 n=15000 個點(diǎn)，所以可能有 30000個不同的坐標(biāo)，將這些值建立一棵可用以統(tǒng)計(jì)的二叉排序樹，即 BUILD。進(jìn)一步考慮對縱坐標(biāo)的特殊處理： 對于每一種坐標(biāo) y，建立成兩個點(diǎn)事件 (y,+1),(y+w+1,1) 例如將前面的點(diǎn)標(biāo)成 (1,+1),(4,1),(3,+1),(6,1),(5,+1),(8,1),(9,+1),(12,1), (9,+1),(12,1), 一共是 10 個點(diǎn)事件，再將他們按照 y 的坐標(biāo)排序，得(1,+1),(3,+1),(4,1), (5,+1)， (6,1), (8,1), (9,+1), (9,+1),(12,1), (12,1)我們把后面的標(biāo)號反映在一個 y 坐標(biāo)的映射上，然后從低到高求和，如下圖： 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 15 + 1 + 1 – 1 + 1 1 1 + 2 2 ∑ 1 2 1 2 1 0 2 0 注意坐標(biāo)下的求和，這些和中最大的一個就是該帶狀區(qū)域中一個包含最多點(diǎn)數(shù)的矩形?？梢园l(fā)現(xiàn)，每個點(diǎn)進(jìn)出要處理的帶狀區(qū)域各一次。然后再統(tǒng)計(jì)這一個帶狀區(qū)域中的每一個寬 度為 W 的矩形。坐標(biāo)范圍是 (30 000=x,y=30 000)。 輸入： 文件 的第一行是 S 和 W， (1=s,w=10 000)。你的任務(wù)就是計(jì)算最多能得到多少個采金點(diǎn)。經(jīng)理為了獎賞他的盡職盡責(zé)的工作，決定送他一塊長方形地。可以很容易得到： 同樣也很方便，另外 如果要求 SUM(1,x)的值，只要根據(jù)這樣一個函數(shù)： 可以發(fā)現(xiàn)這幾個過程基本相似，這種實(shí)現(xiàn)對例二解決的效率并不亞于第二節(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ì)問題 江蘇淮陰中學(xué) 李睿 13 中介紹的方法，而且它對內(nèi)存的消耗也是 1 個單一的數(shù)組，可以很容易地推廣到二維解決 MOBILES 的問題，最后主要的內(nèi)存消耗也是 4Mb 的靜態(tài)數(shù)組，而它的效率也是較高的。舉這個例子在于說明利用二叉排序樹的結(jié)構(gòu)，是很容易結(jié)合具體的問題進(jìn)行變化的。有些特殊的設(shè)定，就比較有大的 作用。例如我們要動態(tài)維護(hù)點(diǎn)的個數(shù)，類似例一中提到的，我們在樹的每個結(jié)點(diǎn)上設(shè)一個 SUM，表示以該結(jié)點(diǎn)為根的二叉樹上的點(diǎn)的總數(shù)。如果有 n 個結(jié)點(diǎn)，首先通過下面這個過程找到第一個結(jié)點(diǎn)： 然后我們可以通過下面這個過程對 V 賦值： p ← 0 作為 X 映射中的指針 procedure BUILD(ID:integer) ID 是 V 結(jié)點(diǎn) 的下標(biāo) begin if (ID*2≤ n) then BUILD(ID*2)。 注意到對 V 對應(yīng)的二叉樹進(jìn)行中序遍歷的結(jié)果就對應(yīng) X 中的映射，所以可以通過遞歸的方法建立 V： 這個過程即對 V 先序遍歷。即上圖中對應(yīng)的編號應(yīng)該是： 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 10 1 4 3 2 5 7 6 這與靜態(tài)堆的實(shí)現(xiàn)是十分類似的。例如在上例中， X={3， 4， 5， 6， 8， 19， 23}， n=7。同時由二叉樹的性質(zhì)：左子樹上的所有點(diǎn)的值都比根小，右子樹上的所有的點(diǎn)的值都比根大，我們利用這一點(diǎn)把線段樹的優(yōu)點(diǎn)繼承過來。另一方面，前面也說明過，線段樹的建立方式非常適用于處理線段，對于點(diǎn)的問題，可以推廣應(yīng)用，例如例一，但是總有些大材小用的感覺。仔細(xì)研究過線段樹會知道它能夠支持很多特殊的統(tǒng)計(jì)問題。用本節(jié)介紹的方法，只需要 4Mb 的 C 數(shù)組以及一些零散的變量。可以發(fā)現(xiàn)，經(jīng)過這次推廣，算法的復(fù)雜度為 log2n。注意我們所需要消耗的內(nèi)存僅是一個很單一的數(shù)組，它的構(gòu)造比起線段樹來說要簡單得多（很明顯，這個問題也可以用前面的線段樹結(jié)構(gòu)來解決）。所以一次提問需要的操作次數(shù)為 2logn。那么如何根據(jù) C 的值來求一個 sum（ 1,x)呢？容易得到如下過程。在很多情況下對 a[x]進(jìn)行修改時，涉及到的 P 序列長度要遠(yuǎn)小于 logn。 C[Y]是不可能包含 a[x]的。我們已經(jīng)借用 C 來表示 a 的一些和，所以這兩個問題的解決，就是要更新 C 的相關(guān)量。有無簡單的操作可以得到這個結(jié)果呢？我們可以利用這樣一個計(jì)算式子： 2^k=x and (x xor (x1)) 這里巧妙地利用了位操作，只需要進(jìn)行兩步的簡單計(jì)算?，F(xiàn)在要求你能對每個提問作出正確的回答。 此種數(shù)據(jù)結(jié)構(gòu)的維護(hù) 也許你已經(jīng)注意到了，對 C 的定義非常奇特，似乎看不出什么規(guī)律。 對于序列 a[]，我們設(shè)一個數(shù)組 C， 其中 ][]1^2[][ iakiaiC ????? ?（ k 為i 在二進(jìn)制下末尾 0 的個數(shù)）。并且修改元素的值的方法也類似。這個問題與 MOBILES 問題實(shí)際上提法是一樣的。但是面對可能將要處理的規(guī)模，我們卻望而卻步了，因?yàn)楹唵蔚膶?shí)現(xiàn)效率實(shí)在太低了。由于線段樹變小了，所以樹的深度只有 14左右，整個問題的復(fù)雜度極限為 N*14+n*14*100*2，對于問題的規(guī)模來說，仍然是高效率的。由于我們對 1000000 種面額都進(jìn)行了保存，所以線段樹顯得比較龐大。它的插入，刪除，查找路徑是相 同的，長度為樹的深度，即 log1000000=20。如何找到最大的帳單呢？顯然，對于一個樹 v來說，如果 C[LSON[v]]0,那么樹 v 中的最小值一定在它的左子樹上。保證每天總可以找到兩張帳單。 [例一 ]PROMOTION 問題（ POI0015） 問題大意： 一位顧客要進(jìn)行 n（ 1≤ n≤ 5000）天的購物，每天他會有一些帳單。同時插入每個點(diǎn)的時候都必須深入到葉結(jié)點(diǎn)，因此一般來說都要有 logn 的復(fù)雜度。即不存在 (a,a+1)這樣的區(qū)間，每個點(diǎn)分裂為 a 和 a+1。 if d? ?2/])[][( vEvB ? then DELETE(c,d。而點(diǎn)也是可以理解為特殊的區(qū)間的。比如說處理一組矩形問題時，可以用來求矩形并圖后的輪廓周長和面積等等，比普通的離散化效率更高。這在許多動態(tài)維護(hù)的題目中是非常有用的，它使得每次操作的維護(hù) 費(fèi)用只有 logn。 線段樹的作用主要體現(xiàn)在 可以動態(tài)維護(hù)一些特征，例如說要得到線段樹上線段并集的長度，增加一個數(shù)據(jù)域 M[v]，討論： 如果 C[v]0,M[v] = E[v]B[v]。插入?yún)^(qū)間的時間復(fù)雜度是 O(logn)。 end 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 4 基數(shù)（即覆蓋線段數(shù)）加 1。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。 這因題而異，同時又往往是解題的靈魂。 C[v]仍然用來作計(jì)數(shù)器。 End。用數(shù)組 B[]， E[]， C[]， LSON[]，Type Tnode=^Treenode。線段樹是平衡樹，它的深度為 lg(ba)。下圖顯示了一個能夠表示[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é)點(diǎn)表示了一個區(qū)間 [a,b]。 線段樹的構(gòu)造思想 線段樹處理的 是一定的固定線段，或者說這些線段是可以對應(yīng)于有限個固定端點(diǎn)的。接著將會介紹一種與線段樹有所不同的構(gòu)造模式，它的形式是二叉排序樹，將會發(fā)現(xiàn)這種方法是十分靈活的，進(jìn)一步，我們將略去對它的構(gòu)造，在有序表中進(jìn)行虛實(shí)現(xiàn)。為了解決這種困難，在統(tǒng)計(jì)中需要借助一些特殊的工具，如比較有效的數(shù)據(jù)結(jié)構(gòu)來幫助解決。這些問題的特點(diǎn)是，問題表現(xiàn)得比較簡單，一般是對一定范圍內(nèi)的數(shù)據(jù)進(jìn)行處理，用基本的方法就可以實(shí)現(xiàn)，但是實(shí)際處理的規(guī)模卻比較大，粗劣的算法只能導(dǎo)致低效。然后將介紹