算法合集之二分法統(tǒng)計問題

算法合集之二分法統(tǒng)計問題第一頁，共四十二頁，編輯于2023年，星期三簡介一定范圍內(nèi)計數(shù)問題特點：1描述簡單2要求對數(shù)據(jù)動態(tài)維護，動態(tài)計算解決手段：特殊的統(tǒng)計模式和結(jié)構(gòu)第二頁，共四十二頁，編輯于2023年，星期三線段樹動態(tài)處理可以映射在一個坐標軸上的一些固定線段，例如求并區(qū)間的總長度，或者并區(qū)間的個數(shù)等等。優(yōu)點：隨時插入一個區(qū)間或刪除一個已有區(qū)間，并同時用低耗費維護需要的性質(zhì)。第三頁，共四十二頁，編輯于2023年，星期三線段樹-構(gòu)造思想下圖顯示了一個能夠表示[1，10]的線段樹：第四頁，共四十二頁，編輯于2023年，星期三線段樹-動態(tài)數(shù)據(jù)結(jié)構(gòu)Type Tnode=^Treenode; Treenode=record

B,E:integer;

Count:integer;

LeftChild,Rightchild:Tnode; End;

其中B和E表示了該區(qū)間為[B,E]；Count為一個計數(shù)器，通常記錄覆蓋到此區(qū)間的線段的個數(shù)。LeftChild和RightChild分別是左右子樹的根。第五頁，共四十二頁，編輯于2023年，星期三線段樹-靜態(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]分別表示了它的左兒子和右兒子的根編號。第六頁，共四十二頁，編輯于2023年，星期三線段樹-建樹從根對應(yīng)的區(qū)間[a，b]出發(fā)，每次分成兩個部分，分別建立對應(yīng)的左右子樹，直到面臨一個初等區(qū)間[x,x+1]。第七頁，共四十二頁，編輯于2023年，星期三線段樹-插入刪除線段將區(qū)間[c,d]插入線段樹T(a,b),并設(shè)T(a,b)的根編號為vprocedureINSERT(c,d;v)Beginmid=(B[v]+E[v])div2;

ifc≤B[v]andE[v]≤dthenC[v]←C[v]+1

elseifc<midthenINSERT(c,d;LSON[v]);

ifd>midthenINSERT(c,d;RSON[v]);end

第八頁，共四十二頁，編輯于2023年，星期三線段樹-一個特殊性質(zhì)舉例要得到線段樹上線段并集的長度，增加一個數(shù)據(jù)域M[v]，討論：C[v]>0,M[v]=E[v]-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]];第九頁，共四十二頁，編輯于2023年，星期三線段樹-變形，對點統(tǒng)計第十頁，共四十二頁，編輯于2023年，星期三[例一]一位顧客要進行n（1≤n≤5000）天的購物，每天他會有一些帳單。每天購物以后，他從以前的所有帳單中挑出兩張帳單，分別是面額最大的和面額最小的一張，并把這兩張帳單從記錄中去掉。剩下的帳單留在以后繼續(xù)統(tǒng)計。輸入的數(shù)據(jù)保證，所有n天的帳單總數(shù)不超過1000000，并且每份帳單的面額值是1到1000000之間的整數(shù)。保證每天總可以找到兩張帳單。第十一頁，共四十二頁，編輯于2023年，星期三建立點線段樹，范圍是[1，1000000]，即每種面額的帳單設(shè)為一個葉結(jié)點。如果C[LSON[v]]>0,那么樹v中的最小值一定在它的左子樹上。如果C[RSON[v]]>0，它的最大值在右子樹上；第十二頁，共四十二頁，編輯于2023年，星期三一種靜態(tài)統(tǒng)計方法[例二]IOI2001MOBILES： 在一個N*N的方格中，開始每個格子里的數(shù)都是0。現(xiàn)在動態(tài)地提出一些問題和修改：提問的形式是求某一個特定的子矩陣(x1,y1)-(x2,y2)中所有元素的和；修改的規(guī)則是指定某一個格子(x,y)，在(x,y)中的格子元素上加上或者減去一個特定的值A(chǔ)?，F(xiàn)在要求你能對每個提問作出正確的回答。1≤N≤1024,提問和修改的總數(shù)可能達到60000條。第十三頁，共四十二頁，編輯于2023年，星期三一維序列求和設(shè)序列的元素存儲在a[]中，a的下標是1..n的正整數(shù)，需要動態(tài)地更新某個a[x]的值，同時要求出a[x1]到a[y1]這一段所有元素的和。第十四頁，共四十二頁，編輯于2023年，星期三對于序列a[1..n]，我們設(shè)一個數(shù)組C[1..n]，C[i]=a[i-2k+1]+…+a[i],其中k為i在二進制下末尾0的個數(shù)

1001010110010000k=4

計算C[x]對應(yīng)的2kLOWBIT（x）2k=xand(xxor(x-1))第十五頁，共四十二頁，編輯于2023年，星期三修改一個a[x]的值與哪些C相關(guān)？例如x=76=(1001010)2，從形式上進行觀察，可以得到：

p1=1001010p2=1001100p3=1010000p4=1100000p5=10000000修改C[p1],C[p2],…第十六頁，共四十二頁，編輯于2023年，星期三procedureUPDATA(x,A)beginp←x

while(p<=n)do

begin C[p]←C[p]+Ap←p+LOWBIT(p)

endend

維護的費用：logn第十七頁，共四十二頁，編輯于2023年，星期三求a[1]-a[x]的和functionSUM(x)begin ans←0p←xwhile(p>0)do

beginans←ans+C[p]p←p-LOWBIT(p)

endreturnansend

C[p]=a[p-2k

+1]+^+a[p]下一個p=x-2k第十八頁，共四十二頁，編輯于2023年，星期三推廣為原來的二維問題，把C構(gòu)造成C[x，y]，其每一維定義與原來相同。推廣后算法：兩層嵌套，一次維護費用為O(log2n)第十九頁，共四十二頁，編輯于2023年，星期三集合{3，4，5，8，19，6}靜態(tài)二叉排序樹實現(xiàn)第二十頁，共四十二頁，編輯于2023年，星期三構(gòu)造過程1遞歸：建立所有點坐標的映射Xp←0作為X映射中的指針procedureBUILD(ID:integer)

begin if(ID*2≤n)thenBUILD(ID*2);p←p+1；

V[ID]=X[p]；

if(ID*2+1≤n)thenBUILD(ID*2+1);end在主程序中調(diào)用BUILD(1)第二十一頁，共四十二頁，編輯于2023年，星期三構(gòu)造過程2非遞歸：方法，依次找出當前點的后繼點的下標第一個點first一定為最下層最左邊的一個位置,若n個點有L層,則first=2L-1若當前的點位置為now：如果它有右兒子，即now*2+1<=n,則下一個位置是右子樹最左下的點如果沒有右兒子，當now是奇數(shù)時，將now除以2，直到now是偶數(shù)，最后再將now除以2。第二十二頁，共四十二頁，編輯于2023年，星期三插入一個點xprocedureINSERT(x)begin now←1repeat

SUM[now]←SUM[now]+1if(V[now]=x)breakif(V[now]>x)now←now*2elsenow←now*2+1untilfalseEnd其中SUM是記錄一棵子樹上結(jié)點總數(shù)刪除的方法是類似的第二十三頁，共四十二頁，編輯于2023年，星期三怎樣解決例二procedureINSERT2(x,A)begin now←1repeat

if(x<=V[now])thenLESS[now]←LESS[now]+Aif(V[now]=x)breakif(V[now]>x)now←now*2elsenow←now*2+1untilfalseendLESS為根及其左子樹上所有點位置的權(quán)和第二十四頁，共四十二頁，編輯于2023年，星期三求a[1..x]的元素和functionSUM(x):longintbegin ans←0 now←1repeat

if(V[now]<=x)ans←ans+LESS[now]if(V[now]=x)breakif(V[now]>x)now←now*2elsenow←now*2+1untilfalsereturnansend第二十五頁，共四十二頁，編輯于2023年，星期三[例三]采礦(KOP)

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

000);他們分別平行于OX坐標和OY坐標，指明了地域的尺寸。接下來一行是整數(shù)n(1<=n<=15

000)，表示采金點的總數(shù)。然后是n行，每行兩個整數(shù)，給出了一個采金點的坐標。坐標范圍是(-30

000<=x,y<=30

000)。輸出： 一個整數(shù)，最多的采金點數(shù)。第二十六頁，共四十二頁，編輯于2023年，星期三樣例圖示第二十七頁，共四十二頁，編輯于2023年，星期三初步，對X離散化后，圖示第二十八頁，共四十二頁，編輯于2023年，星期三對于每一種坐標y，建立成兩個點事件(y,+1),(y+w+1,-1)，例如在一個帶狀區(qū)域內(nèi)有5個點的縱坐標分別是{5，3，9，1，9}，w=2

，標成(1,+1),(4,-1),(3,+1),(6,-1),(5,+1),(8,-1),(9,+1),(12,-1),(9,+1),(12,-1),再將他們按照y的坐標排序，得(1,+1),(3,+1),(4,-1),(5,+1)，(6,-1),(8,-1),(9,+1),(9,+1),(12,-1),(12,-1)我們把后面的標號反映在一個y坐標的映射上，然后從低到高求和

第二十九頁，共四十二頁，編輯于2023年，星期三坐標下的求和，這些和中最大的一個就是該帶狀區(qū)域中一個包含最多點數(shù)的矩形在插入或者刪除一個點事件之后，能夠維持坐標下∑的值；能夠在很短時間內(nèi)得到∑中最大的一個值。第三十頁，共四十二頁，編輯于2023年，星期三實現(xiàn)：SUM[now]對應(yīng)子樹上所有+1，-1標號的和。實現(xiàn)極簡單MAXSUM[now]，子樹上和最大的一個前綴的值。MAXSUM[1]是一種狀態(tài)下得到最優(yōu)解。如何維護？MAXSUM[]有哪幾種可能？1最大值在左樹上；2最大值正好包含根結(jié)點；3最大值在右樹上。第三十一頁，共四十二頁，編輯于2023年，星期三自下而上維護樹的特性找到當前坐標對應(yīng)點序號now,修正標號為kRepeatSUM[now]←SUM[now]+kMAXSUM[now]←Max{

MAXSUM[now*2],SUM[now]-SUM[now*2+1],SUM[now]-SUM[now*2+1]+MAXSUM[now*2+1]}now←nowdiv2untilnow=0第三十二頁，共四十二頁，編輯于2023年，星期三二分法虛擬實現(xiàn)樹二叉樹使用之前必須構(gòu)造出一個空的二叉樹對于任何一個有序表，在對其進行二分查找時，實際上就等于在一個二叉樹上進行查找第三十三頁，共四十二頁，編輯于2023年，星期三對于一個表{1，3，4，8，9}的二分查找，等價于在如下圖的二叉排序樹上進行查找：第三十四頁，共四十二頁，編輯于2023年，星期三舉插入結(jié)點的例子，來說明這種虛實現(xiàn)的方法，設(shè)LESS表示根及其左樹上結(jié)點的個數(shù)：procedureINSERT(x)begin l←1,r←n

while(l<=r)do

begin m=(l+r)div2ifx<=V[m]LESS[m]←LESS[m]+1 ifx=V[m]break ifx<V[m]thenr←m–1 elsel←m+1

endend

第三十五頁，共四十二頁，編輯于2023年，星期三[例四]最長下降序列給定一個整數(shù)序列a，求最長下降序列的長度。O（n2)第三十六頁，共四十二頁，編輯于2023年，星期三對P進行特殊的限制，即，在所有等價的決策j中，P選擇a[j]最大的那一個在處理完a[1..x-1]之后，對于所有長度為M[x]-1的下降序列，P[x]的決策只跟其中末尾最大的一個有關(guān)。用另外一個動態(tài)變化的數(shù)組b，當我們計算完了a[x]之后，a[1..x]中得到的所有下降序列按照長度分為L類，每一類中只需要一個作為代表，這個代表在這個等價類中末尾的數(shù)最大，我們把它記為b[j],1≤j≤L。處理當前的一個數(shù)a[x]，我們無需和前面的a[j]（1≤j≤x-1）作比較，只需要和b[j]（1≤j≤L)進行比較。第三十七頁，共四十二頁，編輯于2023年，星期三首先，如果a[x]<b[L]，把a[x]接在這個序列的后面，形成了一個長度為L+1的序列.。這時b[L+1]=a[x],即a[x]作為長度為L+1的序列的代表，同時L應(yīng)該增加1。另一種可能是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]必然接在