劃分樹(算法總結(jié))

1、用來標(biāo)記和中間值相等的，且分到左孩子的數(shù)的個(gè)數(shù)。動(dòng)態(tài)求解區(qū)間最大數(shù)的問題揭開它神秘的面紗，探尋真理的奧妙。小志。這偏文章主要總結(jié)劃分樹解決區(qū)間第K大數(shù)的問題。一些內(nèi)容并非原創(chuàng)，全部內(nèi)容只供參考交流！劃分樹劃分樹的定義劃分樹定義為，她的每一個(gè)節(jié)點(diǎn)保存區(qū)間所有元素，元素排列順序與原數(shù)組（輸入）相同，但是，兩個(gè)子樹的元素為該節(jié)點(diǎn)所有元素排序后-個(gè)進(jìn)入左子樹，其余的到右子樹，同時(shí)維護(hù)一個(gè)num域，表示t這些點(diǎn)有多少進(jìn)入了左子樹。（摘自某牛人的博客，為了和下面的算法統(tǒng)一，稍有變動(dòng)）劃分樹的Sample.如果由下而上看這個(gè)圖，我們就會發(fā)現(xiàn)他和歸并排序的（歸并樹）的過程很類似，或者說正好相反。歸并樹是由下而

2、上的排序，而她確實(shí)由上而下的排序（觀察4的運(yùn)動(dòng)軌跡，我們可以猜到劃分樹的排序也是一種穩(wěn)定的排序方法，這里不是說明的重點(diǎn)，不予證明）。但這正是她可以用來解決第k大元素的理由所在。（具體的理由，寫完再補(bǔ)）扌非序后原數(shù)組丄6旦4曼2巳冬|空呼0劃分樹的存儲結(jié)構(gòu)（采用層次存儲結(jié)構(gòu)（由下而上，由左到右，每層兩個(gè)孩子，見上圖）對原來集合中的元素排序后的值。記錄第層當(dāng)前位置的元素的值記錄元素所在區(qū)間的當(dāng)前位置之前進(jìn)入左孩子的個(gè)數(shù)記錄比當(dāng)前元素小的元素的和。劃分樹的建立Build劃分樹的建立和普通的二叉樹的建立過程差不多，仍然采取中序的過程（先根節(jié)點(diǎn)，然后左右孩子）。樹的建立相對比較簡單，我們依據(jù)的是已經(jīng)排好

3、序的位置進(jìn)行建樹，所以先用快排將原集合牌還序。要維護(hù)每個(gè)節(jié)點(diǎn)的num域。LBoy_ 初始時(shí)，假定當(dāng)前區(qū)間有個(gè)和相等。先踢掉比中間值小的剩下的就是要插入到左邊的初始一個(gè)子樹。初始區(qū)間下一個(gè)節(jié)點(diǎn)。如果大于，肯定進(jìn)入右孩子，否則，判斷是否還有相等的應(yīng)該進(jìn)入左孩子的,沒有，就直接進(jìn)入右孩子，否則進(jìn)入左孩子，同時(shí)更新節(jié)點(diǎn)的域和域LBoy_ #LBoy_ 劃分樹的查找在區(qū)間上查找第k大的元素,1.2.3.同時(shí)返回她的位置和去見里面小于a,b的所有數(shù)的和。二，即，進(jìn)入p的左孩子的個(gè)數(shù)已經(jīng)超過k個(gè)，那么就往左孩子里Iftt,曲即，進(jìn)入p的左孩子的個(gè)數(shù)小于k個(gè)，那么就要往右孩子查找如果面查找，同時(shí)更新如果第ks（s表示進(jìn)入左孩子的個(gè)數(shù)）個(gè)元素。同時(shí)要更新sun域。詳細(xì)的過程見代碼和注釋：在區(qū)間上查找第大元素，同時(shí)返回區(qū)間中小于第大元素的和。LBoy_ #LBoy_ #到達(dá)葉子就找到該元素，返回。LBoy_ 記錄區(qū)間中進(jìn)入左孩子的元素的個(gè)數(shù)。記錄區(qū)間中計(jì)入左孩子的元素的個(gè)數(shù)。記錄區(qū)間中小于第大元素的值的和。表示中分到右孩子的個(gè)數(shù)表示中分到右孩子的個(gè)數(shù)。區(qū)間端點(diǎn)點(diǎn)重合的情況不一定為，所以要單獨(dú)考慮進(jìn)入左孩子，同時(shí)更新區(qū)間端點(diǎn)值。劃分樹的應(yīng)用pku_2401_K-thNumberhdu_2