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