算法合集之淺談數(shù)據(jù)的合理組織(編輯修改稿)
2025-09-14 16:49 本頁面
【文章內(nèi)容簡介】 的先根遍歷序?qū)⑥D(zhuǎn)樹形轉(zhuǎn)化為線形序列，成功地避免了樹形形態(tài)的限制，正是合理地組織數(shù)據(jù)。我們得到的啟示：憑第一感覺想出來的模型不一定是最好的，對于一個題目，我們充分挖掘其數(shù)據(jù)關(guān)系并加以利用，合理地組織數(shù)據(jù)并且嘗試用已有的知識來解決，推陳出新，才能不斷地進步。前面我們在樹據(jù)的組織結(jié)構(gòu)上進行了合理地安排，成功地對于每一次加強的題目都設(shè)計出了優(yōu)秀的算法，下面，我們來看一看“順序”的合理安排的例子：［例二］樹的果實【題意描述】給出一棵有N個節(jié)點的有根樹（根為1號節(jié)點），每個節(jié)點有權(quán)值。要求對于每一個節(jié)點，求：其中(1=N=105)【問題分析】對于要求的后面兩個值，我們很容易想到O(Nlog2(N))的算法：樹上除其子孫節(jié)點外比該節(jié)點大的節(jié)點總數(shù)：直接排序，在待統(tǒng)計節(jié)點前的與該節(jié)點權(quán)值不同的個數(shù)再減去問題1的答案即為所求。從根節(jié)點到該節(jié)點路徑中比該節(jié)點大的節(jié)點總數(shù)：以權(quán)值為關(guān)鍵字構(gòu)造線段樹(若權(quán)值大可行離散化處理)，深度優(yōu)先遍歷樹上節(jié)點，用棧記錄下到節(jié)點的路徑，并把當前節(jié)點插入線段樹，在線段樹中我們記錄區(qū)間的元素個數(shù)，當前節(jié)點權(quán)值到最大權(quán)值這個區(qū)間中元素個數(shù)即為所求，我們再遞歸處理子樹，在子樹訪問完畢后還須把該節(jié)點從線段樹中刪除。我們最大的困難在于求：其子樹中權(quán)值比該節(jié)點大的節(jié)點總數(shù)O(N2)的樸素統(tǒng)計方法是很容易想到的，但是本題的數(shù)據(jù)規(guī)模達到105，O(N2)的復雜度顯然太高。我們自然想到利用線段樹、樹狀數(shù)組這些優(yōu)秀的統(tǒng)計數(shù)據(jù)結(jié)構(gòu)來進行題目中要求的統(tǒng)計任務(wù)。但是這些數(shù)據(jù)結(jié)構(gòu)都是用于線型序列統(tǒng)計的，并且似乎沒有改造版本用于樹形結(jié)構(gòu)。既然沒有辦法改造數(shù)據(jù)結(jié)構(gòu)，那么我們轉(zhuǎn)換數(shù)據(jù)形態(tài)——把樹轉(zhuǎn)化為序列再進行統(tǒng)計，先根遍歷序即是我們轉(zhuǎn)換后的理想形態(tài)。我們給出一個例子：同一棵子樹構(gòu)成一個連續(xù)的區(qū)間，這正方便了我們的統(tǒng)計。我們定義：一個元素所在子樹在遍歷序中構(gòu)成的區(qū)間叫作元素所在區(qū)間。元素相比較都指其權(quán)值大小相比較?，F(xiàn)在問題已經(jīng)轉(zhuǎn)化成為：給出一個序列，每個元素有權(quán)值。對于每一個元素，統(tǒng)計一個區(qū)間中有多少元素比該元素大。這正是我們比較熟悉的序列上的統(tǒng)計問題。下面我們研究轉(zhuǎn)化后的問題：【數(shù)據(jù)組織方案一】我們不對數(shù)據(jù)進行更深入的組織，直接利用先根遍歷序，強制用數(shù)據(jù)結(jié)構(gòu)來進行統(tǒng)計。當然我們可以構(gòu)造出一種比較有效的嵌套數(shù)據(jù)結(jié)構(gòu)——以有序表為元素的線段樹，如圖： 其中，線段樹的每一個節(jié)點是對應(yīng)區(qū)間的元素以權(quán)值為關(guān)鍵字的有序表。這樣，預處理可以用一個歸并排序，求得樹上所有區(qū)間的有序表。時間復雜度為O(Nlog2(N))。假設(shè)現(xiàn)在我們要統(tǒng)計一個區(qū)間(長度為L)。那么我們可以用log2 (L)的時間找到該區(qū)間的所有分解區(qū)間(不超過2log2 (L)個)。然后在對每個分解區(qū)間進行處理：二分查找在該區(qū)間中有多少元素的權(quán)值比指定的元素的權(quán)值大。然后把所有分解區(qū)間中比給定元素大的元素個數(shù)加起來，即為所求。這樣每統(tǒng)計一個元素的復雜度為O(log22(N))?？倳r間復雜度為O(Nlog22(N))，空間復雜度為O(Nlog2(N))?！緮?shù)據(jù)組織方案二】我們從特殊情況考慮：假設(shè)我們在先根遍歷序中，需要統(tǒng)計元素k，并且k所在區(qū)間里的元素都比它大。顯然，這時比k大的元素個數(shù)就是k所在區(qū)間中的元素個數(shù)。統(tǒng)計區(qū)間元素個數(shù)我們可以直接利用線段樹和樹狀數(shù)組。那么我們?nèi)绾伪ＷC當前列表中的元素權(quán)值都比k的權(quán)值大呢？我們重新組織數(shù)據(jù)：所有元素按從大到小的順序排序。然后依次處理每一個元素：先取得所在區(qū)間的元素個數(shù)，再將該元素插入。我們一個很巧妙的方法：從大到小地向線段樹里面加入元素，然后統(tǒng)計區(qū)間個數(shù)。從大到小保證了現(xiàn)有的所有元素都比待插入的元素大。所以區(qū)間中的元素個數(shù)即為比待插入元素大的元素個數(shù)。按照從大到小的順序之前先對其區(qū)間進行統(tǒng)計，利用線段樹或樹狀數(shù)組。這樣，我們得到了復雜度為O(Nlog2(N))的算法。WC2005何林同學的論文中介紹了此題的另一解法，復雜度也為O(Nlog2(N))。主要思想是也是利用樹的前根遍歷序，不同的是他的算法是基于容斥原理，需要正反兩次遍歷樹，而我們這里介紹的算法是利用了“組織數(shù)據(jù)的操作順序”這一手段來實現(xiàn)的。有興趣的同學可以參見何林同學2005年的論文?！靶螒B(tài)”和“順序”這兩種數(shù)據(jù)組織對象在上面的兩個例題中分別對我們進行了表演。下面我們再來分析一個更經(jīng)典的題目：［例三］航線規(guī)劃【題意描述】給出一個有N個點M條邊的無向圖，兩點之間可能有多條邊，然后給出Q個命令，命令共有如下兩種：1 A B表示刪除一條A到B的邊2 A B表示詢問AB間共有多少條關(guān)鍵邊（即刪除改邊后使得AB不連通)數(shù)據(jù)保證任意時刻圖都是連通的。1 ≤ N ≤ 3 * 1041 ≤ M ≤ 1051 ≤ Q ≤ 105【問題分析】顯然，我們可以輕松地設(shè)計出一個樸素的算法：用隊列保存所有邊，當遇到刪邊操作時加上刪除標記（利用HASH我們可以做到O(1))，遇到詢問操作時則枚舉刪邊然后用并查集判斷AB是否連通。這個算法處理刪邊的復雜度為O(1)，處理詢問的復雜度為O(M2)，空間復雜度為O(M+N)。我們經(jīng)過思考后發(fā)現(xiàn)，事實上所謂的關(guān)鍵邊都是圖上的橋(由題目中的描述我們很容易想到)。而橋的數(shù)量是O(N)級別的。利用上面的結(jié)論，我們顯然可以先用O(E)的時間求出圖中所有的橋，然后再用O(N2)的時間求出AB間的關(guān)鍵邊的數(shù)量。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1