二分法與統(tǒng)計問題江蘇淮陰中學(xué)李睿

1、二分法 與統(tǒng)計問題 江蘇省淮陰中學(xué) 李睿,簡介,一定范圍內(nèi)計數(shù)問題特點：1 描述簡單2 要求對數(shù)據(jù)動態(tài)維護，動態(tài)計算解決手段：特殊的統(tǒng)計模式和結(jié)構(gòu),線段樹,動態(tài)處理可以映射在一個坐標(biāo)軸上的一些固定線段，例如求并區(qū)間的總長度，或者并區(qū)間的個數(shù)等等。 優(yōu)點：隨時插入一個區(qū)間或刪除一個已有區(qū)間，并同時用低耗費維護需要的性質(zhì)。,線段樹-構(gòu)造思想,下圖顯示了一個能夠

2、表示[1，10]的線段樹：,,線段樹-動態(tài)數(shù)據(jù)結(jié)構(gòu),TypeTnode=^Treenode;Treenode=recordB,E:integer; Count:integer;LeftChild,Rightchild:Tnode;End; 其中B和E表示了該區(qū)間為[B,E]；Count為一個計數(shù)器，通常記錄覆蓋到此區(qū)間的線段的個數(shù)。LeftChild和RightChild分別是左右子樹的根。,線

3、段樹-靜態(tài)數(shù)據(jù)結(jié)構(gòu),用數(shù)組B[]，E[]，C[]，LSON[]，RSON[]。設(shè)一棵線段樹的根為v。那么B[v],E[v]就是它所表示區(qū)間的界。C[v]用來作計數(shù)器。LSON[v]，RSON[v]分別表示了它的左兒子和右兒子的根編號。,線段樹-建樹,從根對應(yīng)的區(qū)間[a，b]出發(fā)，每次分成兩個部分，分別建立對應(yīng)的左右子樹，直到面臨一個初等區(qū)間[x,x+1]。,線段樹-插入刪除線段,將區(qū)間[c,d]插入線段樹T(a,b),并設(shè)T(a,b)的

4、根編號為v procedure INSERT(c,d;v)Begin mid=(B[v]+E[v]) div 2;if c≤B[v] and E[v]≤d then C[v] ← C[v]+1else if cmid then INSERT(c,d;RSON[v]);end,線段樹-一個特殊性質(zhì)舉例,要得到線段樹上線段并集的長度，增加一個數(shù)據(jù)域 M[v]，討論： C[v]>0,M[v] = E[v]-

5、B[v];C[v]=0 且v是葉子結(jié)點，M[v]=0；C[v]=0 且v是內(nèi)部結(jié)點，M[v]=M[LSON[v]]+M[RSON[v]];,線段樹-變形，對點統(tǒng)計,,[例一],一位顧客要進行n（1≤n≤5000）天的購物，每天他會有一些帳單。每天購物以后，他從以前的所有帳單中挑出兩張帳單，分別是面額最大的和面額最小的一張，并把這兩張帳單從記錄中去掉。剩下的帳單留在以后繼續(xù)統(tǒng)計。輸入的數(shù)據(jù)保證，所有n天的帳單總數(shù)不超過1000000，

6、并且每份帳單的面額值是1到1000000之間的整數(shù)。保證每天總可以找到兩張帳單。,建立點線段樹，范圍是[1，1000000]，即每種面額的帳單設(shè)為一個葉結(jié)點。 如果C[LSON[v]]>0,那么樹v中的最小值一定在它的左子樹上。如果C[RSON[v]]>0，它的最大值在右子樹上；,一種靜態(tài)統(tǒng)計方法,[例二]IOI2001 MOBILES ：在一個N*N的方格中，開始每個格子里的數(shù)都是0?，F(xiàn)在動態(tài)地提出一些問題和修改：

7、提問的形式是求某一個特定的子矩陣(x1,y1)-(x2,y2)中所有元素的和；修改的規(guī)則是指定某一個格子(x,y)，在(x,y)中的格子元素上加上或者減去一個特定的值A(chǔ)?，F(xiàn)在要求你能對每個提問作出正確的回答。1≤N≤1024,提問和修改的總數(shù)可能達到60000條。,一維序列求和,設(shè)序列的元素存儲在a[]中，a的下標(biāo)是1..n的正整數(shù)，需要動態(tài)地更新某個a[x]的值，同時要求出a[x1]到a[y1]這一段所有元素的和。,對于序列a[1..

8、n]，我們設(shè)一個數(shù)組C[1..n]，C[i]=a[i-2k+1]+…+a[i],其中k為i在二進制下末尾0的個數(shù) 1001010110010000 k =4 計算C[x]對應(yīng)的2k LOWBIT（x）2k =x and (x xor (x-1)),修改一個a[x]的值 與哪些C相關(guān)？ 例如x=76=(1001010)2，從形式上進行觀察，可以得到： p1= 1001010 p2= 1001100 p

9、3= 1010000 p4= 1100000 p5=10000000修改C[p1],C[p2],…,,procedure UPDATA(x,A)begin p←x while (p<=n) do begin C[p]←C[p]+A p←p+LOWBIT(p) endend 維護的費用：logn,求a[1]-a[x]的和function

10、SUM(x)beginans ← 0p ← xwhile (p>0) do begin ans←ans+C[p] p←p-LOWBIT(p) endreturn ansend,C[p]=a[p- 2k +1]+^+a[p]下一個p=x- 2k,推廣為原來的二維問題，把C構(gòu)造成 C[x，y]，其每一維定義與原來相同。推廣后算法：兩層嵌套，一次維護費用

11、為O(log2n),集合{3，4，5，8，19，6},,靜態(tài)二叉排序樹實現(xiàn),構(gòu)造過程1 遞歸：,建立所有點坐標(biāo)的映射Xp ← 0 作為X映射中的指針procedure BUILD(ID:integer) beginif (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在

12、主程序中調(diào)用BUILD(1),構(gòu)造過程2 非遞歸：,方法，依次找出當(dāng)前點的后繼點的下標(biāo)第一個點first一定為最下層最左邊的一個位置,若n個點有L層,則first=2 L-1若當(dāng)前的點位置為now： 如果它有右兒子，即now*2+1<=n,則下一 個位置是右子樹最左下的點 如果沒有右兒子，當(dāng)now是奇數(shù)時，將now除以2，直到now是偶數(shù)，最后再將now除以2。,插入一個點x,procedure INSERT(

13、x)beginnow ← 1repeat SUM[now]←SUM[now]+1 if (V[now]=x) break if (V[now]>x) now←now*2 else now←now*2+1until falseEnd其中SUM是記錄一棵子樹上結(jié)點總數(shù)刪除 的方法是類似的,怎樣解決例二,procedure INSERT2(x,A)beginnow ← 1repeat

14、 if (xx) now←now*2 else now←now*2+1until falseendLESS為根及其左子樹上所有點位置的權(quán)和,求a[1..x]的元素和function SUM(x):longintbeginans ← 0now ←1repeat if (V[now]x) now←now*2 else now←now*2+1until false retu

15、rn ansend,[例三]采礦(KOP),金礦的老師傅年底要退休了。經(jīng)理為了獎賞他的盡職盡責(zé)的工作，決定送他一塊長方形地。長度為S，寬度為W。老師傅可以自己選擇這塊地。顯然其中包含的采金點越多越好。你的任務(wù)就是計算最多能得到多少個采金點。如果一個采金點的位置在長方形的邊上，它也應(yīng)當(dāng)被計算在內(nèi)。任務(wù)：讀入采金點的位置。計算最大的價值。輸入：文件KOP.IN的第一行是S和W，(1<=s,w<=10 00

16、0);他們分別平行于OX坐標(biāo)和OY坐標(biāo)，指明了地域的尺寸。接下來一行是整數(shù)n (1<=n<=15 000)，表示采金點的總數(shù)。然后是n行，每行兩個整數(shù)，給出了一個采金點的坐標(biāo)。坐標(biāo)范圍是(-30 000<=x,y<=30 000)。輸出：一個整數(shù)，最多的采金點數(shù)。,樣例圖示,,初步，對X離散化后，圖示,,對于每一種坐標(biāo)y，建立成兩個點事件(y,+1),(y+w+1,-1)，例

17、如在一個帶狀區(qū)域內(nèi)有5個點的縱坐標(biāo)分別是{5，3，9，1，9}，w=2 ，標(biāo)成(1,+1),(4,-1),(3,+1),(6,-1),(5,+1),(8,-1),(9,+1),(12,-1), (9,+1),(12,-1),再將他們按照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坐

18、標(biāo)的映射上，然后從低到高求和,坐標(biāo)下的求和，這些和中最大的一個就是該帶狀區(qū)域中一個包含最多點數(shù)的矩形 在插入或者刪除一個點事件之后，能夠維持坐標(biāo)下∑的值；能夠在很短時間內(nèi)得到∑中最大的一個值。,,,實現(xiàn)：,SUM[now]對應(yīng)子樹上所有+1，-1標(biāo)號的和。實現(xiàn)極簡單MAXSUM[now]，子樹上和最大的一個前綴的值。MAXSUM[1]是一種狀態(tài)下得到最優(yōu)解。如何維護？MAXSUM[]有哪幾種可能？1 最大值在左樹上；2 最大值

19、正好包含根結(jié)點；3 最大值在右樹上。,自下而上維護樹的特性,找到當(dāng)前坐標(biāo)對應(yīng)點序號now,修正標(biāo)號為kRepeat SUM[now]←SUM[now]+k MAXSUM[now]←Max{ MAXSUM[now*2],SUM[now]-SUM[now*2+1],SUM[now]-SUM[now*2+1]+MAXSUM[now*2+1]} n

20、ow ← now div 2until now = 0,二分法虛擬實現(xiàn)樹,二叉樹使用之前必須構(gòu)造出一個空的二叉樹 對于任何一個有序表，在對其進行二分查找時，實際上就等于在一個二叉樹上進行查找,對于一個表{1，3，4，8，9}的二分查找，等價于在如下圖的二叉排序樹上進行查找：,,舉插入結(jié)點的例子，來說明這種虛實現(xiàn)的方法，設(shè)LESS表示根及其左樹上結(jié)點的個數(shù)：,procedure INSERT(x)beginl←1,r←nwh

21、ile (l<=r) do begin m=(l+r) div 2 if x<=V[m] LESS[m]←LESS[m]+1if x =V[m] breakif x<V[m] then r ←m –1 else l←m+1 endend,[例四]最長下

22、降序列,給定一個整數(shù)序列a，求最長下降序列的長度。,,O（n2),對P進行特殊的限制，即，在所有等價的決策j中，P選擇a[j]最大的那一個 在處理完a[1..x-1]之后，對于所有長度為M[x]-1的下降序列，P[x]的決策只跟其中末尾最大的一個有關(guān)。 用另外一個動態(tài)變化的數(shù)組b，當(dāng)我們計算完了a[x]之后，a[1..x]中得到的所有下降序列按照長度分為L類，每一類中只需要一個作為代表，這個代表在這個等價類中末尾的數(shù)最大，我們把它記

23、為b[j],1≤j≤L。 處理當(dāng)前的一個數(shù)a[x]，我們無需和前面的a[j]（1≤j≤x-1）作比較，只需要和b[j]（1≤j≤L)進行比較。,首先，如果a[x]=b[1]，這時a[x] 僅能構(gòu)成長度為1的下降序列，同時它又必然是最大的，所以它作為b[1]的代表,b[1]=a[x]。 如果前面的情況都不存在，我們肯定可以找到一個j,2≤j≤L,有b[j-1]>a[x],b[j]≤a[x]，這時分析，a[x]必然接在b[j-1]

24、后面，行成一個新的長度為j的序列。,這幾種情況實際上都可以歸結(jié)為：處理a[x]，令b[L+1]為無窮小，從左到右找到第一個位置j，使b[j]≤a[x],然后則只要將b[j]=a[x],如果j=L+1,則L同時增加。x處以前對應(yīng)的最長下降序列長度為M[x]=j。 L ←0for x←1 to n do beginb[L+1]←無窮小 j←1 while (b[j]>

25、a[x]) j←j+1 b[j]←a[x] if j>L then L←j end,更改成： j←1,k←L while (j≤k) do begin m ← (j+k) div 2 if b[m]>a[i] j←