統(tǒng)計(jì)的力量

1、清華大學(xué) 張昆瑋,統(tǒng)計(jì)的力量——線段樹(shù)全接觸,2024年3月10日,清華大學(xué) 張昆瑋,2,許多算法的本質(zhì)是統(tǒng)計(jì),根據(jù) D. E. Knuth 的分類(lèi)方法計(jì)算機(jī)算法可以分為兩類(lèi)：數(shù)值算法與非數(shù)值算法其中的非數(shù)值算法包括：索引分類(lèi)統(tǒng)計(jì)……,2024年3月10日,清華大學(xué) 張昆瑋,3,線段樹(shù)？,大家都說(shuō)：……常數(shù)很大？不好寫(xiě)？難調(diào)試？想不到？……,2024年3月10日,清華大學(xué) 張昆瑋,4,一個(gè)悲劇,POJ上的某題

2、，時(shí)限很緊……大家都用樹(shù)狀數(shù)組，但是有人只會(huì)用線段樹(shù)呢？而且我可以輕易改出一道不能用樹(shù)狀數(shù)組的題在線段樹(shù)一次次TLE后，有一個(gè)ID發(fā)帖抱怨“下次寫(xiě)一個(gè)匯編版非遞歸線段樹(shù)，再超時(shí)？”可是大家都知道，超時(shí)的代碼已經(jīng)2k了。其實(shí)我寫(xiě)的就是線段樹(shù)。很快，而且不到1k。,2024年3月10日,清華大學(xué) 張昆瑋,5,線段樹(shù)用于統(tǒng)計(jì),運(yùn)行速度快適應(yīng)能力強(qiáng)編寫(xiě)方便結(jié)構(gòu)簡(jiǎn)單容易調(diào)試關(guān)鍵在于靈活實(shí)現(xiàn),線段樹(shù)，從何而來(lái)？,為什么在《算

3、法導(dǎo)論》和黑書(shū)中都難見(jiàn)到其蹤跡？,2024年3月10日,清華大學(xué) 張昆瑋,6,2024年3月10日,清華大學(xué) 張昆瑋,7,計(jì)算幾何！,計(jì)算幾何在長(zhǎng)期的發(fā)展中，誕生了許多實(shí)用的數(shù)據(jù)結(jié)構(gòu)。區(qū)間查詢(xún)，穿刺查詢(xún)都是計(jì)算幾何解決的問(wèn)題作為特例中的特例，線段樹(shù)解決的問(wèn)題是：一維空間上的幾何統(tǒng)計(jì)高維推廣（kd-tree & …）可以進(jìn)行正交查詢(xún)由于競(jìng)賽中涉及計(jì)算幾何的內(nèi)容有限，不展開(kāi),2024年3月10日,清華大學(xué) 張昆瑋,8

4、,真正有用的是“點(diǎn)樹(shù)”,線段樹(shù)把數(shù)軸分成區(qū)間來(lái)處理如[8,10), [10,11), …實(shí)際上我們面對(duì)的往往是離散量競(jìng)賽中出現(xiàn)的線段樹(shù)往往因此退化為“點(diǎn)樹(shù)”即，最底層的線段只包含一個(gè)點(diǎn)：如：[8,9)中只有整點(diǎn)8而已在之后的討論中，我們不再區(qū)別“點(diǎn)樹(shù)”與線段樹(shù),第一印象,如果我給MM的第一印象不到80分的話……是不是老老實(shí)實(shí)地早點(diǎn)罷手比較好？,2024年3月10日,清華大學(xué) 張昆瑋,9,2024年3月10日,清華大學(xué) 張

5、昆瑋,10,最經(jīng)典的問(wèn)題：區(qū)間和,2024年3月10日,清華大學(xué) 張昆瑋,11,核心思想：分治,[1,4) in [0,4)左邊，[1,2) in [0,2)Get 1Get [2,4) in [2,4)雖然每次都有可能同時(shí)遞歸進(jìn)入兩棵子樹(shù)，但每層實(shí)際上只訪問(wèn)了兩個(gè)節(jié)點(diǎn)。為什么？因?yàn)椴樵?xún)是連續(xù)的啊……,其實(shí)還有別的核心思想后面再講……,2024年3月10日,清華大學(xué) 張昆瑋,12,因?yàn)椴樵?xún)是連續(xù)的？,如果同一層有三個(gè)被訪問(wèn)

6、，依次為A，B，C查詢(xún)是連續(xù)的，有了A和C，就一定包括B在樹(shù)中的兄弟那我直接用B的父親來(lái)計(jì)算好了，為什么要用B？,為什么用線段樹(shù)？,功利點(diǎn)說(shuō)，沒(méi)啥用的東西咱不學(xué)……,2024年3月10日,清華大學(xué) 張昆瑋,13,且慢,直接把原數(shù)組處理成前綴和For i=2 to n doA[i] += A[i-1]Ans(a,b) = A[a] - A[b-1],區(qū)區(qū)區(qū)間和，用的著線段樹(shù)？,2024年3月10日,清華大學(xué) 張昆瑋,14,202

7、4年3月10日,清華大學(xué) 張昆瑋,15,這是為什么呢？,原因是區(qū)間和的性質(zhì)非常好滿(mǎn)足區(qū)間減法區(qū)間減法什么的最討厭了！后面再說(shuō)！不過(guò)直接前綴和不是萬(wàn)能的！如果修改元素的話……,2024年3月10日,清華大學(xué) 張昆瑋,16,真正的作用,溝通原數(shù)組與前綴和的橋梁,其實(shí)……（其實(shí)什么，后面再講）,怎么寫(xiě)？,這個(gè)問(wèn)題，本來(lái)是仁者見(jiàn)仁，智者見(jiàn)智的啊但是我要講一點(diǎn)不那么“本來(lái)”的東西,2024年3月10日,清華大學(xué) 張昆瑋,17,2024年

8、3月10日,清華大學(xué) 張昆瑋,18,樸素的遞歸算法,訪問(wèn)線段如果要的是整條線段就直接返回如果與左子線段相交就遞歸處理如果與右子線段相交就遞歸處理合并所得到的解遺憾的是，這種樸素的方法并不是那么容易實(shí)現(xiàn)而且存在嚴(yán)重的效率問(wèn)題（常數(shù)太大）,怎么辦？,2024年3月10日,清華大學(xué) 張昆瑋,19,TLE,從存儲(chǔ)方式講起,工欲善其事，必先利其器。,2024年3月10日,清華大學(xué) 張昆瑋,20,2024年3月10日,清華大學(xué) 張昆瑋,

9、21,幾個(gè)不那么重要的問(wèn)題,雖然可以設(shè)計(jì)出三叉，四叉，……線段樹(shù)但是我們先從二叉樹(shù)開(kāi)始登高必自邇，行遠(yuǎn)必自卑多叉怎么辦后面再講（這還要講？自己研究去）為了不處理各種特殊情況，假設(shè)二叉樹(shù)是滿(mǎn)的！不是滿(mǎn)的？你的總區(qū)間是[0,1000)？你就當(dāng)作[0,1024)不就好了？,2024年3月10日,清華大學(xué) 張昆瑋,22,堆式存儲(chǔ)是關(guān)鍵,指針退休了？后面再講……,2024年3月10日,清華大學(xué) 張昆瑋,23,一些簡(jiǎn)單的問(wèn)題,N 的

10、左兒子是 2NN 的右兒子是 2N + 1N 的父親是 N >> 1……不就是個(gè)堆存儲(chǔ)么？不用講了吧？,2024年3月10日,清華大學(xué) 張昆瑋,24,換成二進(jìn)制看看吧！,2024年3月10日,清華大學(xué) 張昆瑋,25,似曾相識(shí)？,字母樹(shù)！存放的是100,101,110,111四個(gè)串！每個(gè)節(jié)點(diǎn)存的是以這個(gè)節(jié)點(diǎn)為前綴的所有節(jié)點(diǎn)和例：1中存的是所有四個(gè)以1開(kāi)頭的和。似乎從 100 到 111 就正好是原數(shù)組貌似…

11、…下標(biāo)減 4 就行了？,2024年3月10日,清華大學(xué) 張昆瑋,26,好多性質(zhì)啊，有用么？,我們可以直接找到一個(gè)數(shù)對(duì)應(yīng)的葉子不用自頂向下慢慢地找啊找“直接加 4 ”多簡(jiǎn)單！……直接找到葉子？無(wú)限遐想中……,存下來(lái)了，然后呢？,可以直接找到葉子？,2024年3月10日,清華大學(xué) 張昆瑋,27,2024年3月10日,清華大學(xué) 張昆瑋,28,天然的非遞歸方法！,2024年3月10日,清華大學(xué) 張昆瑋,29,天然的非遞歸方法！,20

12、24年3月10日,清華大學(xué) 張昆瑋,30,這么簡(jiǎn)單？,Func Query(s,t) // 詢(xún)問(wèn)從s到t閉區(qū)間s = s – 1, t = t + 1; // 變?yōu)殚_(kāi)區(qū)間s += M, t += M; // 找到葉子位置While not ((s xor t) == 1) doIf ((s and 1) == 0) Answer += Tree[s + 1];If ((t and 1) == 1) Answer += T

13、ree[t – 1];s = s >> 1, t = t >> 1;,2024年3月10日,清華大學(xué) 張昆瑋,31,C語(yǔ)言更簡(jiǎn)單！,for (s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1) {if (~s&1) Ans+=T[s^1];if ( t&1) Ans+=T[t^1];},2024年3月10日,清華大學(xué) 張昆瑋,32,Warning

14、,在將閉區(qū)間轉(zhuǎn)化成開(kāi)區(qū)間的時(shí)候可能越界1理論上能放 [0,2^N) 的樹(shù)其實(shí)只能查詢(xún) [1,2^N - 2] 的范圍切記切記,2024年3月10日,清華大學(xué) 張昆瑋,33,不要緊張,如果需要查詢(xún) 0 就整個(gè)向后平移一下所有下標(biāo)加一！如果需要在[0,1024)中查詢(xún)1023結(jié)尾的區(qū)間？慢！你的數(shù)據(jù)規(guī)模不是 1000 么？……如果真的要到1023，直接把總區(qū)間變成[0,2048)就是這么狠！,2024年3月10日,清華大

15、學(xué) 張昆瑋,34,修改就更簡(jiǎn)單,Func Change(n,NewValue)n += M;Tree[n] = NewValue;While n > 1 don = n >> 1;Tree[n] = Tree[2n] + Tree[2n+1];,2024年3月10日,清華大學(xué) 張昆瑋,35,C語(yǔ)言更簡(jiǎn)單,for(T[n+=M]=V, n>>=1;n;n>>=1)T[n]=T[n+n

16、]+T[n+n+1];沒(méi)了？沒(méi)了。,2024年3月10日,清華大學(xué) 張昆瑋,36,技術(shù)參數(shù)？,僅使用了兩倍原數(shù)組的空間其中還完整地包括了原數(shù)組構(gòu)造容易:For i=M-1 downto 1 do T[i]=T[2i]+T[2i+1];太好寫(xiě)了！好理解！自底向上，只訪問(wèn)一次，而且不一定訪問(wèn)到頂層實(shí)踐中非常快，與樹(shù)狀數(shù)組接近為什么呢？后面再講。,2024年3月10日,清華大學(xué) 張昆瑋,37,人家樹(shù)狀數(shù)組只用一倍空間,因?yàn)?/p>

17、樹(shù)狀數(shù)組依賴(lài)于區(qū)間減法區(qū)間減法什么的，最討厭了……后面再講，再講反正如果只問(wèn)問(wèn)前綴和，不問(wèn)區(qū)間和的話那我也可以只用一倍空間！,2024年3月10日,清華大學(xué) 張昆瑋,38,天然的非遞歸方法！,2024年3月10日,清華大學(xué) 張昆瑋,39,天然的非遞歸方法！,2024年3月10日,清華大學(xué) 張昆瑋,40,天然的非遞歸方法！,2024年3月10日,清華大學(xué) 張昆瑋,41,所有右兒子沒(méi)有用了,2024年3月10日,清華大學(xué) 張昆瑋,42

18、,省了一半空間吧,這不就和樹(shù)狀數(shù)組一樣了？本來(lái)就應(yīng)該一樣。回過(guò)頭說(shuō)，樹(shù)狀數(shù)組究竟是什么？就是省掉一半空間后的線段樹(shù)加上中序遍歷計(jì)算位置需要lowbit什么的我們用的是先序遍歷，符合人的思考習(xí)慣。,但是，這個(gè)空間沒(méi)必要省。費(fèi)點(diǎn)空間能換來(lái)實(shí)現(xiàn)的絕對(duì)簡(jiǎn)單。,2024年3月10日,清華大學(xué) 張昆瑋,43,哈哈,2024年3月10日,清華大學(xué) 張昆瑋,44,Just For Fun,我之前用這種寫(xiě)法做過(guò)不少題……大家都說(shuō)我的代碼看

19、不懂我說(shuō)這就是一個(gè)樹(shù)狀數(shù)組寫(xiě)樹(shù)狀數(shù)組的人說(shuō)沒(méi)有l(wèi)owbit我說(shuō)那就算是線段樹(shù)吧大家不相信非遞歸的線段樹(shù)這么短……我：……,標(biāo)記的傳遞與收集,懶惰即美德。,2024年3月10日,清華大學(xué) 張昆瑋,45,區(qū)間修改,噩夢(mèng)的開(kāi)始,2024年3月10日,清華大學(xué) 張昆瑋,46,2024年3月10日,清華大學(xué) 張昆瑋,47,帶區(qū)間修改的RMQ,RMQ (Range Minimum Query)區(qū)間最小值查詢(xún)線段樹(shù)支持區(qū)間修改：某一

20、區(qū)間的數(shù)值全部增加一個(gè)可正可負(fù)的數(shù)暴力修改不靈了！,2024年3月10日,清華大學(xué) 張昆瑋,48,四兩撥千斤,在線段樹(shù)上的每個(gè)節(jié)點(diǎn)增加一個(gè)標(biāo)記表示這一區(qū)間被增加過(guò)多少在自頂而下的遞歸過(guò)程中如果看到標(biāo)記，就更新當(dāng)前節(jié)點(diǎn)的值并將標(biāo)記下傳嗯？又要自頂向下？,2024年3月10日,清華大學(xué) 張昆瑋,49,標(biāo)記永久化,其實(shí)堆式存儲(chǔ)也可以自頂向下訪問(wèn)就是上下各走一次而已但是我們有更好的辦法（使勁想想就知道了）不再下傳標(biāo)記，而是隨

21、用隨查在自底向上的查詢(xún)過(guò)程中每向上走一層，就按照對(duì)應(yīng)的標(biāo)記調(diào)整答案仔細(xì)想想很有道理。我們?cè)敢獍驯M可能多的信息存放在樹(shù)的根部，所以下傳標(biāo)記做什么？,常數(shù)很小：One Pass,永久化的標(biāo)記就是值,莊周夢(mèng)蝶而已,2024年3月10日,清華大學(xué) 張昆瑋,50,2024年3月10日,清華大學(xué) 張昆瑋,51,染色問(wèn)題,一根線段，支持區(qū)間染色。詢(xún)問(wèn)區(qū)間是否同色？區(qū)間染色需要使用染色標(biāo)記1表示紅色，2表示藍(lán)色，3綠色，0雜色詢(xún)問(wèn)的時(shí)候就

22、直接看標(biāo)記嘛,2024年3月10日,清華大學(xué) 張昆瑋,52,直接看標(biāo)記？,2為紅色，3為藍(lán)色，1為雜色修改3為紅色查詢(xún)1，雜色？永久化的標(biāo)記就是值??！值是自動(dòng)維護(hù)的??！其實(shí)我們的修改算法在修改3的時(shí)候已經(jīng)維護(hù)了1自底向上順便重算所有遇到的節(jié)點(diǎn)標(biāo)記即可If (Mark[x]==0 and Mark[2x]==Mark[2x+1])Mark[x]=Mark[2x];,2024年3月10日,清華大學(xué) 張昆瑋,53,狗拿耗子，貓下

23、崗了,回到區(qū)間修改的RMQ通俗地講，標(biāo)記就是一個(gè)相對(duì)的量既然有了標(biāo)記，值還有什么用？或者說(shuō)，如果值本身就是相對(duì)的，還需要標(biāo)記？如果我讓所有的數(shù)都從零開(kāi)始變化，那標(biāo)記永久化之后，所有值都恒為零??！于是我們連值也不存了。永久化的標(biāo)記就是值。,2024年3月10日,清華大學(xué) 張昆瑋,54,什么意思？,每個(gè)節(jié)點(diǎn)不存區(qū)間最大值T[n]了存放M[n]=T[n]-T[n>>1]讓每一個(gè)節(jié)點(diǎn)的值都減除它父親的值區(qū)間修改就直

24、接改M[n]。查詢(xún)就是從要查的節(jié)點(diǎn)開(kāi)始一直加到根。T[n]=M[n]+M[n>>1]+…+M[1];遇到節(jié)點(diǎn)x，則 A=min(M[2x],M[2x+1])M[x]+=A,M[2x]-=A,M[2x+1]-=A,2024年3月10日,清華大學(xué) 張昆瑋,55,簡(jiǎn)單……,Func Add_x(s,t,x)for (s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1) {if (

25、~s&1) T[s^1]+=x;if ( t&1) T[t^1]+=x;A=min(T[s],T[s^1]),T[s]-=A,T[s^1]-=A,T[s>>1]+=A;A=min(T[t],T[t^1]),T[t]-=A,T[t^1]-=A,T[t>>1]+=A;},2024年3月10日,清華大學(xué) 張昆瑋,56,too 簡(jiǎn)單，too,Func Max(s,t)for (s=s+M-1,

26、t=t+M+1;s^t^1;s>>=1,t>>=1) {LAns+=T[s],Rans+=T[t];if (~s&1) LAns=max(LAns,T[s^1]);if ( t&1) RAns=max(RAns,T[t^1]);}Ans = max(LAns,RAns);while (s>1) Ans += T[s>>=1];,2024年3月10日,清華大學(xué) 張昆瑋

27、,57,啟示,差分是化絕對(duì)為相對(duì)的重要手段標(biāo)記永久化后就是值，只不過(guò)這種值是相對(duì)的計(jì)算答案時(shí)可以利用從節(jié)點(diǎn)到根部的信息,2024年3月10日,清華大學(xué) 張昆瑋,58,alternative,截至PPT制作時(shí)，大家用的線段樹(shù)自頂向下居多在自頂向下的線段樹(shù)中，標(biāo)記往往不是永久化的對(duì)于RMQ，需要下傳標(biāo)記對(duì)于染色問(wèn)題，需要下傳并收集標(biāo)記思想與這里我的方法差不多，實(shí)現(xiàn)上差別較大至少上下各訪問(wèn)一次，較慢參見(jiàn)其他資料,2024年3月

28、10日,清華大學(xué) 張昆瑋,59,還一個(gè)欠賬,線段樹(shù)是連接原數(shù)組和前綴和的橋梁橋梁兩邊同時(shí)取差分前綴和與差分互為逆運(yùn)算因此線段樹(shù)也是連接差分和原數(shù)組的橋梁如果要支持區(qū)間修改，單點(diǎn)查詢(xún)無(wú)需使用標(biāo)記，直接將原數(shù)組差分用線段樹(shù)維護(hù)差分?jǐn)?shù)組的前綴和即可。,其實(shí)什么……現(xiàn)在可以講了,2024年3月10日,清華大學(xué) 張昆瑋,60,前綴和的前綴和？,不借助標(biāo)記，支持區(qū)間修改和區(qū)間求和（原創(chuàng)）先差分后變成維護(hù)一個(gè)前綴和的前綴和……別被嚇

29、到，前綴和的前綴和是什么SS1 = S1 = x1SS2 = S1+ = 2x1+x2SS3 = S1+S2+S3 = 3x1+2x2+x3 =4(x1+x2+x3)-(1x1+2x2+3x3)多維護(hù)一個(gè){nxn}的前綴和就行了。,數(shù)學(xué)啊數(shù)學(xué)！,2024年3月10日,清華大學(xué) 張昆瑋,61,最長(zhǎng)上升區(qū)間列,最長(zhǎng)上升“區(qū)間列”在一個(gè)區(qū)間列中按順序找出最多區(qū)間使得不重疊，單調(diào)增如

30、 [1,3] [2,4] [4,5] 答案是[1,3]+[4,5]動(dòng)態(tài)規(guī)劃的可行決策是什么呢？如果要使上升列長(zhǎng)度大于x，最后一個(gè)數(shù)最小是多少，記為f[x]維護(hù)f[x]支持點(diǎn)查詢(xún)和區(qū)間修改。,2024年3月10日,清華大學(xué) 張昆瑋,62,前綴min的逆運(yùn)算,點(diǎn)查詢(xún)：查詢(xún)x處f[x]的值區(qū)間修改：x左邊的所有超過(guò)K的值，變?yōu)镵把x的左右換一下……（囧）整個(gè)f[-x]就是單調(diào)減的一個(gè)單調(diào)減的序列可以看作是由一個(gè)普通序列經(jīng)過(guò)前

31、綴min得到的！前綴min的逆運(yùn)算是什么呢？我們并不關(guān)心,2024年3月10日,清華大學(xué) 張昆瑋,63,這樣也行？,我們現(xiàn)在要維護(hù)的就是前綴min的逆運(yùn)算后的原序列！可是我們甚至不知道前綴min的逆運(yùn)算是什么不要緊，反正用不到。點(diǎn)查詢(xún)：查詢(xún)x處f[x]的值直接返回維護(hù)序列的前綴min區(qū)間修改：x左邊的所有超過(guò)K的值，變?yōu)镵把維護(hù)序列中的f[x]變?yōu)镵,線段樹(shù)，太靈活了！,2024年3月10日,清華大學(xué) 張昆瑋,64,但

32、是不要迷信線段樹(shù),不要迷戀哥，哥只是個(gè)傳說(shuō)……,2024年3月10日,清華大學(xué) 張昆瑋,65,2024年3月10日,清華大學(xué) 張昆瑋,66,重要條件：區(qū)間加法,說(shuō)了這么多，能使用線段樹(shù)解決問(wèn)題的關(guān)鍵：區(qū)間加法，即區(qū)間的“性質(zhì)”由子區(qū)間完全決定包括但不僅限于求和，求最值，求染色狀態(tài)這里的“性質(zhì)”有點(diǎn)像動(dòng)態(tài)規(guī)劃的狀態(tài)表示有時(shí)候，求的更多反而更容易最簡(jiǎn)單的例子：求區(qū)間第二最值如果實(shí)在不滿(mǎn)足區(qū)間加法，就全完了,2024年3月10日,

33、清華大學(xué) 張昆瑋,67,不滿(mǎn)足區(qū)間加法？,我們都知道線段樹(shù)求區(qū)間平均值不難那求一個(gè)區(qū)間中位數(shù)試試？什么，還不難？那你再求個(gè)眾數(shù)？……,2024年3月10日,清華大學(xué) 張昆瑋,68,不滿(mǎn)足區(qū)間加法！,越來(lái)越難的原因很簡(jiǎn)單知道兩區(qū)間的中位數(shù)，就知道和區(qū)間的中位數(shù)？知道各自眾數(shù)有什么用？……,2024年3月10日,清華大學(xué) 張昆瑋,69,超越中位數(shù)K-th number,給定一列數(shù)，反復(fù)求區(qū)間第k大數(shù)。要求的更多反而更容易…

34、…更容易……線段樹(shù)的每個(gè)區(qū)間必須保留更多的信息！每個(gè)區(qū)間中存下區(qū)間所有數(shù)的有序數(shù)組通過(guò)歸并完成區(qū)間加法,2024年3月10日,清華大學(xué) 張昆瑋,70,歸并很慢,如果每做一次查詢(xún)就歸并若干個(gè)線段復(fù)雜度就會(huì)達(dá)到O(n)離散化！二分答案！變?yōu)榍螅簒是區(qū)間第幾大數(shù)？這可以分別二分查找若干線段得到。總復(fù)雜度O(nlogn+Q*log2n),另一種原創(chuàng)方法，后面再講,2024年3月10日,清華大學(xué) 張昆瑋,71,區(qū)間減法,如果有

35、了區(qū)間減法……線段樹(shù)就能如虎添翼如“區(qū)間和”變成“前綴和”操作能簡(jiǎn)單不少同時(shí)也是能夠使用樹(shù)狀數(shù)組的條件但這不是必需的（和區(qū)間加法比一比）,另一種核心思想,我說(shuō)過(guò)后面要講的嘛,2024年3月10日,清華大學(xué) 張昆瑋,72,2024年3月10日,清華大學(xué) 張昆瑋,73,堆？,維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)支持整數(shù)插入取最大整數(shù)范圍是0~65535好了,2024年3月10日,清華大學(xué) 張昆瑋,74,劉汝佳老師的大招,堆當(dāng)然可以但是劉汝佳老

36、師的黑書(shū)上有大招！“分段哈?！薄殖扇舾啥?，存下“段里面有沒(méi)有數(shù)”信息,2024年3月10日,清華大學(xué) 張昆瑋,75,分段哈希,2024年3月10日,清華大學(xué) 張昆瑋,76,多來(lái)幾層如何,如果多來(lái)幾層呢？3層？4層？……到每個(gè)節(jié)點(diǎn)下面都只有兩個(gè)點(diǎn)為止！……我們得到了什么……,2024年3月10日,清華大學(xué) 張昆瑋,77,這也是線段樹(shù),2024年3月10日,清華大學(xué) 張昆瑋,78,哈哈,平衡樹(shù) vs 線段樹(shù),不要折騰……,2

37、024年3月10日,清華大學(xué) 張昆瑋,79,2024年3月10日,清華大學(xué) 張昆瑋,80,一種似曾相識(shí)的感覺(jué),維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)支持整數(shù)插入整數(shù)刪除取第k大的數(shù)（取最大最小什么的就不說(shuō)了）查詢(xún)數(shù)的排名查某數(shù)是否存在允許元素重復(fù)（為了難一點(diǎn)）整數(shù)范圍是0~65535好了,2024年3月10日,清華大學(xué) 張昆瑋,81,統(tǒng)計(jì)的力量！,平衡樹(shù)么？線段樹(shù)！統(tǒng)計(jì)[0,65536)每個(gè)數(shù)的出現(xiàn)頻率，記為f[x]整數(shù)插入，f[x]++

38、整數(shù)刪除，f[x]--查詢(xún)數(shù)的排名，求前綴和取第k大的數(shù)（取最大最小什么的就不說(shuō)了）給定前綴和，查找自頂向下，左邊不夠就向右走，否則向左。,2024年3月10日,清華大學(xué) 張昆瑋,82,事半功倍,實(shí)測(cè)得到線段樹(shù)用來(lái)處理這類(lèi)問(wèn)題非?？炱胶鈽?shù)中最快的Size Balanced Tree用了4秒多線段樹(shù)不到半秒全部出解。這還沒(méi)有分別減去讀入數(shù)據(jù)的時(shí)間。線段樹(shù)使用剛剛所講的實(shí)現(xiàn)，代碼量極小，且調(diào)試非常簡(jiǎn)單。,2024年3月10

39、日,清華大學(xué) 張昆瑋,83,如果數(shù)據(jù)范圍大呢？,離散化。不能離散化？呵呵……后面再講,2024年3月10日,清華大學(xué) 張昆瑋,84,一種似曾相識(shí)的感覺(jué),維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)支持字符串插入字符串刪除取第k大的字符串（取最大最小什么的就不說(shuō)了）查詢(xún)字符串的排名查某字符串是否存在,2024年3月10日,清華大學(xué) 張昆瑋,85,帶size域的字母樹(shù),這里的size域的維護(hù)方式和線段樹(shù)如出一轍！排名的計(jì)算方法，和之前整數(shù)的線段樹(shù)完

40、全一樣如果把字符串看作26進(jìn)制數(shù)那字母樹(shù)就是線段樹(shù)？,2024年3月10日,清華大學(xué) 張昆瑋,86,哈哈,2024年3月10日,清華大學(xué) 張昆瑋,87,那為啥字母樹(shù)省空間？,所有節(jié)點(diǎn)用指針記錄兒子空間隨用隨開(kāi)不是滿(mǎn)二叉樹(shù)，甚至不完全自頂向下處理所有問(wèn)題線段樹(shù)也可以這樣數(shù)據(jù)范圍再大，能比26^N還大？,2024年3月10日,清華大學(xué) 張昆瑋,88,線段樹(shù)處理long int,就是一棵三十二層高的線段樹(shù)指針式存儲(chǔ)，節(jié)點(diǎn)像字

41、母樹(shù)一樣動(dòng)態(tài)生成支持插入刪除選擇等等……復(fù)雜度是O(NlogM)，M是最大的數(shù)對(duì)于long int，M=32實(shí)測(cè)用了一秒多（還記得平衡樹(shù)四秒多么？）自頂向下，只算前綴和，也不難寫(xiě),不就是個(gè)二進(jìn)制的字母樹(shù)？,2024年3月10日,清華大學(xué) 張昆瑋,89,可能的改進(jìn),像壓縮字母樹(shù)一樣，會(huì)節(jié)約大量空間代價(jià)：不好寫(xiě)了刪除一個(gè)數(shù)之后嘗試回收已經(jīng)分配的節(jié)點(diǎn)代價(jià)：略慢，不好寫(xiě)了樹(shù)高動(dòng)態(tài)化初始樹(shù)高是1，只能放0每一次如果要放的數(shù)

42、太大，增加一個(gè)根根的左兒子是當(dāng)前的根，右兒子空。這個(gè)還實(shí)用！,平衡樹(shù) with 線段樹(shù),在天愿作比翼鳥(niǎo)，在地愿為連理枝,2024年3月10日,清華大學(xué) 張昆瑋,90,2024年3月10日,清華大學(xué) 張昆瑋,91,記得Size域么？,平衡樹(shù)上很多信息可以像線段樹(shù)一樣維護(hù)平衡樹(shù)就是一個(gè)會(huì)旋轉(zhuǎn)的動(dòng)態(tài)線段樹(shù)！最簡(jiǎn)單的，比如size域,2024年3月10日,清華大學(xué) 張昆瑋,92,NOI2005 維護(hù)數(shù)列,塊狀鏈表的傷心題，標(biāo)準(zhǔn)程序5

43、k+維護(hù)一個(gè)數(shù)列，支持：區(qū)間增加一個(gè)數(shù)區(qū)間刪除區(qū)間插入?yún)^(qū)間求和區(qū)間翻轉(zhuǎn),2024年3月10日,清華大學(xué) 張昆瑋,93,平衡樹(shù)與線段樹(shù),平衡樹(shù) splay 可以支持：區(qū)間刪除區(qū)間插入線段樹(shù)可以支持區(qū)間增加一個(gè)數(shù)區(qū)間求和把線段樹(shù)的值放在平衡樹(shù)的節(jié)點(diǎn)上,2024年3月10日,清華大學(xué) 張昆瑋,94,轉(zhuǎn)起來(lái)的線段樹(shù),每個(gè)節(jié)點(diǎn)表示它和子樹(shù)的信息總和平衡樹(shù)旋轉(zhuǎn)時(shí)更新線段樹(shù)的域哇，會(huì)動(dòng)的線段樹(shù)……,2024年3月10日,清

44、華大學(xué) 張昆瑋,95,標(biāo)記啊標(biāo)記,既要區(qū)間修改又要區(qū)間求和使用自頂向下的標(biāo)記下傳即可為了處理區(qū)間反轉(zhuǎn)增設(shè)一個(gè)bool值表示當(dāng)前節(jié)點(diǎn)左右子樹(shù)已經(jīng)互換先把區(qū)間從樹(shù)中splay出再處理要同時(shí)更改所有節(jié)點(diǎn)的反轉(zhuǎn)標(biāo)記？不記錄反轉(zhuǎn)標(biāo)記，記錄反轉(zhuǎn)標(biāo)記的標(biāo)記（?。?2024年3月10日,清華大學(xué) 張昆瑋,96,好綜合的一道題,但是所有部分都是相對(duì)簡(jiǎn)單的！一點(diǎn)點(diǎn)寫(xiě)，只是很多很多小題而已……,返璞歸真,關(guān)于線段樹(shù)，我們講的已經(jīng)太多了……,2

45、024年3月10日,清華大學(xué) 張昆瑋,97,2024年3月10日,清華大學(xué) 張昆瑋,98,再還一個(gè)欠賬,K-th number 的另一個(gè)方法如果區(qū)間互不包含，將所有要求的區(qū)間排個(gè)序來(lái)算。用平衡樹(shù)或線段樹(shù)存下當(dāng)前區(qū)間中的數(shù)然后向下一個(gè)區(qū)間移動(dòng)左端點(diǎn)增加是數(shù)的刪除右端點(diǎn)增加是數(shù)的添加每個(gè)數(shù)進(jìn)出各一次而已,2024年3月10日,清華大學(xué) 張昆瑋,99,如果相互可以包含呢？,關(guān)鍵在于合理的計(jì)算方式使得相鄰區(qū)間的差異盡量小從一個(gè)

46、區(qū)間變?yōu)榱硪粋€(gè)區(qū)間的代價(jià)是多少？把區(qū)間看作二維平面的坐標(biāo)代價(jià)就是兩個(gè)平面點(diǎn)的Manhattan距離！然后呢？Hamilton路？不！一個(gè)已知的區(qū)間可以用來(lái)算很多個(gè)未知的！平面圖Manhattan距離最小生成樹(shù)。,2024年3月10日,清華大學(xué) 張昆瑋,100,然后呢？,平面圖Manhattan距離MST可以在O(nlogn)求出先對(duì)Q個(gè)問(wèn)題用這個(gè)方法處理再按照MST的順序和方法實(shí)際計(jì)算求數(shù)學(xué)大牛分析總復(fù)雜度雖然繞了很

47、多彎路，但是有一種用模型解決實(shí)際問(wèn)題的感覺(jué)。居然MST還能用來(lái)做預(yù)處理呢……,2024年3月10日,清華大學(xué) 張昆瑋,101,最后的硬骨頭，眾數(shù),聽(tīng)了這么久，一起做一道練習(xí)題吧……給定一列n個(gè)數(shù)，和m個(gè)區(qū)間，求每個(gè)區(qū)間里的眾數(shù)出現(xiàn)了多少次。對(duì)于10%的數(shù)據(jù)n<100, m<100對(duì)于30%的數(shù)據(jù)n<1000,m<1000對(duì)于50%的數(shù)據(jù)n<100000,m<100000對(duì)于70%的數(shù)據(jù)n&l