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

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

2、表示[1，10]的線段樹：,,線段樹-動(dòng)態(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為一個(gè)計(jì)數(shù)器，通常記錄覆蓋到此區(qū)間的線段的個(gè)數(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]用來作計(jì)數(shù)器。LSON[v]，RSON[v]分別表示了它的左兒子和右兒子的根編號(hào)。,線段樹-建樹,從根對(duì)應(yīng)的區(qū)間[a，b]出發(fā)，每次分成兩個(gè)部分，分別建立對(duì)應(yīng)的左右子樹，直到面臨一個(gè)初等區(qū)間[x,x+1]。,線段樹-插入刪除線段,將區(qū)間[c,d]插入線段樹T(a,b),并設(shè)T(a,b)的

4、根編號(hào)為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,線段樹-一個(gè)特殊性質(zhì)舉例,要得到線段樹上線段并集的長(zhǎng)度，增加一個(gè)數(shù)據(jù)域 M[v]，討論： C[v]>0,M[v] = E[v]-

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

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

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

8、n]，我們?cè)O(shè)一個(gè)數(shù)組C[1..n]，C[i]=a[i-2k+1]+…+a[i],其中k為i在二進(jìn)制下末尾0的個(gè)數(shù) 1001010110010000 k =4 計(jì)算C[x]對(duì)應(yīng)的2k LOWBIT（x）2k =x and (x xor (x-1)),修改一個(gè)a[x]的值 與哪些C相關(guān)？ 例如x=76=(1001010)2，從形式上進(jìn)行觀察，可以得到： 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 維護(hù)的費(fèi)用：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]下一個(gè)p=x- 2k,推廣為原來的二維問題，把C構(gòu)造成 C[x，y]，其每一維定義與原來相同。推廣后算法：兩層嵌套，一次維護(hù)費(fèi)用

11、為O(log2n),集合{3，4，5，8，19，6},,靜態(tài)二叉排序樹實(shí)現(xiàn),構(gòu)造過程1 遞歸：,建立所有點(diǎn)坐標(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)前點(diǎn)的后繼點(diǎn)的下標(biāo)第一個(gè)點(diǎn)first一定為最下層最左邊的一個(gè)位置,若n個(gè)點(diǎn)有L層,則first=2 L-1若當(dāng)前的點(diǎn)位置為now： 如果它有右兒子，即now*2+1<=n,則下一 個(gè)位置是右子樹最左下的點(diǎn) 如果沒有右兒子，當(dāng)now是奇數(shù)時(shí)，將now除以2，直到now是偶數(shù)，最后再將now除以2。,插入一個(gè)點(diǎn)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é)點(diǎn)總數(shù)刪除 的方法是類似的,怎樣解決例二,procedure INSERT2(x,A)beginnow ← 1repeat

14、 if (xx) now←now*2 else now←now*2+1until falseendLESS為根及其左子樹上所有點(diǎn)位置的權(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)理為了獎(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à)值。輸入：文件KOP.IN的第一行是S和W，(1<=s,w<=10 00

16、0);他們分別平行于OX坐標(biāo)和OY坐標(biāo)，指明了地域的尺寸。接下來一行是整數(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ù)。,樣例圖示,,初步，對(duì)X離散化后，圖示,,對(duì)于每一種坐標(biāo)y，建立成兩個(gè)點(diǎn)事件(y,+1),(y+w+1,-1)，例

17、如在一個(gè)帶狀區(qū)域內(nèi)有5個(gè)點(diǎn)的縱坐標(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)號(hào)反映在一個(gè)y坐

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

19、正好包含根結(jié)點(diǎn)；3 最大值在右樹上。,自下而上維護(hù)樹的特性,找到當(dāng)前坐標(biāo)對(duì)應(yīng)點(diǎn)序號(hào)now,修正標(biāo)號(hà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,二分法虛擬實(shí)現(xiàn)樹,二叉樹使用之前必須構(gòu)造出一個(gè)空的二叉樹 對(duì)于任何一個(gè)有序表，在對(duì)其進(jìn)行二分查找時(shí)，實(shí)際上就等于在一個(gè)二叉樹上進(jìn)行查找,對(duì)于一個(gè)表{1，3，4，8，9}的二分查找，等價(jià)于在如下圖的二叉排序樹上進(jìn)行查找：,,舉插入結(jié)點(diǎn)的例子，來說明這種虛實(shí)現(xiàn)的方法，設(shè)LESS表示根及其左樹上結(jié)點(diǎn)的個(gè)數(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,[例四]最長(zhǎng)下

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

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

24、后面，行成一個(gè)新的長(zhǎng)度為j的序列。,這幾種情況實(shí)際上都可以歸結(jié)為：處理a[x]，令b[L+1]為無窮小，從左到右找到第一個(gè)位置j，使b[j]≤a[x],然后則只要將b[j]=a[x],如果j=L+1,則L同時(shí)增加。x處以前對(duì)應(yīng)的最長(zhǎng)下降序列長(zhǎ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←