算法paper線段樹與二分法lirui

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

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

3、) div 2;if cBv and Evd then Cv Cv+1else if cmid then INSERT(c,d;RSONv);end 線段樹-一個特殊性質(zhì)舉例要得到線段樹上線段并集的長度，增加一個數(shù)據(jù)域 Mv，討論： Cv0,Mv = Ev-Bv;Cv=0 且v是葉子結(jié)點，Mv=0；Cv=0 且v是內(nèi)部結(jié)點，Mv=MLSONv+MRSONv; 線段樹-變形，對點統(tǒng)計例一一位顧客要進(jìn)行n（1n5000）天的購物，每天他會有一些帳單。每天購物以后，他從以前的所有帳單中挑出兩張帳單，分別是面額最大的和面額最小的一張，并把這兩張帳單從記錄中去掉。剩下的帳單留在以后繼續(xù)統(tǒng)計。輸入的數(shù)據(jù)保

4、證，所有n天的帳單總數(shù)不超過1000000，并且每份帳單的面額值是1到1000000之間的整數(shù)。保證每天總可以找到兩張帳單。 建立點線段樹，范圍是1，1000000，即每種面額的帳單設(shè)為一個葉結(jié)點。 如果CLSONv0,那么樹v中的最小值一定在它的左子樹上。如果CRSONv0，它的最大值在右子樹上； 一種靜態(tài)統(tǒng)計方法例二IOI2001 MOBILES ：在一個N*N的方格中，開始每個格子里的數(shù)都是0?，F(xiàn)在動態(tài)地提出一些問題和修改：提問的形式是求某一個特定的子矩陣(x1,y1)-(x2,y2)中所有元素的和；修改的規(guī)則是指定某一個格子(x,y)，在(x,y)中的格子元素上加上或者減去一個特定的值

5、A?，F(xiàn)在要求你能對每個提問作出正確的回答。1N1024,提問和修改的總數(shù)可能達(dá)到60000條。 一維序列求和設(shè)序列的元素存儲在a中，a的下標(biāo)是1.n的正整數(shù)，需要動態(tài)地更新某個ax的值，同時要求出ax1到ay1這一段所有元素的和。 對于序列a1.n，我們設(shè)一個數(shù)組C1.n，Ci=ai-2k+1+ai,其中k為i在二進(jìn)制下末尾0的個數(shù) 1001010110010000 k =4 計算Cx對應(yīng)的2k LOWBIT（x）2k =x and (x xor (x-1)修改一個ax的值 與哪些C相關(guān)？ 例如x=76=(1001010)2，從形式上進(jìn)行觀察，可以得到： p1= 1001010 p2= 100

6、1100 p3= 1010000 p4= 1100000 p5=10000000修改Cp1,Cp2,procedure UPDATA(x,A)begin px while (p0) do begin ansans+Cp pp-LOWBIT(p) endreturn ansend Cp=ap- 2k +1+ap下一個p=x- 2k推廣為原來的二維問題，把C構(gòu)造成 Cx，y，其每一維定義與原來相同。推廣后算法：兩層嵌套，一次維護(hù)費用為O(log2n)集合3，4，5，8，19，6 靜態(tài)二叉排序樹實現(xiàn)構(gòu)造過程1 遞歸：建立所有點坐標(biāo)的映射Xp 0 作為X映射中的指針procedure BUILD(ID

7、:integer) beginif (ID*2n) then BUILD(ID*2); pp+1； VID=Xp； if (ID*2+1n) then BUILD(ID*2+1);end在主程序中調(diào)用BUILD(1) 構(gòu)造過程2 非遞歸：方法，依次找出當(dāng)前點的后繼點的下標(biāo)第一個點first一定為最下層最左邊的一個位置,若n個點有L層,則first=2 L-1若當(dāng)前的點位置為now： 如果它有右兒子，即now*2+1x) nownow*2 else nownow*2+1until falseEnd其中SUM是記錄一棵子樹上結(jié)點總數(shù)刪除 的方法是類似的怎樣解決例二procedure INSERT2

8、(x,A)beginnow 1repeat if (xx) nownow*2 else nownow*2+1until falseendLESS為根及其左子樹上所有點位置的權(quán)和求a1.x的元素和function SUM(x):longintbeginans 0now 1repeat if (Vnowx) nownow*2 else nownow*2+1until false return ansend 例三采礦(KOP) 金礦的老師傅年底要退休了。經(jīng)理為了獎賞他的盡職盡責(zé)的工作，決定送他一塊長方形地。長度為S，寬度為W。老師傅可以自己選擇這塊地。顯然其中包含的采金點越多越好。你的任務(wù)就是計算最

9、多能得到多少個采金點。如果一個采金點的位置在長方形的邊上，它也應(yīng)當(dāng)被計算在內(nèi)。任務(wù)：讀入采金點的位置。計算最大的價值。輸入：文件KOP.IN的第一行是S和W，(1=s,w=10000);他們分別平行于OX坐標(biāo)和OY坐標(biāo)，指明了地域的尺寸。接下來一行是整數(shù)n (1=n=15000)，表示采金點的總數(shù)。然后是n行，每行兩個整數(shù)，給出了一個采金點的坐標(biāo)。坐標(biāo)范圍是(-30000=x,y=30000)。輸出：一個整數(shù)，最多的采金點數(shù)。樣例圖示初步，對X離散化后，圖示對于每一種坐標(biāo)y，建立成兩個點事件(y,+1),(y+w+1,-1)，例如在一個帶狀區(qū)域內(nèi)有5個點的縱坐標(biāo)分別是5，3，9，1，9，w=2

10、 ，標(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坐標(biāo)的映射上，然后從低到高求和 坐標(biāo)下的求和，這些和中最大的一個就是該帶狀區(qū)域中一個包含最多點數(shù)的矩形 在插入或者刪除一個點事件之后，能夠維持坐標(biāo)下的值；能夠在很短時間內(nèi)得到中最大的一個值。 實現(xiàn)：SUMnow對應(yīng)子樹上所有+1，-1標(biāo)

11、號的和。實現(xiàn)極簡單MAXSUMnow，子樹上和最大的一個前綴的值。MAXSUM1是一種狀態(tài)下得到最優(yōu)解。如何維護(hù)？MAXSUM有哪幾種可能？1 最大值在左樹上；2 最大值正好包含根結(jié)點；3 最大值在右樹上。 自下而上維護(hù)樹的特性找到當(dāng)前坐標(biāo)對應(yīng)點序號now,修正標(biāo)號為kRepeat SUMnowSUMnow+k MAXSUMnowMax MAXSUMnow*2,SUMnow-SUMnow*2+1,SUMnow-SUMnow*2+1+MAXSUMnow*2+1 now now div 2until now = 0 二分法虛擬實現(xiàn)樹二叉樹使用之前必須構(gòu)造出一個空的二叉樹 對于任何一個有序表，在對其

12、進(jìn)行二分查找時，實際上就等于在一個二叉樹上進(jìn)行查找 對于一個表1，3，4，8，9的二分查找，等價于在如下圖的二叉排序樹上進(jìn)行查找： 舉插入結(jié)點的例子，來說明這種虛實現(xiàn)的方法，設(shè)LESS表示根及其左樹上結(jié)點的個數(shù)： procedure INSERT(x)beginl1,rnwhile (l=r) do begin m=(l+r) div 2 if x=Vm LESSmLESSm+1if x =Vm breakif xVm then r m 1 else lm+1 endend 例四最長下降序列給定一個整數(shù)序列a，求最長下降序列的長度。O（n2)對P進(jìn)行特殊的限制，即，在所有等價的決策j中，P選擇

13、aj最大的那一個 在處理完a1.x-1之后，對于所有長度為Mx-1的下降序列，Px的決策只跟其中末尾最大的一個有關(guān)。 用另外一個動態(tài)變化的數(shù)組b，當(dāng)我們計算完了ax之后，a1.x中得到的所有下降序列按照長度分為L類，每一類中只需要一個作為代表，這個代表在這個等價類中末尾的數(shù)最大，我們把它記為bj,1jL。 處理當(dāng)前的一個數(shù)ax，我們無需和前面的aj（1jx-1）作比較，只需要和bj（1jL)進(jìn)行比較。 首先，如果ax=b1，這時ax 僅能構(gòu)成長度為1的下降序列，同時它又必然是最大的，所以它作為b1的代表,b1=ax。 如果前面的情況都不存在，我們肯定可以找到一個j,2jL,有bj-1ax,bjax，這時分析，ax必然接在bj-1后面，行成一個新的長度為j的序列。 這幾種情況實際上都可以歸結(jié)為：處理ax，令bL+1為無窮小，從左到右找到第一個位置j，使bjax,然后則只要將bj=ax,如果j=L+1,則L同時增加。x處以前對應(yīng)