樹(shù)結(jié)構(gòu)在程序設(shè)計(jì)中的運(yùn)用

1、樹(shù)結(jié)構(gòu)在程序設(shè)計(jì)中的運(yùn)用浙江省4年NOI組隊(duì)賽1目錄引言樹(shù)結(jié)構(gòu)在程序設(shè)計(jì)中的運(yùn)用2 2003年競(jìng)賽的知識(shí)結(jié)構(gòu)分布 競(jìng)賽試題算法NOIP乒乓球數(shù)據(jù)統(tǒng)計(jì)NOIP數(shù)字游戲動(dòng)態(tài)程序設(shè)計(jì)NOIP棧回溯法或組合數(shù)學(xué)的Catalan數(shù)NOIP麥森數(shù)高精度運(yùn)算NOIP神經(jīng)網(wǎng)絡(luò)圖的遞歸運(yùn)算NOIP偵探推理回溯法NOIP加分二叉樹(shù)遞歸的動(dòng)態(tài)程序設(shè)計(jì)NOIP傳染病擴(kuò)展回溯法3 競(jìng)賽試題算法IOI 可視邊界線段樹(shù)IOI 代碼轉(zhuǎn)換程序語(yǔ)句在滿足加法交換率和變量名改換情況下的匹配IOI 猜牛游戲貪心或類博弈樹(shù)算法IOI 路徑維護(hù)在無(wú)向圖的生成過(guò)程過(guò)程中計(jì)算最小生成樹(shù)IOI 逆向輸出開(kāi)放性試題IOI 機(jī)器人寬度優(yōu)先搜索20

2、03年競(jìng)賽的知識(shí)結(jié)構(gòu)分布4 競(jìng)賽試題算法NOI 木棒游戲枚舉搜索NOI文本編輯器數(shù)據(jù)結(jié)構(gòu)NOI 衛(wèi)星探測(cè)二分查找NOI草莓后序遍歷NOI 數(shù)據(jù)生成器前序遍歷和后序遍歷NOI智破連環(huán)陣回溯法2003年競(jìng)賽的知識(shí)結(jié)構(gòu)分布5試題特點(diǎn)1、強(qiáng)調(diào)基礎(chǔ)知識(shí)的靈活應(yīng)用。每一輪競(jìng)賽都有基礎(chǔ)知識(shí)題，但對(duì)靈活應(yīng)用基礎(chǔ)知識(shí)的要求愈來(lái)愈高。例如IOI的路徑維護(hù)在逐邊添入無(wú)向圖的過(guò)程中計(jì)算最小生成樹(shù)；文本編輯器要求設(shè)計(jì)多樣的數(shù)據(jù)結(jié)構(gòu)。例如線性表、非線性的樹(shù)和圖；NOIP的加分二叉樹(shù)采用的動(dòng)態(tài)程序設(shè)計(jì)是遞歸形式的；NOI的數(shù)據(jù)生成器必須綜合使用前序遍歷和后序遍歷2、首次出現(xiàn)了線段樹(shù)和可以選擇類博弈樹(shù)算法的試題3、近似算法類

3、的試題增加。例如IOI的猜牛游戲、逆向輸出、機(jī)器人、NOI的衛(wèi)星探測(cè)、草莓、智破連環(huán)陣等。由于這些例題視程序逼近最優(yōu)解和最優(yōu)效率的程度給分，因此拓展了選手思維的空間，易啟發(fā)選手的創(chuàng)造性。但反過(guò)來(lái)說(shuō)，由于近似算法類的選題空間比較大，因此有可能使得題目的難度加大。6試題特點(diǎn)4、樹(shù)形結(jié)構(gòu)類的問(wèn)題增多。例如NOI的衛(wèi)星探測(cè)通過(guò)二分查找構(gòu)造一棵隱形的二叉樹(shù)；草莓和數(shù)據(jù)生成器使用了人們?nèi)菀妆缓鲆暤暮笮虮闅v；IOI的路徑維護(hù)要求計(jì)算最小生成樹(shù)；5、可“一題多解”和開(kāi)放性的試題增多。例如，IOI的逆向輸出就是一道沒(méi)有固定模式和經(jīng)典算法可套用、需要量身定制合適算法的試題；猜牛游戲既可以采用貪心法，亦可以采用類博

4、弈樹(shù)的算法；NOIP的棧既可以通過(guò)回溯法計(jì)算，亦可以通過(guò)組合數(shù)學(xué)的Catalan數(shù)計(jì)算；6、出現(xiàn)一些“陷阱題”。例如NOIP的傳染病擴(kuò)展極易誘導(dǎo)選手錯(cuò)誤地使用貪心法或動(dòng)態(tài)程序設(shè)計(jì)，實(shí)際上該問(wèn)題不具備最優(yōu)子結(jié)構(gòu)的特征，正確的算法是回溯搜索。7啟示培養(yǎng)內(nèi)省智力充分利用網(wǎng)絡(luò)資源以問(wèn)題為出發(fā)點(diǎn)、以自主探究為途徑、以構(gòu)造網(wǎng)絡(luò)式思維模式為基礎(chǔ)、以創(chuàng)新為目的組織集訓(xùn) 8培養(yǎng)內(nèi)省智力入門 自信心提高 自省力自信心和自知之明是對(duì)立的統(tǒng)一。自信心倘若不是建立在自知之明的基礎(chǔ)上，則會(huì)變成一種無(wú)知的自負(fù)，不可能取得持續(xù)的成功。 科學(xué)精神的核心是懷疑和批評(píng)。這種態(tài)度既對(duì)他人又對(duì)自己，“知人者智，自知者明”，“知常曰明”

5、 不能用看書(shū)取代上機(jī)實(shí)踐，經(jīng)常要想“自己怎樣面對(duì)這個(gè)問(wèn)題的挑戰(zhàn)；如果由自己當(dāng)場(chǎng)獨(dú)立解題的話，會(huì)得到怎樣的結(jié)果”?！凹埳系脕?lái)終覺(jué)淺，絕知此事要躬行”?？炊瞬幌∑?，會(huì)做有靈氣，能講清原理、提出質(zhì)疑、拓延思路、探索新知才算了不起在挑選練習(xí)題時(shí)，既不要因?yàn)檩p視而放棄基礎(chǔ)題；也不要因?yàn)槲冯y而放棄大題難題。 9充分利用網(wǎng)絡(luò)上與信息學(xué)活動(dòng)相關(guān)的信息資源1、由于網(wǎng)絡(luò)上大量的算法知識(shí)和試題的出現(xiàn)，使得學(xué)生學(xué)習(xí)的大部分時(shí)間和空間由課堂轉(zhuǎn)移到網(wǎng)上學(xué)習(xí)，自主性顯著提高，學(xué)習(xí)方式發(fā)生了根本性的變化2、學(xué)習(xí)的效率取決于如何在浩如煙海的網(wǎng)上信息中選擇適應(yīng)于競(jìng)賽需要和個(gè)性發(fā)展的東西3、千萬(wàn)不要有“太易了不屑做、太難了不愿做

6、”的主觀隨意性 10充分利用網(wǎng)絡(luò)上與信息學(xué)活動(dòng)相關(guān)的信息資源編程解題能力是在長(zhǎng)期的上機(jī)實(shí)踐中積累起來(lái)的。如果長(zhǎng)期的無(wú)所事事、無(wú)所作為，遲早會(huì)落得了“小題做不對(duì)、大題難題不會(huì)做”的可悲結(jié)局應(yīng)該對(duì)試題本身有一個(gè)科學(xué)的價(jià)值判斷：“這道題是不是有利于夯實(shí)基礎(chǔ)，或者這道題是不是引出帶規(guī)律性的東西，能不能派生出更多類似的問(wèn)題”，真正從提高自身的算法認(rèn)知水平和編程能力的高度，來(lái)決定練習(xí)題的取舍。 11以問(wèn)題為出發(fā)點(diǎn)、以自主探究為途徑、以構(gòu)造網(wǎng)絡(luò)式思維模式為基礎(chǔ)、以創(chuàng)新為目的組織集訓(xùn)第一步：界定問(wèn)題。即明確試題要求我們做什么,解決什么問(wèn)題，輸出怎樣的結(jié)果第二步：明確出發(fā)點(diǎn)，即明確試題的初始狀態(tài)是什么，給出了哪

7、些求解條件，其中哪些是顯性的，哪些是隱性的，必須無(wú)一漏失。第三步：尋找怎樣做的創(chuàng)意。即要求學(xué)生獨(dú)立思考，盡可能多地收集相關(guān)資料，嘗試各種組合，調(diào)動(dòng)所有的靈感和思考方式。第四步：集中測(cè)試。每人設(shè)計(jì)三組測(cè)試數(shù)據(jù),分別從一般情況、邊界情況、擴(kuò)大問(wèn)題規(guī)模三個(gè)角度測(cè)試程序的正確性、時(shí)間效率和空間效率。然后交流測(cè)試數(shù)據(jù)，學(xué)生間進(jìn)行互測(cè)。這樣做既能測(cè)出自己程序的正確程度，又能在改善程序的時(shí)空效率上取長(zhǎng)補(bǔ)短。 12建立知識(shí)信息網(wǎng)絡(luò) 歸納概括 通過(guò)對(duì)相關(guān)問(wèn)題（即形式不同、本質(zhì)類似的一類問(wèn)題）的歸納，揭示內(nèi)在的聯(lián)系，概括出解決類似問(wèn)題的一般規(guī)律，并得到高度抽象、概括的模型，為以后分析問(wèn)題、設(shè)計(jì)算法進(jìn)行指導(dǎo)。 13

8、觸類旁通、聯(lián)想外推 通過(guò)舉一反三、由此及彼、觸類旁通，從一個(gè)問(wèn)題拓廣出許多新問(wèn)題。在解決這些新問(wèn)題的過(guò)程中，進(jìn)一步鍛煉思維，并通過(guò)聯(lián)想的線索將新問(wèn)題、新模型、新算法并入知識(shí)網(wǎng)14近年來(lái)，由于各種競(jìng)賽紛紛采用free-pascal，因此對(duì)于算法來(lái)說(shuō)，空間效率上的要求降低了，而對(duì)時(shí)間效率卻提出了更高的要求。這使得選手不僅要嫻熟地掌握常規(guī)算法，而且要大膽創(chuàng)新，構(gòu)造更高效的算法來(lái)解決問(wèn)題。在以往的程序設(shè)計(jì)中，鏈?zhǔn)浇Y(jié)構(gòu)采用得較多。的確鏈?zhǔn)浇Y(jié)構(gòu)有編程復(fù)雜度低、簡(jiǎn)單易懂等優(yōu)點(diǎn)，但有一個(gè)致命的弱點(diǎn)：相鄰的兩個(gè)元素間的聯(lián)系并不明顯。而樹(shù)結(jié)構(gòu)卻能很好的做到這一點(diǎn)。選手對(duì)樹(shù)的先根遍歷十分嫻熟，但對(duì)后根遍歷卻不能像先

9、根遍歷那樣應(yīng)用自如。15樹(shù)結(jié)構(gòu)在程序設(shè)計(jì)中的運(yùn)用一并查集二線段樹(shù)三解決動(dòng)態(tài)統(tǒng)計(jì)的靜態(tài)方法四、二叉樹(shù)應(yīng)用的拓廣五、先根遍歷與后根遍歷的應(yīng)用小結(jié)16并查集 競(jìng)賽中會(huì)經(jīng)常遇到這樣的題目：給出各個(gè)元素之間的聯(lián)系，要求將這些元素分成幾個(gè)集合，每個(gè)集合中的元素直接或間接有聯(lián)系。在這類問(wèn)題中主要涉及的是對(duì)集合的合并和查找，因此將這種集合稱為并查集。 鏈結(jié)構(gòu)的并查集 樹(shù)結(jié)構(gòu)的并查集17鏈結(jié)構(gòu)的并查集鏈表被普通用來(lái)計(jì)算并查集.表中的每個(gè)元素設(shè)兩個(gè)指針：一個(gè)指向同一集合中的下一個(gè)元素；另一個(gè)指向表首元素。 采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，在進(jìn)行集合查找時(shí)的算法復(fù)雜度僅為O（1）；但合并集合時(shí)的算法復(fù)雜度卻達(dá)到了O（n）。如果我

10、們希望兩種基本操作的時(shí)間效率都比較高的話，鏈?zhǔn)酱鎯?chǔ)方式就“力不從心”了。18樹(shù)結(jié)構(gòu)的并查集采用樹(shù)結(jié)構(gòu)支持并查集的計(jì)算能夠滿足我們的要求。并查集與一般的樹(shù)結(jié)構(gòu)不同，每個(gè)頂點(diǎn)紀(jì)錄的不是它的子結(jié)點(diǎn)，而是將它的父結(jié)點(diǎn)記錄下來(lái)。下面我介紹一下樹(shù)結(jié)構(gòu)的并查集的兩種運(yùn)算方式直接在樹(shù)中查詢邊查詢邊“路徑壓縮”對(duì)應(yīng)與前面的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，樹(shù)狀結(jié)構(gòu)的優(yōu)勢(shì)非常明顯：編程復(fù)雜度低；時(shí)間效率高。 返回19直接在樹(shù)中查詢集合的合并算法很簡(jiǎn)單，只要將兩棵樹(shù)的根結(jié)點(diǎn)相連即可，這步操作只要O（1）時(shí)間復(fù)雜度。算法的時(shí)間效率取決于集合查找的快慢。而集合的查找效率與樹(shù)的深度呈線性關(guān)系。因此直接查詢所需要的時(shí)間復(fù)雜度平均為O（logN

11、）。但在最壞情況下，樹(shù)退化成為一條鏈，使得每一次查詢的算法復(fù)雜度為O（N）。20邊查詢邊“路徑壓縮” 其實(shí)，我們還能將集合查找的算法復(fù)雜度進(jìn)一步降低：采用“路徑壓縮”算法。它的想法很簡(jiǎn)單：在集合的查找過(guò)程中順便將樹(shù)的深度降低。采用路徑壓縮后，每一次查詢所用的時(shí)間復(fù)雜度為增長(zhǎng)極為緩慢的ackerman函數(shù)的反函數(shù)（x）。對(duì)于可以想象到的n，（n）都是在5之內(nèi)的。21銀河英雄傳說(shuō) 【問(wèn)題描述】公元五八一年，地球居民遷移至金牛座第二行星，在那里發(fā)表銀河聯(lián)邦創(chuàng)立宣言，同年改元為宇宙歷元年，并開(kāi)始向銀河系深處拓展。 宇宙歷七九九年，銀河系的兩大軍事集團(tuán)在巴米利恩星域爆發(fā)戰(zhàn)爭(zhēng)。泰山壓頂集團(tuán)派宇宙艦隊(duì)司令萊

12、因哈特率領(lǐng)十萬(wàn)余艘戰(zhàn)艦出征，氣吞山河集團(tuán)點(diǎn)名將楊威利組織麾下三萬(wàn)艘戰(zhàn)艦迎敵。 楊威利擅長(zhǎng)排兵布陣，巧妙運(yùn)用各種戰(zhàn)術(shù)屢次以少勝多，難免恣生驕氣。在這次決戰(zhàn)中，他將巴米利恩星域戰(zhàn)場(chǎng)劃分成30000列，每列依次編號(hào)為1， 2， ， 30000。之后，他把自己的戰(zhàn)艦也依次編號(hào)為1， 2， ， 30000，讓第i號(hào)戰(zhàn)艦處于第i列(i = 1， 2， ， 30000)，形成“一字長(zhǎng)蛇陣”，誘敵深入。這是初始陣形。當(dāng)進(jìn)犯之?dāng)车竭_(dá)時(shí)，楊威利會(huì)多次發(fā)布合并指令，將大部分戰(zhàn)艦集中在某幾列上，實(shí)施密集攻擊。合并指令為Mij，含義為讓第i號(hào)戰(zhàn)艦所在的整個(gè)戰(zhàn)艦隊(duì)列，作為一個(gè)整體（頭在前尾在后）接至第j號(hào)戰(zhàn)艦所在的戰(zhàn)艦隊(duì)

13、列的尾部。顯然戰(zhàn)艦隊(duì)列是由處于同一列的一個(gè)或多個(gè)戰(zhàn)艦組成的。合并指令的執(zhí)行結(jié)果會(huì)使隊(duì)列增大。然而，老謀深算的萊因哈特早已在戰(zhàn)略上取得了主動(dòng)。在交戰(zhàn)中，他可以通過(guò)龐大的情報(bào)網(wǎng)絡(luò)隨時(shí)監(jiān)聽(tīng)楊威利的艦隊(duì)調(diào)動(dòng)指令。 在楊威利發(fā)布指令調(diào)動(dòng)艦隊(duì)的同時(shí)，萊因哈特為了及時(shí)了解當(dāng)前楊威利的戰(zhàn)艦分布情況，也會(huì)發(fā)出一些詢問(wèn)指令：Cij。該指令意思是，詢問(wèn)電腦，楊威利的第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦當(dāng)前是否在同一列中，如果在同一列中，那么它們之間布置有多少戰(zhàn)艦。 作為一個(gè)資深的高級(jí)程序設(shè)計(jì)員，你被要求編寫(xiě)程序分析楊威利的指令，以及回答萊因哈特的詢問(wèn)。 最終的決戰(zhàn)已經(jīng)展開(kāi)，銀河的歷史又翻過(guò)了一頁(yè)22【輸入文件】輸入文件galax

14、y.in的第一行有一個(gè)整數(shù)T（1T500，000），表示總共有T條指以下有T行，每行有一條指令。指令有兩種格式：1. Mij：i和j是兩個(gè)整數(shù)（1i ， j30000），表示指令涉及的戰(zhàn)艦編號(hào)。該指令是萊因哈特竊聽(tīng)到的楊威利發(fā)布的艦隊(duì)調(diào)動(dòng)指令，并且保證第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦不在同一列。2.Cij：i和j是兩個(gè)整數(shù)（1i ， j30000），表示指令涉及的戰(zhàn)艦編號(hào)。該指令是萊因哈特發(fā)布的詢問(wèn)指令?！据敵鑫募枯敵鑫募間alaxy.out。你的程序應(yīng)當(dāng)依次對(duì)輸入的每一條指令進(jìn)行分析和處理：如果是楊威利發(fā)布的艦隊(duì)調(diào)動(dòng)指令，則表示艦隊(duì)排列發(fā)生了變化，你的程序要注意到這一點(diǎn)，但是不要輸出任何信息；如果

15、是萊因哈特發(fā)布的詢問(wèn)指令，你的程序要輸出一行，僅包含一個(gè)整數(shù)，表示在同一列上，第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦之間布置的戰(zhàn)艦數(shù)目。如果第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦當(dāng)前不在同一列上，則輸出-1。23設(shè)var Father，Count，Behind：array1.maxn of integer；在同一隊(duì)列中的戰(zhàn)艦組成一個(gè)樹(shù)型結(jié)構(gòu)的并查集。Fatherx 戰(zhàn)艦x的父指針。Fatherx=x，表明戰(zhàn)艦x為根節(jié)點(diǎn)。路徑壓縮后，樹(shù)中所有子節(jié)點(diǎn)的父指針指向根節(jié)點(diǎn)；Countx 以節(jié)點(diǎn)x為根的樹(shù)的節(jié)點(diǎn)數(shù)；Behindx 戰(zhàn)艦x在列中的相對(duì)位置；初始時(shí)，我們?yōu)槊恳凰覒?zhàn)艦建立一個(gè)集合，即Fatherx=x Countx=1 Be

16、hindx=0（1x30000) 241、查找根節(jié)點(diǎn)并進(jìn)行路徑壓縮 function Find_Father(x：integer)：integer；查找節(jié)點(diǎn)x所在樹(shù)的根節(jié)點(diǎn)，并進(jìn)行路徑壓縮var i，j，f，next：integer；begin ix； 找出節(jié)點(diǎn)x所在樹(shù)的根節(jié)點(diǎn)f while Fatherii do iFatheri； fi；ix； while if do 按照自下而上的順序處理x的祖先節(jié)點(diǎn) begin nextFatheri；FatherIf；把節(jié)點(diǎn)i的父節(jié)點(diǎn)設(shè)為f，完成路徑壓縮 jnext； repeat BehindiBehindi+Behindj；迭代求出路徑上每一個(gè)子

17、節(jié)點(diǎn)相對(duì)于f的相對(duì)位置 jFatherj； until Fatherj=j； inext； end；while find_Fatherf； 返回x所在樹(shù)的根節(jié)點(diǎn)end； Find_Father 252、計(jì)算合并指令 procedure MoveShip(x，y：integer)；把x所在的集合合并入y所在的集合var fx，fy：integer；begin fxfind_Father(x)；計(jì)算x所在樹(shù)的根節(jié)點(diǎn)fx fyfind_Father(y)；計(jì)算y所在樹(shù)的根節(jié)點(diǎn)fy Fatherfxfy；將fx的父節(jié)點(diǎn)設(shè)為fy BehindfxCountfy；計(jì)算fx的相對(duì)位置為Countfy Cou

18、ntfyCountfy+Countfx；計(jì)算新集合的節(jié)點(diǎn)數(shù)end； MoveShip 263、計(jì)算詢問(wèn)指令 procedure CheckShip(x，y：integer)；計(jì)算x節(jié)點(diǎn)和y節(jié)點(diǎn)的相對(duì)位置情況var f1，f2：integer；begin f1Find_Father(x)；計(jì)算x所在樹(shù)的根f1 f2Find_Father(y)；計(jì)算y所在樹(shù)的根f2 if f1f2 若x，y不在一棵樹(shù)中，則返回-1，否則返回x和y間隔的戰(zhàn)艦數(shù)then writeln(-1)else writeln(abs(Behindx-Behindy)-1)；end； CheckShip 27由此得出主程序：

19、for i1 to maxn do 初始時(shí)為每一艘戰(zhàn)艦建立一個(gè)并查集 begin Fatheri i； Counti 1； Behindi 0； end；for readln(CmdCount)； 讀指令數(shù) for i1 to CmdCount do 順序處理每一條指令 begin read(ch)；讀第i條指令的類型 case ch of M：begin readln(x，y)；MoveShip(x，y)； end；處理合并指令 C：begin readln(x，y)；CheckShip(x，y)； end；處理詢問(wèn)指令 end；case end；for 28線段樹(shù) 動(dòng)態(tài)處理可以映射在一個(gè)坐

20、標(biāo)軸上的一些固定線段，例如求并區(qū)間的總長(zhǎng)度，或者并區(qū)間的個(gè)數(shù)等等。 優(yōu)點(diǎn)：隨時(shí)插入一個(gè)區(qū)間或刪除一個(gè)已有區(qū)間，并同時(shí)用低耗費(fèi)維護(hù)需要的性質(zhì)。29線段樹(shù)-構(gòu)造思想下圖顯示了一個(gè)能夠表示1，10的線段樹(shù)： 30特點(diǎn)1、葉結(jié)點(diǎn)表示一個(gè)初等區(qū)間：a,b=a+1;每一個(gè)內(nèi)部結(jié)點(diǎn)b-a1;2、根為a,b的線段樹(shù)為T(a,b),其左子樹(shù)為T(a,(a+b)/2),右子樹(shù)為T(a+b)/2,b),直至細(xì)分為一個(gè)初等區(qū)間（葉結(jié)點(diǎn)）為止。 31線段樹(shù)的存儲(chǔ)結(jié)構(gòu)1、動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)TypeTnode=Treenode;Treenode=recordB,E:integer; 該區(qū)間為B,ECount:integer;記錄

21、覆蓋到B,E區(qū)間的線段條數(shù)LeftChild,Rightchild:Tnode;左右子樹(shù)的根End;322、靜態(tài)數(shù)據(jù)結(jié)構(gòu)用數(shù)組B，E，C，LSON，RSON。設(shè)一棵線段樹(shù)的根為v。那么Bv,Ev就是它所表示區(qū)間的界。Cv記錄覆蓋到B,E區(qū)間的線段的條數(shù)。LSONv，RSONv分別表示了它的左兒子和右兒子的根編號(hào)。 33線段樹(shù)的運(yùn)算1、建樹(shù) 從根對(duì)應(yīng)的區(qū)間a，b出發(fā)，每次分成兩個(gè)部分，分別建立對(duì)應(yīng)的左右子樹(shù)，直到面臨一個(gè)初等區(qū)間x,x+1。設(shè)一個(gè)全局變量n，來(lái)記錄一共用到了多少結(jié)點(diǎn)。開(kāi)始n=0procedure BUILD(a,b)Begin n n+1；v n；Bva；Evb；Cv0； if

22、b a1 thenbegin LSONvn+1；BUILD(a, （a+b）div 2)； RSONvn+1；BUILD(（a+b）div 2 ,b); end; end;342、插入線段將區(qū)間c,d插入線段樹(shù)T(a,b),并設(shè)T(a,b)的根編號(hào)為v procedure INSERT(c，d，v)Begin mid=(Bv+Ev) div 2;計(jì)算（a,b）的中間點(diǎn) if cBv and Evd若(c,d)覆蓋（a,b），則區(qū)間數(shù)+1 then Cv cv+1 else begin若（c,d）位于(a,b)的左半?yún)^(qū)間，則遞歸插入v的左子樹(shù)；若（c,d）位于(a,b)的右半?yún)^(qū)間，則遞歸插入v的

23、右子樹(shù) if cmid then INSERT(c,d;RSONv); end;end 353、刪除線段在線段樹(shù)T(a,b)中刪除區(qū)間c,d,并設(shè)T(a,b)的根編號(hào)為v：procedure DELETE(c,d;v) begin if cBv and Evd 若(c,d)覆蓋（a,b），則區(qū)間數(shù)-1 then Cv Cv-1 elsebegin若（c,d）位于(a,b)的左半?yún)^(qū)間，則遞歸刪除v的左子樹(shù)；若（c,d）位于(a,b)的右半?yún)^(qū)間，則遞歸刪除v的右子樹(shù) if c (Bv+Ev) div 2 then DELETE(c,d;RSONv); end；end 特別注意：只有曾經(jīng)插入過(guò)的區(qū)間

24、才能夠進(jìn)行刪除。這樣才能保證線段樹(shù)的維護(hù)是正確的。36 線段樹(shù)的動(dòng)態(tài)維護(hù)1、計(jì)算測(cè)度結(jié)點(diǎn)的測(cè)度Mv 指的是結(jié)點(diǎn)v所表示區(qū)間中線段覆蓋過(guò)的長(zhǎng)度。Cv0,Mv = Ev-Bv;Cv=0 且v是葉子結(jié)點(diǎn)，Mv=0；Cv=0 且v是內(nèi)部結(jié)點(diǎn)，Mv=MLSONv+MRSONv; 37連續(xù)線段數(shù)linev指的是區(qū)間中互不相交的線段條數(shù)。連續(xù)線段數(shù)并不能像測(cè)度那樣將兩個(gè)子結(jié)點(diǎn)中的連續(xù)線段數(shù)簡(jiǎn)單相加。于是我們引進(jìn)了兩個(gè)量lbdv，rbd v ，分別表示區(qū)間的左右兩端是否被線段覆蓋。 1 (左端點(diǎn)被線段覆蓋到)lbdv = 0 (左端點(diǎn)不被線段覆蓋到) 1 (右端點(diǎn)被線段覆蓋到)rbdv = 0 (右端點(diǎn)不被線

25、段覆蓋到)2、計(jì)算連續(xù)線段數(shù)38Lbd=1rbd=1line可以根據(jù)lbd，rbd定義如下： 1 (count 0) 0 (count=0 且結(jié)點(diǎn)為葉結(jié)點(diǎn)) Line= lch.Line + rch.Line - 1 (count=0 且結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)，lchrbd、 rchlbd都為1) lch.Line + rch.Line (count=0且結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)，hrbd, rchLbd不同時(shí)為1) 39線段樹(shù)的變形對(duì)點(diǎn)統(tǒng)計(jì)原線段數(shù)記錄基數(shù)的Cv這時(shí)就可以用來(lái)計(jì)算落在定區(qū)間內(nèi)的點(diǎn)個(gè)數(shù)了。原搜索路徑也發(fā)生了改變，不存在“跨越”的情況。同時(shí)插入每個(gè)點(diǎn)的時(shí)候都必須深入到葉結(jié)點(diǎn)，因此一般來(lái)說(shuō)都要有l(wèi)o

26、gn的復(fù)雜度。 應(yīng)用這樣的線段樹(shù)一方面是方便計(jì)數(shù)。另一方面由于它實(shí)際上是排序二叉樹(shù)，所以容易找出最大和最小來(lái)。 40例一商品促銷一位顧客要進(jìn)行n（1n5000）天的購(gòu)物，每天他會(huì)有一些帳單。每天購(gòu)物以后，他從以前的所有帳單中挑出兩張帳單，分別是面額最大的和面額最小的一張，并把這兩張帳單從記錄中去掉。剩下的帳單留在以后繼續(xù)統(tǒng)計(jì)。輸入的數(shù)據(jù)保證，所有n天的帳單總數(shù)不超過(guò)1000000并且每份帳單的面額值是1到1000000之間的整數(shù)。保證每天總可以找到兩張帳單。 41建立點(diǎn)線段樹(shù)，范圍是1，1000000，即每種面額的帳單設(shè)為一個(gè)葉結(jié)點(diǎn)。 如果CLSONv0,那么樹(shù)v中的最小值一定在它的左子樹(shù)上。

27、如果CRSONv0，它的最大值在右子樹(shù)上； 線段樹(shù)的深度為log 1000000 =2042改進(jìn)的辦法 用hash來(lái)保存每一種面額的帳單數(shù)目，然后對(duì)于一個(gè)具體的帳單（面額V），在線段樹(shù)中保存V/100的值，即把連續(xù)的100種面額的帳單看成是一組。由于V的范圍是1.1000000，所以線段樹(shù)中有10000個(gè)點(diǎn)。在找最大的數(shù)的時(shí)候，首先找到最小的組，然后在hash里對(duì)這個(gè)組進(jìn)行搜索，顯然這個(gè)搜索的規(guī)模不會(huì)超過(guò)100。由于線段樹(shù)變小了，所以樹(shù)的深度只有14左右，整個(gè)問(wèn)題的復(fù)雜度極限為N*14+n*14*100*2，對(duì)于問(wèn)題的規(guī)模來(lái)說(shuō)，仍然是高效率的。但這樣做比前種方法在一定程度上節(jié)省了空間。同時(shí)實(shí)際

28、上也提醒了我們對(duì)線段樹(shù)應(yīng)該加以靈活的應(yīng)用。43 農(nóng)夫Don要監(jiān)察他的N米乘N米(2 N 500,000)的正方形田園的圍欄。該圍欄的一角在原點(diǎn)(0，0)上，另一對(duì)角則在坐標(biāo)點(diǎn)(N，N)上, 圍欄的邊平行於X軸及Y軸。圍欄上有些支柱, 這些支柱分別立在圍欄的四個(gè)角上及圍欄的每條邊上每隔1米的地方, 因此整個(gè)圍欄上就有4N根支柱。這些支柱是垂直的，而且可以認(rèn)為其半徑為0。農(nóng)夫Don希望知道，當(dāng)他站在田園中的某一點(diǎn)時(shí)他可以看到的支柱的數(shù)量。 農(nóng)夫Don的田園內(nèi)有R塊巨石 (1 R 30,000) 阻礙他的視線。因?yàn)樗粔蚋?，無(wú)法從巨石上面望過(guò)去，因此有些支柱看不到。巨石的底部是一個(gè)面積不為零的凸多邊

29、形, 而多邊形的端點(diǎn)坐標(biāo)均為整數(shù)。巨石垂直地立在地上。巨石之間不重疊，互相之間不接觸， 巨石與農(nóng)夫Don或圍欄也不接觸。農(nóng)夫Don所站立的地方也不接觸圍欄，他也不會(huì)站在巨石內(nèi)或巨石上。 給定農(nóng)夫Don的圍欄大小, 其內(nèi)的巨石的位置及形狀，以及農(nóng)夫Don所站立的位置, 求出Don在該位置上可以看到的支柱數(shù)量。如果一根支柱在農(nóng)夫Don的視線上剛好和巨石的邊重疊，則農(nóng)夫Don是看不到該支柱的。 可視邊界44將統(tǒng)計(jì)農(nóng)夫位置“可視”的正方形四條邊界上的整點(diǎn)總數(shù)問(wèn)題，簡(jiǎn)化為計(jì)算農(nóng)夫站立位置到正方形下邊界線的可視點(diǎn)數(shù)的問(wèn)題。 我們按逆時(shí)針順序枚舉多邊形i的每一個(gè)頂點(diǎn)（1ir），不斷調(diào)整最左端的頂點(diǎn)序號(hào)min

30、和最右端的頂點(diǎn)序號(hào)max，并按照下述方法計(jì)算區(qū)間lt、rt若第j個(gè)頂點(diǎn)位于農(nóng)夫位置的上方(yijy01)，則分析：若第j個(gè)頂點(diǎn)位于農(nóng)夫位置的左方（xijx01），則設(shè)區(qū)間左端點(diǎn)lt為0；否則設(shè)區(qū)間右端點(diǎn)rt為n-145若第j個(gè)頂點(diǎn)位于農(nóng)夫位置的下方(yijy01)，則計(jì)算截點(diǎn)的x坐標(biāo)（hv為截點(diǎn)存在標(biāo)志）x0= x01+ *y01） lt= rt= 如果正方形下邊界線上不存在截點(diǎn)（hv=false），是不是意味著正方形下邊界線上的頂點(diǎn)都是可視點(diǎn)呢？不一定 即過(guò)農(nóng)夫位置引垂直于X軸的射線，如果與凸多邊形i最左的頂點(diǎn)min、最右的頂點(diǎn)max所連線段不相交，則凸多邊形i不擋住正方形下邊界線上的任何整

31、點(diǎn)；否則凸多邊形i擋住了正方形下邊界線。相交的標(biāo)志是農(nóng)夫位置的x坐標(biāo)位于頂點(diǎn)min的x坐標(biāo)和頂點(diǎn)max的x坐標(biāo)之間（(ximinx01ximax)）且交點(diǎn)在農(nóng)夫位置之下（yimin+ *(x01-ximin)y01） 46構(gòu)建區(qū)間表xx和tp 區(qū)間表xx。xx存儲(chǔ)正方形下邊界線上被r個(gè)凸多邊形擋住的所有區(qū)間； 區(qū)間表元素的類型tp。其中 tpi=1，表明排序前的xxi為區(qū)間左端點(diǎn)的x坐標(biāo)； tpi=-1，表明排序前的xxi為區(qū)間右端點(diǎn)的x坐標(biāo)， lg:=0;區(qū)間表的長(zhǎng)度清零 for i:=1 to r do依次處理每個(gè)凸多邊形 begin 計(jì)算正方形下邊界線被凸多邊形i擋住的區(qū)間lt,rt x

32、xlg+1:=lt; xxlg+2:=rt;將lt,rt存入?yún)^(qū)間表 tplg+1:=1; tplg+2:=-1; inc(lg,2) end;for47計(jì)算正方形下邊界線上被擋住的整點(diǎn)數(shù)a1 目標(biāo)是計(jì)算正方形下邊界線上被各個(gè)區(qū)間的線段覆蓋過(guò)的長(zhǎng)度a1（簡(jiǎn)稱a1為測(cè)度）。這里有兩種做法： 建立線段樹(shù)，最后統(tǒng)計(jì)測(cè)度；將xx和tp中所有區(qū)間的端點(diǎn)lt,rt進(jìn)行排序，根據(jù)tp表自左而右掃描一遍，利用統(tǒng)計(jì)點(diǎn)值的和s統(tǒng)計(jì)測(cè)度a1：48 sort(1,lg);對(duì)區(qū)間表進(jìn)行分治排序 s:=0; al:=0;初始化點(diǎn)值和與測(cè)度 for i:=1 to lg do(從左到右掃描區(qū)間表的每一個(gè)元素) if tpi=

33、1一個(gè)新區(qū)間開(kāi)始 then begin if s=0 then lt:=xxi;若點(diǎn)值和為0，則該截點(diǎn)作為連續(xù)區(qū)間的左端點(diǎn) inc(s) 點(diǎn)值和+1 endthen else begin(若當(dāng)前區(qū)間結(jié)束，統(tǒng)計(jì)測(cè)度) if s=1 then al:=al+trunc(xxi)-trunc(lt-zero)+ord(lt1e-6); dec(s) 點(diǎn)值和-1 end;else 顯然，正方形下邊界線上的可視點(diǎn)數(shù)為n-a1。 49主程序 輸入信息； ans:=0; for t:=1 to 4 do分別處理正方形四條邊 begin 構(gòu)建區(qū)間表xx和tp； 計(jì)算正方形下邊界線上被擋住的整點(diǎn)數(shù)a1； ans

34、:=ans+n-al;將農(nóng)夫所能看到的正方形t邊上的支柱數(shù)n-a1記入ans for i:=0 to r do將每一個(gè)凸多邊形逆時(shí)針轉(zhuǎn)90度，以便將下一條邊旋轉(zhuǎn)至下底邊 for j:=1 to pi do begin x0:=xij;y0:=yij;xij:=n-trunc(y0); yij:=trunc(x0) endfor end;for 輸出農(nóng)夫Don所能看到的支柱數(shù)ans ； 50線段樹(shù)的總結(jié)1、線段樹(shù)經(jīng)過(guò)左右分割以后具有二叉排序樹(shù)的性質(zhì)；2、線段樹(shù)的建立方式非常適用于處理線段，對(duì)于點(diǎn)的問(wèn)題，亦可以推廣應(yīng)用3、線段樹(shù)上的一個(gè)結(jié)點(diǎn)分裂為兩個(gè)半?yún)^(qū)間的時(shí)候?qū)嶋H上是通過(guò)一個(gè)中間點(diǎn)來(lái)分割的；4、

35、在線段樹(shù)上需要設(shè)立左右指針；結(jié)點(diǎn)表示區(qū)間，但處理點(diǎn)的時(shí)候不需要保留這樣的區(qū)間。51一定范圍內(nèi)計(jì)數(shù)問(wèn)題的特點(diǎn)1 描述簡(jiǎn)單2 要求對(duì)數(shù)據(jù)動(dòng)態(tài)維護(hù)，動(dòng)態(tài)計(jì)算3 解決手段：特殊的統(tǒng)計(jì)模式和結(jié)構(gòu)怎樣用靜態(tài)方法解決動(dòng)態(tài)統(tǒng)計(jì)的問(wèn)題？52一種靜態(tài)統(tǒng)計(jì)方法例題IOI2001 MOBILES ：在一個(gè)N*N的方格中，開(kāi)始每個(gè)格子里的數(shù)都是0?，F(xiàn)在動(dòng)態(tài)地提出一些問(wèn)題和修改：提問(wèn)的形式是求某一個(gè)特定的子矩陣(x1,y1)-(x2,y2)中所有元素的和；修改的規(guī)則是指定某一個(gè)格子(x,y)，在(x,y)中的格子元素上加上或者減去一個(gè)特定的值A(chǔ)。現(xiàn)在要求你能對(duì)每個(gè)提問(wèn)作出正確的回答。1N1024,提問(wèn)和修改的總數(shù)可能達(dá)到

36、60000條。 53一維序列求和設(shè)序列的元素存儲(chǔ)在a中，a的下標(biāo)是1.n的正整數(shù)，需要?jiǎng)討B(tài)地更新某個(gè)ax的值，同時(shí)要求出ax1到ay1這一段所有元素的和（sum(1,y1)-sum(1,x1-1)）。 54對(duì)于序列a1.n，設(shè)一個(gè)數(shù)組C1.n 其中Ci=ai- 2k +1+ai k為i在二進(jìn)制下末尾0的個(gè)數(shù)。例如10000 k =4 C10000 =a10001+ a10000 計(jì)算Cx對(duì)應(yīng)的2k LOWBIT（x）=2k =x and (x xor (x-1)55修改一個(gè)ax的值 與C的哪些下標(biāo)變量p相關(guān)？ 例如x=76=(1001010)2，從形式上進(jìn)行觀察，可以得到： p1= 10010

37、10 p2= 1001100 p3= 1010000 p4= 1100000 p5=修改Cp1,Cp2,56procedure UPDATA(x,A)begin px while (p0) do begin ansans+Cp pp-LOWBIT(p) endreturn ansend Cp=ap- 2k +1+ap下一個(gè)p=x- 2k58推廣為原來(lái)的二維問(wèn)題，把C構(gòu)造成 Cx，y，其每一維定義與原來(lái)相同。推廣后算法：兩層嵌套，一次維護(hù)費(fèi)用為O(log2n)59在解決點(diǎn)統(tǒng)計(jì)問(wèn)題時(shí)，多考慮靜態(tài)二叉排序樹(shù)二分法的虛擬實(shí)現(xiàn)樹(shù)60集合3，4，5，8，19，6 靜態(tài)二叉排序統(tǒng)計(jì)樹(shù)實(shí)現(xiàn)是把所有要處理的點(diǎn)坐

38、標(biāo)離散化，形成一個(gè)排序的映射，例如我們稱為X映射，并且設(shè)其中一共有n個(gè)不同的對(duì)象。例如在上例中，X=3，4，5，6，8，19，n=6。 第一個(gè)點(diǎn)61靜態(tài)二叉排序統(tǒng)計(jì)樹(shù)與一般二叉排序樹(shù)的區(qū)別1、一般二叉排序樹(shù)的結(jié)構(gòu)由輸入順序決定的2、靜態(tài)二叉排序統(tǒng)計(jì)樹(shù)的結(jié)構(gòu)由區(qū)間中間點(diǎn)決定，因此需要預(yù)先排序62把X映射中的點(diǎn)值填入到樹(shù)中，使它有上面的構(gòu)造。這里我們選擇靜態(tài)結(jié)構(gòu)作為對(duì)二叉樹(shù)的支持。將二叉樹(shù)的結(jié)點(diǎn)從上到下，從左到右進(jìn)行編號(hào)，并令根結(jié)點(diǎn)的編號(hào)為1。即上圖中對(duì)應(yīng)的編號(hào)應(yīng)該是：對(duì)于任何一個(gè)編號(hào)為i的結(jié)點(diǎn)，它的左兒子編號(hào)自然為i*2，右兒子編號(hào)為i*2+1。現(xiàn)在要把X的映射填入到數(shù)組V中去。V1.n應(yīng)該保存

39、相應(yīng)位置上的點(diǎn)值。注意到對(duì)V對(duì)應(yīng)的二叉樹(shù)進(jìn)行中序遍歷的結(jié)果就對(duì)應(yīng)X中的映射，所以可以通過(guò)遞歸的方法建立V：63構(gòu)造過(guò)程1 遞歸：建立所有點(diǎn)坐標(biāo)的映射Xp 0 作為X映射中的指針procedure BUILD(ID: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) 64構(gòu)造過(guò)程2 非遞歸 方法，依次找出當(dāng)前點(diǎn)的后繼點(diǎn)的下標(biāo) 第一個(gè)點(diǎn)first一定為最下層最左邊的一個(gè)位置,若n個(gè)點(diǎn)有L層,則first=2 L-1function fi

40、rst:integerbeginlevel 1, tot = 2while (tot-1n) do begin levellevel+1；tottot*2 end return tot div 2end65若當(dāng)前的點(diǎn)位置為now：如果它有右兒子，即now*2+1x) thennownow*2x在now的左子樹(shù)方向 else nownow*2+1x在now的右子樹(shù)方向until falseEnd刪除 的方法是類似的672、插入時(shí)，計(jì)算每個(gè)結(jié)點(diǎn)以及其左子樹(shù)上頂點(diǎn)的總數(shù)設(shè)LESS表示值小于等于根結(jié)點(diǎn)值的總數(shù) (LESSI=SUMI-SUMI*2+1)：procedure INSERT1(x)Begi

41、nnow 1repeat if (xx) then nownow*2 計(jì)算左兒子指針 else nownow*2+1計(jì)算右兒子指針 until falseend68利用二叉排序統(tǒng)計(jì)樹(shù)解決MOBILES問(wèn)題這個(gè)過(guò)程與前一個(gè)大同小異。實(shí)際上LESSI=SUMI-SUMI*2+1。舉這個(gè)例子在于說(shuō)明利用二叉排序樹(shù)的結(jié)構(gòu)，是很容易結(jié)合具體的問(wèn)題進(jìn)行變化的。我們對(duì)其變化，甚至也可以利用來(lái)解決MOBILES問(wèn)題。只要將剛才LESS的定義作一點(diǎn)變化，令它為根及其左樹(shù)上所有點(diǎn)上的權(quán)和。如果要在ax上增加A。可以很容易得到：69procedure INSERT2(x,A)beginnow 1repeat if

42、(xx) then nownow*2 else nownow*2+1until falseend70求a1.x的元素和SUM(x)function SUM(x):longintbeginans 0now 1repeat if (Vnowx) then nownow*2 else nownow*2+1until falsereturn ansend 71例題采礦(KOP) 金礦的老師傅年底要退休了。經(jīng)理為了獎(jiǎng)賞他的盡職盡責(zé)的工作，決定送他一塊長(zhǎng)方形地。長(zhǎng)度為S，寬度為W。老師傅可以自己選擇這塊地。顯然其中包含的采金點(diǎn)越多越好。你的任務(wù)就是計(jì)算最多能得到多少個(gè)采金點(diǎn)。如果一個(gè)采金點(diǎn)的位置在長(zhǎng)方形的

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

44、1),(3,+1),(6,-1),(5,+1),(8,-1),(9,+1),(12,-1), (9,+1),(12,-1),2、將他們按照y的坐標(biāo)排序，得(1,+1),(3,+1),(4,-1), (5,+1)， (6,-1), (8,-1), (9,+1), (9,+1),(12,-1), (12,-1)3、把后面的標(biāo)號(hào)反映在一個(gè)y坐標(biāo)的映射上，然后從低到高求和 75坐標(biāo)下的求和，這些和中最大的一個(gè)就是該帶狀區(qū)域中一個(gè)包含最多點(diǎn)數(shù)的矩形 在插入或者刪除一個(gè)點(diǎn)事件之后，能夠維持坐標(biāo)下的值；能夠在很短時(shí)間內(nèi)得到中最大的一個(gè)值。 76實(shí)現(xiàn)：SUMnow對(duì)應(yīng)子樹(shù)上所有+1，-1標(biāo)號(hào)的和。實(shí)現(xiàn)極簡(jiǎn)單M

45、AXSUMnow，子樹(shù)上和最大的一個(gè)前綴值。MAXSUM1是一種狀態(tài)下得到最優(yōu)解。如何維護(hù)？MAXSUM有哪幾種可能？ 1 最大值在左樹(shù)上； 2 最大值正好包含根結(jié)點(diǎn)； 3 最大值在右樹(shù)上。 77自下而上維護(hù)樹(shù)的特性procecure INSERT(y,k)begin now 1 repeat 向下找到y(tǒng)所在的結(jié)點(diǎn) if Vnow=y then breakif Vnowy then nownow*2+1 else nownow*2until false; Repeat 再向上，對(duì)路徑上的每個(gè)點(diǎn)的SUM和MAXSUM進(jìn)行修改 SUMnowSUMnow+k MAXSUMnowMax 對(duì)取得連續(xù)和最

46、大值的3種情況 進(jìn)行決策 MAXSUMnow*2, 最大值在左樹(shù)上 SUMnow-SUMnow*2+1, 最大值正好包含根結(jié)點(diǎn) SUMnow-SUMnow*2+1+MAXSUMnow*2+1 最大值在右樹(shù)上 now now div 2 until now = 0 End;78二分法虛擬實(shí)現(xiàn)樹(shù)二叉樹(shù)使用之前必須構(gòu)造出一個(gè)空的二叉樹(shù) 對(duì)于任何一個(gè)有序表，在對(duì)其進(jìn)行二分查找時(shí)，實(shí)際上就等于在一個(gè)二叉樹(shù)上進(jìn)行查找 79對(duì)于一個(gè)有序表1，3，4，8，9的二分查找，等價(jià)于在如下圖的二叉排序樹(shù)上進(jìn)行查找： m取中間位置值，即為一棵樹(shù)的樹(shù)根，它左邊的所位置值即l,m-1構(gòu)成了其左子樹(shù)上的形態(tài)，而m+1,r構(gòu)成

47、了右子樹(shù)上的形態(tài) 。等價(jià)的二叉排序樹(shù)是平衡二叉樹(shù)。最多l(xiāng)ogn次查找就可以指定的結(jié)點(diǎn)。 80舉插入結(jié)點(diǎn)的例子，來(lái)說(shuō)明這種虛實(shí)現(xiàn)的方法設(shè)LESS表示根及其左樹(shù)上結(jié)點(diǎn)的個(gè)數(shù)： procedure INSERT(x)beginl1,rnwhile (l=r) do begin m=(l+r) div 2 if x=Vm then LESSmLESSm+1 if x =Vm then break if xVm then r m 1 else lm+1 endend 81例4在一個(gè)平面直角坐標(biāo)系上有n個(gè)點(diǎn)，n最多為15000，要求每個(gè)點(diǎn)的左下方有多少個(gè)點(diǎn)，也就是說(shuō)對(duì)于每個(gè)點(diǎn)xi,yi，求滿足xjxi并且

48、yjyi的j的個(gè)數(shù)。1、按照x為第一關(guān)鍵字、y為第二關(guān)鍵字的順序?qū)λ悬c(diǎn)進(jìn)行升序排列2、對(duì)排好序的y坐標(biāo)建立映射關(guān)系，放在V數(shù)組中，并按照先前點(diǎn)排序的順序依次把各個(gè)y插入到計(jì)數(shù)用的LESS中去，同時(shí)就可以得到一個(gè)點(diǎn)左下方的值。 82function INSERT-AND-GET(y):integerbegin l1,rn ans0 while (l=r) do begin m=(l+r) div 2 if y=Vm then ansans+LESSm if y =Vm then break if yVm then r m 1 else lm+1 end return ansEnd 復(fù)雜度為O(

49、logn) 83例題最長(zhǎng)下降序列給定一個(gè)整數(shù)序列a，求最長(zhǎng)下降序列的長(zhǎng)度。設(shè)mi為ai的前綴中（包括ai ）的最長(zhǎng)下降序列的長(zhǎng)度。該序列中ai前的整數(shù)為api1、最基本的解決方法O（n2)84 對(duì)P進(jìn)行特殊的限制，即在所有等價(jià)的(相同長(zhǎng)度)決策j中，P選擇aj最大的那一個(gè) 在處理完a1.x-1之后，對(duì)于所有長(zhǎng)度為Mx-1的下降序列，Px的決策只跟其中末尾最大的一個(gè)有關(guān)。 用另外一個(gè)動(dòng)態(tài)變化的數(shù)組b，當(dāng)我們計(jì)算完了ax之后，a1.x中得到的所有下降序列按照長(zhǎng)度分為L(zhǎng)類，每一類中只需要一個(gè)作為代表，這個(gè)代表在這個(gè)等價(jià)類中末尾的數(shù)最大，我們把它記為bj,1jL。 處理當(dāng)前的一個(gè)數(shù)ax，我們無(wú)需和前面

50、的aj（1jx-1）作比較，只需要和bj（1jL)進(jìn)行比較。 85 首先，如果ax=b1，這時(shí)ax 僅能構(gòu)成長(zhǎng)度為1的下降序列，同時(shí)它又必然是最大的，所以它作為b1的代表,b1=ax。 如果前面的情況都不存在，我們肯定可以找到一個(gè)j,2jL,有bj-1ax,bjax，這時(shí)分析，ax必然接在bj-1后面，行成一個(gè)新的長(zhǎng)度為j的序列。 86 這幾種情況實(shí)際上都可以歸結(jié)為：處理ax，令bL+1為無(wú)窮小，從左到右找到第一個(gè)位置j，使bjax,然后則只要將bj=ax,如果j=L+1,則L同時(shí)增加。x處以前對(duì)應(yīng)的最長(zhǎng)下降序列長(zhǎng)度為Mx=j。 順序查找L 0； 下降序列的最大長(zhǎng)度初始化for x1 to n

51、 do beginbL+1無(wú)窮小 j1從左到右找到第一個(gè)使得bjax的位置j while (bjax) do jj+1 bjax if jL then Lj end 87順序查找更改成二分法查找 L0 下降序列的最大長(zhǎng)度初始化for i1 to n do begin j1;kL;在b1.bL中二分法查找第一個(gè)使得bjax的位置j while (jk) do改為二分法查找 begin m (j+k) div 2; if bmai then jm+1 else km-1; end if jL then LL+1；bjai end88衛(wèi)星探測(cè)（Detect）【問(wèn)題描述】A國(guó)最近檢測(cè)到了B國(guó)內(nèi)有不正常

52、的輻射，經(jīng)調(diào)查發(fā)現(xiàn)，這是因?yàn)锽國(guó)正在耗資百億研制新式武器連環(huán)陣?？墒?，由于B國(guó)對(duì)此武器的高度保密措施，A國(guó)的間諜甚至無(wú)法確定出連環(huán)陣的具體位置。不過(guò)，A國(guó)的衛(wèi)星還是可以找出連環(huán)陣所在的基地的。我們現(xiàn)在知道該基地是一個(gè)邊上含有放射性物質(zhì)的凸多邊形。經(jīng)研究發(fā)現(xiàn)，在這個(gè)凸多邊形所在的平面內(nèi)，它具有如下性質(zhì)： 包含坐標(biāo)原點(diǎn)；任意兩條邊不在同一直線上；沒(méi)有和x軸或y軸平行的邊； 所有頂點(diǎn)的x坐標(biāo)和y坐標(biāo)都是整數(shù)。現(xiàn)在A國(guó)可以通過(guò)衛(wèi)星發(fā)出無(wú)限大的扇形探測(cè)波，與該凸多邊形所在平面交于一條直線。不過(guò)該直線不是與x軸平行，就是與y軸平行。通過(guò)反射信號(hào)，我們可以確定該直線與凸多邊形的交點(diǎn)個(gè)數(shù)和所有交點(diǎn)的坐標(biāo)（如果

53、有的話）。現(xiàn)在，需要你寫(xiě)一個(gè)程序，通過(guò)控制衛(wèi)星發(fā)出的探測(cè)波來(lái)確定這個(gè)凸多邊形。891、通過(guò)二分法確定凸多邊形的左端頂點(diǎn)和右端頂點(diǎn) 我們通過(guò)readx（at，nm，y1，y2）過(guò)程詢問(wèn)直線x=at與凸多邊形交點(diǎn)的個(gè)數(shù)nm和兩個(gè)交點(diǎn)坐標(biāo)y1、y2。 rcdat,1.3為x=at與凸多邊形交點(diǎn)的y坐標(biāo)和交點(diǎn)個(gè)數(shù)Procedure readx(at:longint;var nm:longint;var y1,y2:double);詢問(wèn)直線x=at與凸多邊形的相交情況begin if rcdat,10 如果以前詢問(wèn)過(guò)，則直接返回詢問(wèn)結(jié)果 then begin nm:=round(rcdat,3);y1:

54、=rcdat,1; y2:=rcdat,2 endthen else begin nm:=ask_x(at,y1,y2);詢問(wèn)直線x=at與凸多邊形的交點(diǎn) if y1y2y1和y2按照遞增排列 then begin y1:=y1+y2;y2:=y1-y2;y1:=y1-y2 end;then rcdat,1:=y1;rcdat,2:=y2; rcdat,3:=nm記錄詢問(wèn)結(jié)果 endelseend; readx 90fillchar(rcd,sizeof(rcd),0); 詢問(wèn)結(jié)果初始化 hd:=-10000; tl:=0; md:=0;設(shè)定左端頂點(diǎn)所在的區(qū)間，交點(diǎn)個(gè)數(shù)初始化 while tr

55、ue do begin md:=(hd+tl) div 2;將詢問(wèn)的直線設(shè)在區(qū)間中點(diǎn)處 readx(md,nm,y1,y2);計(jì)算該直線與凸多邊形的交點(diǎn)y1、y2和交點(diǎn)個(gè)數(shù)nm if nm=1 then break;若僅有一個(gè)交點(diǎn)，則退出循環(huán) if nm=0 then hd:=md+1若沒(méi)有交點(diǎn)，則取右區(qū)間 else tl:=md-1若有兩個(gè)交點(diǎn)，則取左區(qū)間 end;while x1:=md;y1:=round(y1);確定左端頂點(diǎn)的坐標(biāo)hd:=0; tl:=10000; md:=0;設(shè)定右端頂點(diǎn)所在的區(qū)間，交點(diǎn)個(gè)數(shù)初始化while true do begin md:=(hd+tl) div

56、2;將詢問(wèn)的直線設(shè)在區(qū)間中點(diǎn)處 readx(md,nm,y1,y2);計(jì)算該直線與凸多邊形的交點(diǎn)y1、y2和交點(diǎn)個(gè)數(shù)nm if nm=1 then break;若僅有一個(gè)交點(diǎn)，則退出循環(huán) if nm=2 then hd:=md+1若有兩個(gè)交點(diǎn)，則取右區(qū)間 else tl:=md-1若沒(méi)有交點(diǎn)，則取左區(qū)間 end;while顯然，通過(guò)上述運(yùn)算后，（x1，y1）為凸多邊形最左方頂點(diǎn)的坐標(biāo)；（md，y1）為凸多邊形最右方頂點(diǎn)的坐標(biāo) 912、按照先下方、后上方的順序計(jì)算凸多邊形的頂點(diǎn)坐標(biāo) 在找出凸多邊形的左端點(diǎn)和右端點(diǎn)之后，由左端點(diǎn)開(kāi)始，沿著上方的路徑和下方的路徑，逐步找出凸多邊形的其他頂點(diǎn)。其中每次

57、從當(dāng)前頂點(diǎn)（X0，Y0）開(kāi)始，先詢問(wèn)直線XX01確定下一條邊的斜率tg=y-y0 然后二分地尋找斜率開(kāi)始發(fā)生變化的頂點(diǎn)，這個(gè)頂點(diǎn)就是下一個(gè)頂點(diǎn) 92計(jì)算與凸多邊形的下一個(gè)頂點(diǎn)相鄰的兩條直線每次二分查找的邊界不必定得過(guò)大。由于之前我們已經(jīng)進(jìn)行過(guò)了一些詢問(wèn)，詢問(wèn)的結(jié)果存儲(chǔ)在rcd數(shù)組中。我們可以充分利用已得到的信息，通過(guò)rcd數(shù)組限制邊界范圍，即確定一個(gè)頂點(diǎn)在rcd數(shù)組中哪兩條相鄰直線之間，將這兩條直線設(shè)為下一次詢問(wèn)的邊界。設(shè)目前已得出凸多邊形的第n個(gè)頂點(diǎn)為（xn，yn），尚待計(jì)算的下一個(gè)頂點(diǎn)在rcd數(shù)組中的直線x=lt和直線x=rt之間，這兩條相鄰直線與凸多邊形相交的情況存儲(chǔ)在rcdlt和rcd

58、rt中。凸多邊形與直線x=lt的交點(diǎn)（lt，rcdlt，1）(計(jì)算上方頂點(diǎn)時(shí)交點(diǎn)為（lt，rcdlt，2）)連接（xn，yn）的直線斜率 =tg；凸多邊形與直線x=rt的交點(diǎn)（rt，rcdrt，1）(計(jì)算上方頂點(diǎn)時(shí)交點(diǎn)為（rt，rcdrt，2）)連接（xn，yn）的直線斜率 tg。我們從xn+1出發(fā)，由左而右計(jì)算直線x=lt；從凸多邊形的右端點(diǎn)的x坐標(biāo)-1出發(fā)，由右而左計(jì)算直線x=rt：93結(jié)合跨度kd二分查找 由于直線x=lt和直線x=rt是目前詢問(wèn)到的兩條直線，因此其在x軸的間隔完全可能大于1。如何以盡可能少的詢問(wèn)次數(shù)找到位于兩條直線間的凸邊形頂點(diǎn)（xn+1，yn+1）呢？ 凸邊形的邊（x

59、n，yn），（xn+1，yn+1）經(jīng)過(guò)點(diǎn)（xn+1，y），由此得出該邊的斜率為tg=y-yn。由于凸邊形頂點(diǎn)（xn+1，yn+1）的坐標(biāo)為整數(shù)，因此位于x=xn與x=xn+1間的有些直線不會(huì)與斜率tg的直線交與整數(shù)坐標(biāo)，這些直線不必詢問(wèn)。 為了盡可能將這些頂點(diǎn)從詢問(wèn)范圍內(nèi)剔除，我們將斜率tg化為一個(gè)既約分?jǐn)?shù)A/B，把B（而不是1）作為詢問(wèn)的“跨度”，即每一次詢問(wèn)，x直線的間隔距離為B。這個(gè)B值可以枚舉。 我們通過(guò)函數(shù)get_kd(tg)計(jì)算詢問(wèn)的“跨度”Bfunction get_kd(x:double):longint;求跨度 var i:longint; begin get_kd:=0;

60、for i:=1 to 20000 do if abs(x*i-round(x*i)1e-6 then begin get_kd:=i; exit endend; get_kd 94按照先下方、后上方的順序計(jì)算凸多邊形的頂點(diǎn)坐標(biāo) tx:=md;n:=1; 記下凸多邊形左端的x坐標(biāo) repeat從頂點(diǎn)1出發(fā)，計(jì)算凸多邊形下方各邊的頂點(diǎn)坐標(biāo) readx(xn+1,nm,y1,y2);計(jì)算（xn，yn）至（xn+1，y1）的斜率tg tg:=y1-yn;kd:=get_kd(tg);計(jì)算跨度kd lt:=xn; rt:=tx;與第n+1個(gè)頂點(diǎn)相鄰的兩條直線初始化 for i:=xn+1 to tx