統(tǒng)計(jì)的力量線段樹詳細(xì)教程

統(tǒng)計(jì)的力量線段樹詳細(xì)教程第1頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋2許多算法的本質(zhì)是統(tǒng)計(jì)根據(jù)D.E.Knuth的分類方法

計(jì)算機(jī)算法可以分為兩類：數(shù)值算法與非數(shù)值算法其中的非數(shù)值算法包括：索引分類統(tǒng)計(jì)……第2頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋3一個(gè)悲劇POJ上的某題，時(shí)限很緊……大家都用樹狀數(shù)組，但是有人只會(huì)用線段樹呢？而且我可以輕易改出一道不能用樹狀數(shù)組的題在線段樹一次次TLE后，有一個(gè)ID發(fā)帖抱怨“下次寫一個(gè)匯編版非遞歸線段樹，再超時(shí)？”可是大家都知道，超時(shí)的代碼已經(jīng)2k了。其實(shí)我寫的就是線段樹。很快，而且不到1k。第3頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋4線段樹用于統(tǒng)計(jì)運(yùn)行速度快適應(yīng)能力強(qiáng)編寫方便結(jié)構(gòu)簡單容易調(diào)試關(guān)鍵在于靈活實(shí)現(xiàn)第4頁，共100頁，2023年，2月20日，星期六線段樹，從何而來？為什么在《算法導(dǎo)論》和黑書中都難見到其蹤跡？2023年4月23日清華大學(xué)張昆瑋5第5頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋6計(jì)算幾何！計(jì)算幾何在長期的發(fā)展中，

誕生了許多實(shí)用的數(shù)據(jù)結(jié)構(gòu)。區(qū)間查詢，穿刺查詢都是計(jì)算幾何解決的問題作為特例中的特例，線段樹解決的問題是：一維空間上的幾何統(tǒng)計(jì)高維推廣（kd-tree&…）可以進(jìn)行正交查詢由于競賽中涉及計(jì)算幾何的內(nèi)容有限，不展開第6頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋7真正有用的是“點(diǎn)樹”線段樹把數(shù)軸分成區(qū)間來處理如[8,10),[10,11),…實(shí)際上我們面對(duì)的往往是離散量競賽中出現(xiàn)的線段樹往往因此退化為“點(diǎn)樹”即，最底層的線段只包含一個(gè)點(diǎn)：如：[8,9)中只有整點(diǎn)8而已在之后的討論中，我們不再區(qū)別“點(diǎn)樹”與線段樹第7頁，共100頁，2023年，2月20日，星期六第一印象如果我給MM的第一印象不到80分的話……是不是老老實(shí)實(shí)地早點(diǎn)罷手比較好？2023年4月23日清華大學(xué)張昆瑋8第8頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋9最經(jīng)典的問題：區(qū)間和第9頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋10核心思想：分治[1,4)in[0,4)左邊，[1,2)in[0,2)Get1Get[2,4)in[2,4)雖然每次都有可能同時(shí)遞歸進(jìn)入兩棵子樹，

但每層實(shí)際上只訪問了兩個(gè)節(jié)點(diǎn)。為什么？因?yàn)椴樵兪沁B續(xù)的啊……其實(shí)還有別的核心思想后面再講……第10頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋11因?yàn)椴樵兪沁B續(xù)的？如果同一層有三個(gè)被訪問，依次為A，B，C查詢是連續(xù)的，有了A和C，就一定包括B在樹中的兄弟那我直接用B的父親來計(jì)算好了，為什么要用B？第11頁，共100頁，2023年，2月20日，星期六為什么用線段樹？功利點(diǎn)說，沒啥用的東西咱不學(xué)……2023年4月23日清華大學(xué)張昆瑋12第12頁，共100頁，2023年，2月20日，星期六且慢直接把原數(shù)組處理成前綴和Fori=2tondoA[i]+=A[i-1]Ans(a,b)=A[a]-A[b-1]區(qū)區(qū)區(qū)間和，用的著線段樹？2023年4月23日清華大學(xué)張昆瑋13第13頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋14這是為什么呢？原因是區(qū)間和的性質(zhì)非常好滿足區(qū)間減法區(qū)間減法什么的最討厭了！后面再說！不過直接前綴和不是萬能的！如果修改元素的話……第14頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋15真正的作用數(shù)據(jù)結(jié)構(gòu)修改元素取前綴和直接存儲(chǔ)原數(shù)組O(1)O(n)直接存儲(chǔ)前綴和O(n)O(1)線段樹O(logn)O(logn)溝通原數(shù)組與前綴和的橋梁其實(shí)……（其實(shí)什么，后面再講）第15頁，共100頁，2023年，2月20日，星期六怎么寫？這個(gè)問題，本來是仁者見仁，智者見智的啊但是我要講一點(diǎn)不那么“本來”的東西2023年4月23日清華大學(xué)張昆瑋16第16頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋17樸素的遞歸算法訪問線段如果要的是整條線段就直接返回如果與左子線段相交就遞歸處理如果與右子線段相交就遞歸處理合并所得到的解遺憾的是，這種樸素的方法并不是那么容易實(shí)現(xiàn)而且存在嚴(yán)重的效率問題（常數(shù)太大）第17頁，共100頁，2023年，2月20日，星期六怎么辦？2023年4月23日清華大學(xué)張昆瑋18TLE第18頁，共100頁，2023年，2月20日，星期六從存儲(chǔ)方式講起工欲善其事，必先利其器。2023年4月23日清華大學(xué)張昆瑋19第19頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋20幾個(gè)不那么重要的問題雖然可以設(shè)計(jì)出三叉，四叉，……線段樹但是我們先從二叉樹開始登高必自邇，行遠(yuǎn)必自卑多叉怎么辦后面再講（這還要講？自己研究去）為了不處理各種特殊情況，假設(shè)二叉樹是滿的！不是滿的？你的總區(qū)間是[0,1000)？你就當(dāng)作[0,1024)不就好了？第20頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋21堆式存儲(chǔ)是關(guān)鍵指針退休了？后面再講……第21頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋22一些簡單的問題N的左兒子是2NN的右兒子是2N+1N的父親是N>>1……不就是個(gè)堆存儲(chǔ)么？不用講了吧？第22頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋23換成二進(jìn)制看看吧！第23頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋24似曾相識(shí)？字母樹！存放的是100,101,110,111四個(gè)串！每個(gè)節(jié)點(diǎn)存的是以這個(gè)節(jié)點(diǎn)為前綴的所有節(jié)點(diǎn)和例：1中存的是所有四個(gè)以1開頭的和。似乎從100到111就正好是原數(shù)組貌似……下標(biāo)減4就行了？第24頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋25好多性質(zhì)啊，有用么？我們可以直接找到一個(gè)數(shù)對(duì)應(yīng)的葉子不用自頂向下慢慢地找啊找“直接加4”多簡單！……直接找到葉子？無限遐想中……第25頁，共100頁，2023年，2月20日，星期六存下來了，然后呢？可以直接找到葉子？2023年4月23日清華大學(xué)張昆瑋26第26頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋27天然的非遞歸方法！第27頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋28天然的非遞歸方法！第28頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋29這么簡單？FuncQuery(s,t)//詢問從s到t閉區(qū)間s=s–1,t=t+1;//變?yōu)殚_區(qū)間s+=M,t+=M;//找到葉子位置Whilenot((sxort)==1)doIf((sand1)==0)Answer+=Tree[s+1];If((tand1)==1)Answer+=Tree[t–1];s=s>>1,t=t>>1;第29頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋30C語言更簡單！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];}第30頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋31Warning在將閉區(qū)間轉(zhuǎn)化成開區(qū)間的時(shí)候可能越界1理論上能放[0,2^N)的樹其實(shí)只能查詢[1,2^N-2]的范圍切記切記第31頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋32不要緊張如果需要查詢0就整個(gè)向后平移一下所有下標(biāo)加一！如果需要在[0,1024)中查詢1023結(jié)尾的區(qū)間？慢！你的數(shù)據(jù)規(guī)模不是1000么？……如果真的要到1023，直接把總區(qū)間變成[0,2048)就是這么狠！第32頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋33修改就更簡單FuncChange(n,NewValue)n+=M;Tree[n]=NewValue;Whilen>1don=n>>1;Tree[n]=Tree[2n]+Tree[2n+1];第33頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋34C語言更簡單for(T[n+=M]=V,n>>=1;n;n>>=1)T[n]=T[n+n]+T[n+n+1];沒了？沒了。第34頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋35技術(shù)參數(shù)？僅使用了兩倍原數(shù)組的空間其中還完整地包括了原數(shù)組構(gòu)造容易:Fori=M-1downto1doT[i]=T[2i]+T[2i+1];太好寫了！好理解！自底向上，只訪問一次，而且不一定訪問到頂層實(shí)踐中非常快，與樹狀數(shù)組接近為什么呢？后面再講。第35頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋36人家樹狀數(shù)組只用一倍空間因?yàn)闃錉顢?shù)組依賴于區(qū)間減法區(qū)間減法什么的，最討厭了……后面再講，再講反正如果只問問前綴和，不問區(qū)間和的話那我也可以只用一倍空間！第36頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋37天然的非遞歸方法！第37頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋38天然的非遞歸方法！第38頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋39天然的非遞歸方法！第39頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋40所有右兒子沒有用了第40頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋41省了一半空間吧這不就和樹狀數(shù)組一樣了？本來就應(yīng)該一樣。回過頭說，樹狀數(shù)組究竟是什么？就是省掉一半空間后的線段樹加上中序遍歷計(jì)算位置需要lowbit什么的我們用的是先序遍歷，符合人的思考習(xí)慣。但是，這個(gè)空間沒必要省。費(fèi)點(diǎn)空間能換來實(shí)現(xiàn)的絕對(duì)簡單。第41頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋42哈哈第42頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋43JustForFun我之前用這種寫法做過不少題……大家都說我的代碼看不懂我說這就是一個(gè)樹狀數(shù)組寫樹狀數(shù)組的人說沒有l(wèi)owbit我說那就算是線段樹吧大家不相信非遞歸的線段樹這么短……我：……第43頁，共100頁，2023年，2月20日，星期六標(biāo)記的傳遞與收集懶惰即美德。2023年4月23日清華大學(xué)張昆瑋44第44頁，共100頁，2023年，2月20日，星期六區(qū)間修改噩夢(mèng)的開始2023年4月23日清華大學(xué)張昆瑋45第45頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋46帶區(qū)間修改的RMQRMQ(RangeMinimumQuery)區(qū)間最小值查詢線段樹支持區(qū)間修改：某一區(qū)間的數(shù)值全部增加一個(gè)可正可負(fù)的數(shù)暴力修改不靈了！第46頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋47四兩撥千斤在線段樹上的每個(gè)節(jié)點(diǎn)增加一個(gè)標(biāo)記表示這一區(qū)間被增加過多少在自頂而下的遞歸過程中如果看到標(biāo)記，就更新當(dāng)前節(jié)點(diǎn)的值并將標(biāo)記下傳嗯？又要自頂向下？第47頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋48標(biāo)記永久化其實(shí)堆式存儲(chǔ)也可以自頂向下訪問就是上下各走一次而已但是我們有更好的辦法（使勁想想就知道了）不再下傳標(biāo)記，而是隨用隨查在自底向上的查詢過程中每向上走一層，就按照對(duì)應(yīng)的標(biāo)記調(diào)整答案仔細(xì)想想很有道理。我們?cè)敢獍驯M可能多的信息存放在樹的根部，所以下傳標(biāo)記做什么？常數(shù)很?。篛nePass第48頁，共100頁，2023年，2月20日，星期六永久化的標(biāo)記就是值莊周夢(mèng)蝶而已2023年4月23日清華大學(xué)張昆瑋49第49頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋50染色問題一根線段，支持區(qū)間染色。

詢問區(qū)間是否同色？區(qū)間染色需要使用染色標(biāo)記

1表示紅色，2表示藍(lán)色，3綠色，0雜色詢問的時(shí)候就直接看標(biāo)記嘛第50頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋51直接看標(biāo)記？2為紅色，3為藍(lán)色，1為雜色

修改3為紅色

查詢1，雜色？永久化的標(biāo)記就是值??！值是自動(dòng)維護(hù)的??！其實(shí)我們的修改算法在修改3的時(shí)候已經(jīng)維護(hù)了1自底向上順便重算所有遇到的節(jié)點(diǎn)標(biāo)記即可If(Mark[x]==0andMark[2x]==Mark[2x+1])Mark[x]=Mark[2x];第51頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋52狗拿耗子，貓下崗了回到區(qū)間修改的RMQ通俗地講，標(biāo)記就是一個(gè)相對(duì)的量既然有了標(biāo)記，值還有什么用？或者說，如果值本身就是相對(duì)的，還需要標(biāo)記？如果我讓所有的數(shù)都從零開始變化，

那標(biāo)記永久化之后，所有值都恒為零?。∮谑俏覀冞B值也不存了。永久化的標(biāo)記就是值。第52頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋53什么意思？每個(gè)節(jié)點(diǎn)不存區(qū)間最大值T[n]了

存放M[n]=T[n]-T[n>>1]讓每一個(gè)節(jié)點(diǎn)的值都減除它父親的值區(qū)間修改就直接改M[n]。查詢就是從要查的節(jié)點(diǎn)開始一直加到根。

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第53頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋54簡單……FuncAdd_x(s,t,x)for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){if(~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;}第54頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋55too簡單，tooFuncMax(s,t)for(s=s+M-1,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];第55頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋56啟示差分是化絕對(duì)為相對(duì)的重要手段標(biāo)記永久化后就是值，只不過這種值是相對(duì)的計(jì)算答案時(shí)可以利用從節(jié)點(diǎn)到根部的信息第56頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋57alternative截至PPT制作時(shí)，大家用的線段樹自頂向下居多在自頂向下的線段樹中，標(biāo)記往往不是永久化的對(duì)于RMQ，需要下傳標(biāo)記對(duì)于染色問題，需要下傳并收集標(biāo)記思想與這里我的方法差不多，實(shí)現(xiàn)上差別較大至少上下各訪問一次，較慢參見其他資料第57頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋58還一個(gè)欠賬線段樹是連接原數(shù)組和前綴和的橋梁橋梁兩邊同時(shí)取差分前綴和與差分互為逆運(yùn)算因此線段樹也是連接差分和原數(shù)組的橋梁如果要支持區(qū)間修改，單點(diǎn)查詢無需使用標(biāo)記，直接將原數(shù)組差分用線段樹維護(hù)差分?jǐn)?shù)組的前綴和即可。其實(shí)什么……現(xiàn)在可以講了第58頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋59前綴和的前綴和？不借助標(biāo)記，支持區(qū)間修改和區(qū)間求和（原創(chuàng)）先差分后變成維護(hù)一個(gè)前綴和的前綴和……別被嚇到，前綴和的前綴和是什么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é)！第59頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋60最長上升區(qū)間列最長上升“區(qū)間列”在一個(gè)區(qū)間列中按順序找出最多區(qū)間

使得不重疊，單調(diào)增如[1,3][2,4][4,5]答案是[1,3]+[4,5]動(dòng)態(tài)規(guī)劃的可行決策是什么呢？

如果要使上升列長度大于x，

最后一個(gè)數(shù)最小是多少，記為f[x]維護(hù)f[x]支持點(diǎn)查詢和區(qū)間修改。第60頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋61前綴min的逆運(yùn)算點(diǎn)查詢：查詢x處f[x]的值區(qū)間修改：x左邊的所有超過K的值，變?yōu)镵把x的左右換一下……（囧）整個(gè)f[-x]就是單調(diào)減的一個(gè)單調(diào)減的序列可以看作

是由一個(gè)普通序列經(jīng)過前綴min得到的！前綴min的逆運(yùn)算是什么呢？我們并不關(guān)心第61頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋62這樣也行？我們現(xiàn)在要維護(hù)的就是

前綴min的逆運(yùn)算后的原序列！可是我們甚至不知道前綴min的逆運(yùn)算是什么不要緊，反正用不到。點(diǎn)查詢：查詢x處f[x]的值

直接返回維護(hù)序列的前綴min區(qū)間修改：x左邊的所有超過K的值，變?yōu)镵

把維護(hù)序列中的f[x]變?yōu)镵第62頁，共100頁，2023年，2月20日，星期六線段樹，太靈活了！2023年4月23日清華大學(xué)張昆瑋63第63頁，共100頁，2023年，2月20日，星期六但是不要迷信線段樹不要迷戀哥，哥只是個(gè)傳說……2023年4月23日清華大學(xué)張昆瑋64第64頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋65重要條件：區(qū)間加法說了這么多，能使用線段樹解決問題的關(guān)鍵：區(qū)間加法，即區(qū)間的“性質(zhì)”由子區(qū)間完全決定包括但不僅限于求和，求最值，求染色狀態(tài)這里的“性質(zhì)”有點(diǎn)像動(dòng)態(tài)規(guī)劃的狀態(tài)表示有時(shí)候，求的更多反而更容易最簡單的例子：求區(qū)間第二最值如果實(shí)在不滿足區(qū)間加法，就全完了第65頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋66不滿足區(qū)間加法？我們都知道線段樹求區(qū)間平均值不難那求一個(gè)區(qū)間中位數(shù)試試？什么，還不難？那你再求個(gè)眾數(shù)？……第66頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋67不滿足區(qū)間加法！越來越難的原因很簡單知道兩區(qū)間的中位數(shù)，就知道和區(qū)間的中位數(shù)？知道各自眾數(shù)有什么用？……第67頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋68超越中位數(shù)

K-thnumber給定一列數(shù)，反復(fù)求區(qū)間第k大數(shù)。要求的更多反而更容易……

更容易……線段樹的每個(gè)區(qū)間必須保留更多的信息！每個(gè)區(qū)間中存下區(qū)間所有數(shù)的有序數(shù)組通過歸并完成區(qū)間加法第68頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋69歸并很慢如果每做一次查詢就歸并若干個(gè)線段復(fù)雜度就會(huì)達(dá)到O(n)離散化！二分答案！變?yōu)榍螅簒是區(qū)間第幾大數(shù)？這可以分別二分查找若干線段得到?？倧?fù)雜度O(nlogn+Q*log2n)另一種原創(chuàng)方法，后面再講第69頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋70區(qū)間減法如果有了區(qū)間減法……線段樹就能如虎添翼如“區(qū)間和”變成“前綴和”操作能簡單不少同時(shí)也是能夠使用樹狀數(shù)組的條件但這不是必需的（和區(qū)間加法比一比）第70頁，共100頁，2023年，2月20日，星期六另一種核心思想我說過后面要講的嘛2023年4月23日清華大學(xué)張昆瑋71第71頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋72堆？維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)支持整數(shù)插入取最大整數(shù)范圍是0~65535好了第72頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋73劉汝佳老師的大招堆當(dāng)然可以但是劉汝佳老師的黑書上有大招！“分段哈希”……分成若干段，存下“段里面有沒有數(shù)”信息第73頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋74分段哈希第74頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋75多來幾層如何如果多來幾層呢？3層？4層？……到每個(gè)節(jié)點(diǎn)下面都只有兩個(gè)點(diǎn)為止！……我們得到了什么……第75頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋76這也是線段樹第76頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋77哈哈第77頁，共100頁，2023年，2月20日，星期六平衡樹vs線段樹不要折騰……2023年4月23日清華大學(xué)張昆瑋78第78頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋79一種似曾相識(shí)的感覺維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)支持整數(shù)插入整數(shù)刪除取第k大的數(shù)（取最大最小什么的就不說了）查詢數(shù)的排名查某數(shù)是否存在允許元素重復(fù)（為了難一點(diǎn)）整數(shù)范圍是0~65535好了第79頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋80統(tǒng)計(jì)的力量！平衡樹么？線段樹！統(tǒng)計(jì)[0,65536)每個(gè)數(shù)的出現(xiàn)頻率，記為f[x]整數(shù)插入，f[x]++整數(shù)刪除，f[x]--查詢數(shù)的排名，求前綴和取第k大的數(shù)（取最大最小什么的就不說了）

給定前綴和，查找

自頂向下，左邊不夠就向右走，否則向左。第80頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋81事半功倍實(shí)測得到線段樹用來處理這類問題非?？炱胶鈽渲凶羁斓腟izeBalancedTree用了4秒多線段樹不到半秒全部出解。這還沒有分別減去讀入數(shù)據(jù)的時(shí)間。線段樹使用剛剛所講的實(shí)現(xiàn)，代碼量極小，且調(diào)試非常簡單。第81頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋82如果數(shù)據(jù)范圍大呢？離散化。不能離散化？呵呵……后面再講第82頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋83一種似曾相識(shí)的感覺維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)支持字符串插入字符串刪除取第k大的字符串（取最大最小什么的就不說了）查詢字符串的排名查某字符串是否存在第83頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋84帶size域的字母樹

這里的size域的維護(hù)方式和線段樹如出一轍！排名的計(jì)算方法，和之前整數(shù)的線段樹完全一樣如果把字符串看作26進(jìn)制數(shù)那字母樹就是線段樹？第84頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋85哈哈第85頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋86那為啥字母樹省空間？所有節(jié)點(diǎn)用指針記錄兒子空間隨用隨開不是滿二叉樹，甚至不完全自頂向下處理所有問題線段樹也可以這樣數(shù)據(jù)范圍再大，能比26^N還大？第86頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋87線段樹處理longint就是一棵三十二層高的線段樹

指針式存儲(chǔ)，節(jié)點(diǎn)像字母樹一樣動(dòng)態(tài)生成支持插入刪除選擇等等……復(fù)雜度是O(NlogM)，M是最大的數(shù)對(duì)于longint，M=32實(shí)測用了一秒多（還記得平衡樹四秒多么？）自頂向下，只算前綴和，也不難寫不就是個(gè)二進(jìn)制的字母樹？第87頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋88可能的改進(jìn)像壓縮字母樹一樣，會(huì)節(jié)約大量空間

代價(jià)：不好寫了刪除一個(gè)數(shù)之后嘗試回收已經(jīng)分配的節(jié)點(diǎn)

代價(jià)：略慢，不好寫了樹高動(dòng)態(tài)化

初始樹高是1，只能放0

每一次如果要放的數(shù)太大，增加一個(gè)根

根的左兒子是當(dāng)前的根，右兒子空。

這個(gè)還實(shí)用！第88頁，共100頁，2023年，2月20日，星期六平衡樹with線段樹在天愿作比翼鳥，在地愿為連理枝2023年4月23日清華大學(xué)張昆瑋89第89頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋90記得Size域么？平衡樹上很多信息可以像線段樹一樣維護(hù)平衡樹就是一個(gè)會(huì)旋轉(zhuǎn)的動(dòng)態(tài)線段樹！最簡單的，比如size域第90頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋91NOI2005維護(hù)數(shù)列塊狀鏈表的傷心題，標(biāo)準(zhǔn)程序5k+維護(hù)一個(gè)數(shù)列，支持：區(qū)間增加一個(gè)數(shù)區(qū)間刪除區(qū)間插入?yún)^(qū)間求和區(qū)間翻轉(zhuǎn)第91頁，共100頁，2023年，2月20日，星期六2023年4月23日清華大學(xué)張昆瑋92平衡樹與線段樹平衡樹splay可以支持：區(qū)間刪除區(qū)間插入線段樹可以支持區(qū)間