【正文】 結(jié)合一定的數(shù)據(jù)結(jié)構(gòu)，使得統(tǒng)計(jì)的過程存在一定的模式，以到達(dá)提高效率的目的。二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 1 二分法與統(tǒng)計(jì)問題 淮陰中學(xué) 李睿 [關(guān)鍵字 ] 線段樹 二叉樹 二分法 [摘要 ] 我們經(jīng)常遇到統(tǒng)計(jì)的問題。首先簡(jiǎn)要介紹線段樹的基礎(chǔ)，它是一種很適合計(jì)算幾何的數(shù)據(jù)結(jié)構(gòu)，同時(shí)也可以擴(kuò) 充到其他方面。由于線段是可以互相覆蓋的，有時(shí)需要?jiǎng)討B(tài)地取線段的并，例如取得并區(qū)間的總長(zhǎng)度，或者并區(qū)間的個(gè)數(shù)等等。那么對(duì)于任何一個(gè)要處理的線段（區(qū)間） [a,b]來說，總可以找到相應(yīng)的 i,j，使得 ti=a,tj=b,1≤ i≤ j≤ N。對(duì)于每一個(gè)內(nèi)部結(jié)點(diǎn) ba1，設(shè)根為 [a,b]的線段樹為 T(a,b),則進(jìn)一步將此線段樹分為左子樹 T(a,(a+b)/2),以及右子樹T((a+b)/2,b),直到分裂為一個(gè)初等區(qū)間為止。 LeftChild 和 RightChild 分別是左右子樹的根。 Count:integer。設(shè)一棵線段樹的根為 v。 注意，這只是線段樹的基本結(jié)構(gòu)。 建立線段樹（ a,b） : 設(shè)一個(gè)全局變量 n，來記錄一共用到了多少結(jié)點(diǎn)。 if d? ?2/])[][( vEvB ? then INSERT(c,d。否則，在左樹和右樹上都要進(jìn)行插入。這樣才能保證線段樹的維護(hù)是正確的。 只要每次插入或刪除線段區(qū)間時(shí)，在訪問到的結(jié)點(diǎn)上更新 M 的值，不妨稱之為 UPDATA，就可以在插入和刪除的同時(shí)維持好 M。這里不再深入列舉。這里不作深入。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。 end 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 5 可以轉(zhuǎn)化為記錄點(diǎn)的結(jié)構(gòu)。如下圖： [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]這時(shí)就可以用來計(jì)算落在定區(qū)間內(nèi)的點(diǎn)個(gè)數(shù)了。另一方面由于它實(shí)際上是排序二叉樹，所以容易找出最大和 最小來。剩下的帳單留在以后繼續(xù)統(tǒng)計(jì)。不妨建立前面所說的線段樹，這棵線段樹的范圍是 [1， 1000000]，即我們把所有面額的帳單設(shè)為一個(gè)點(diǎn)。所以線段樹的計(jì)數(shù)其實(shí)為我們提供了線索。這比普通排序的實(shí)現(xiàn)要簡(jiǎn)單得多。由于 V 的范圍是 [1..1000000]，所以線段樹中 有 10000 個(gè)點(diǎn)。同時(shí)實(shí)際上也提醒了我們對(duì)線段樹應(yīng)該加以靈活的應(yīng)用。問題是二維的，注意到降格的思想，我們對(duì)一維的問題進(jìn)行討論，然后只要稍微進(jìn)行推廣。因?yàn)槲覀冎烙?jì)算a[x1]到 a[y1]這一段所有元素的和，可以用 sum(1,y1)sum(1,x11)，即用部分和求差的技術(shù)。我們希望再構(gòu)造一種特殊的形式，因?yàn)樗膶?shí)現(xiàn)比線段樹要來得簡(jiǎn)單得多。那么在這個(gè)用來記錄的數(shù)組中， C[K]到底是怎樣的表現(xiàn)呢？舉一個(gè)例子，C[56]，將 56 寫成二進(jìn)制的形式為 111000，那么 C[56]表示的最小的數(shù)是 110001，即 49， C[56]表示的是 a[49]到 a[56]的所有元素的和。 在一個(gè) N*N 的方格中，開始每個(gè)格子里的數(shù)都是 0。 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 7 如何計(jì)算 C[x]對(duì)應(yīng)的 2^k？ k 為 x 在二進(jìn)制數(shù)下末尾 0 的個(gè)數(shù)。 在下面的敘述中我們把這個(gè)計(jì)算式子用函數(shù) LOWBIT(x)來表示。這一串?dāng)?shù)到底有什么規(guī)律呢 ?可以發(fā) 現(xiàn)： )(111PiL O W B I TPiPiPiPixP?????? 從觀察上容易看出這是正確的，從理論上也容易證明它是正確的。所以 P 序列所含的數(shù)最多為 lgn，這里 n 是 a 表的長(zhǎng)度，或者說是 C 表的長(zhǎng)度。修改一個(gè)元素 a[x]，使其加上 A，變成 a[x]+A，可以有如下的過程： procedure UPDATA(x,A) begin p← x while (p=n) do begin C[p]← C[p]+A p← p+LOWBIT(p) end end 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 8 計(jì)算一個(gè)提問 [x,y]的結(jié)果： 我們下面來解決求部分和的問題。同時(shí)，它的復(fù)雜度顯然是 lgn。這個(gè)結(jié)果是非常令人驚喜和滿意的。如何推廣呢？注意在 MOBILES 問題中我們要修改的是 a[x,y]的值，那么模仿一維問題的解法，可以將 C[x,y]定義為： yiyL O W B I TyxixL O W B I TxjiayxC ????????? ? 1)(,1)(],[],[ 其中 其具體的修改和求和過程實(shí)際上是一維過程的嵌套。 可以嘗試類似地建立二維線段樹來解決這個(gè)問題，它的復(fù)雜性要比這種靜態(tài)的方法高得多。 這種特殊的統(tǒng)計(jì)方法對(duì)于本題很有優(yōu)勢(shì)，同時(shí)它推廣到高維時(shí)比較方便，是function SUM(x) begin ans ← 0 p ← x while (p0) do begin ans← ans+C[p] p← pLOWBIT(p) end return ans end 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 9 前面所涉及的線段樹不可比的。下面再介紹一些其他的實(shí)現(xiàn)方法。線段樹上的一個(gè)結(jié)點(diǎn)分裂為兩個(gè)半?yún)^(qū)間的時(shí)候?qū)嶋H上是通過一個(gè)中間點(diǎn)來分割的，那么在點(diǎn)的統(tǒng)計(jì)問題中，只要保留這樣的分割點(diǎn)就可以了。例如對(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ài)結(jié)構(gòu)作為對(duì)二插樹的支持。現(xiàn)在要把 X 的映射填入到數(shù)組 V 中去。只要從先序遍歷的第一個(gè)結(jié)點(diǎn)開始，每次找到它的后繼。 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ì)問題 江蘇淮陰中學(xué) 李睿 11 從構(gòu)造的方法可以看出，這是一棵近似滿 二叉樹，因此它也是一棵平衡樹，它的深度為 logn。插入一個(gè)點(diǎn)有如下過程： 我們可以在 logn 時(shí)間內(nèi)動(dòng)態(tài)維護(hù) SUM,其過程與 value 的查找是同步的。那么插入時(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ì)問題 江蘇淮陰中學(xué) 李睿 12 這個(gè)過程與前一個(gè)大同小異。只要將剛才 LESS 的定義作一點(diǎn)變化，令它為根及其左樹上所有點(diǎn)上的權(quán)和。 這種方法經(jīng)常被應(yīng)用到離散化的統(tǒng)計(jì)問題中，尤其是平面問題的統(tǒng)計(jì)。老師傅可以自己選擇這塊地。 任務(wù)： 讀入采金點(diǎn)的位置。接下來一行是整數(shù) n (1=n=15 000)，表示采金點(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ì)問題 江蘇淮陰中學(xué) 李睿 14 這是一個(gè)針對(duì)點(diǎn)進(jìn)行掃描的問題。 L2 在 L1 前面動(dòng)，通過調(diào)整，使得 L1 到 L2 的距離不大于 S。例如在一個(gè)帶狀區(qū)域內(nèi)有 5 個(gè)點(diǎn)的縱坐標(biāo)分別是 {5， 3， 9， 1， 9}， w=2，很自然地，考慮將這幾個(gè)坐標(biāo)排序成 {1， 3，5， 9， 9}，然后可以通過類似 橫坐標(biāo)的掃描方法來求得寬度為 w 的矩形。