Mato is No.1

額……最近兩天光顧著刷題忘了總結(jié)了……正好現(xiàn)在把總結(jié)的東東全部補(bǔ)上吧囧……

【重復(fù)次數(shù)mul】
在前面第一篇總結(jié)Splay Tree的時(shí)候就提到了結(jié)點(diǎn)的重復(fù)次數(shù)(mul)域，這個(gè)東東至今在網(wǎng)上還米看見(jiàn)有犇用（在本沙茶見(jiàn)過(guò)的范圍內(nèi)），但是不可否認(rèn)的是這個(gè)域在某些情況下幾乎是“必須使用”的。
所謂重復(fù)次數(shù)，就是將樹(shù)中所有值(v)相同的結(jié)點(diǎn)全部合并成一個(gè)，這些結(jié)點(diǎn)的總個(gè)數(shù)就是合并后的結(jié)點(diǎn)的mul值。比如，在一棵空樹(shù)中插入3個(gè)值為5的結(jié)點(diǎn)后，在使用mul域的情況下，樹(shù)中只有一個(gè)結(jié)點(diǎn)，其v值為5，mul值為3。
在平衡樹(shù)中，值相同的結(jié)點(diǎn)確實(shí)非常礙事。按照二叉查找樹(shù)的定義：“要么是一棵空樹(shù)，要么是一棵滿足以下條件的非空樹(shù)：根結(jié)點(diǎn)左子樹(shù)中所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)，根結(jié)點(diǎn)右子樹(shù)中所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)，且根的左右子樹(shù)均為二叉查找樹(shù)”，在二叉查找樹(shù)中，是不應(yīng)該出現(xiàn)值相同的結(jié)點(diǎn)的。可是在實(shí)際問(wèn)題中，出現(xiàn)值相同的結(jié)點(diǎn)幾乎是不可避免的。此時(shí)，樹(shù)的定義就會(huì)變得非常模糊，也就是要把二叉查找樹(shù)定義中的“小于”全部改為“小于等于”，“大于”全部改為“大于等于”。這樣定義的樹(shù)在一般情況下也米有神馬問(wèn)題，但是在找前趨(Pred)和找后繼(Succ)操作中，問(wèn)題就來(lái)了。因?yàn)楦Y(jié)點(diǎn)的前趨和后繼的值可能與根結(jié)點(diǎn)相等（比如 HNOI2004 寵物收養(yǎng)所 那一題），這時(shí)，根結(jié)點(diǎn)的前趨既有可能在左子樹(shù)里，也有可能在右子樹(shù)里，根結(jié)點(diǎn)的后繼也一樣。此時(shí)，這兩個(gè)操作就無(wú)法進(jìn)行了。
【mul域的維護(hù)】
mul域其實(shí)可以看成結(jié)點(diǎn)的一個(gè)本身屬性，和v一樣。因此在旋轉(zhuǎn)、伸展操作中任何結(jié)點(diǎn)的mul值都是不會(huì)改變的。可能改變結(jié)點(diǎn)mul值的地方只有兩處：一是插入，二是刪除。在插入一個(gè)值為_(kāi)v的結(jié)點(diǎn)的時(shí)候，如果發(fā)現(xiàn)值為_(kāi)v的結(jié)點(diǎn)在樹(shù)中已經(jīng)存在，則只會(huì)將這個(gè)結(jié)點(diǎn)的mul值加1，而不是真正插入一個(gè)新的結(jié)點(diǎn)。同樣的，在刪除一個(gè)結(jié)點(diǎn)的時(shí)候，如果這個(gè)結(jié)點(diǎn)的mul值大于1，則只會(huì)將這個(gè)結(jié)點(diǎn)的mul值減1，而不是真正刪除。
【mul域的作用】
mul域最主要的作用就是解決值相同的結(jié)點(diǎn)對(duì)于某些操作的影響。另外，mul域的引入可以減少樹(shù)中結(jié)點(diǎn)的總個(gè)數(shù)（尤其是當(dāng)插入的結(jié)點(diǎn)數(shù)很多而結(jié)點(diǎn)的值的范圍不大的時(shí)候），從而降低時(shí)間復(fù)雜度（準(zhǔn)確來(lái)說(shuō)可以降低常數(shù)）。
【Splay Tree的進(jìn)階操作】
<1>找非根結(jié)點(diǎn)的前趨和后繼。
Splay Tree由于有伸展操作，可以將要求前趨或后繼的點(diǎn)伸展到根再求前趨或后繼。如果要不通過(guò)伸展操作找一個(gè)非根結(jié)點(diǎn)的前趨或后繼怎么辦？
設(shè)這個(gè)結(jié)點(diǎn)為x。如果x有左子結(jié)點(diǎn)，則x的前趨就是x的左子結(jié)點(diǎn)的右鏈上的最后一個(gè)結(jié)點(diǎn)；如果x沒(méi)有左子結(jié)點(diǎn)，則x的前趨就是從x開(kāi)始往上（往x的祖先）查找，直到找到第一個(gè)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)的結(jié)點(diǎn)為止，則這個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)就是x的前趨（或者說(shuō)，就是不斷沿著x的父結(jié)點(diǎn)往上找，一開(kāi)始都是往右的，找到第一個(gè)往左的就行了）。后繼則正好相反。證明可以用中序遍歷。
<2>找某個(gè)值v0的前趨和后繼（值為v0的結(jié)點(diǎn)在樹(shù)中不一定存在）。
所謂v0的前趨和后繼，就是指在樹(shù)中值小于（也有的是不大于）v0的最大的結(jié)點(diǎn)的值，和樹(shù)中值大于（也有的是不小于）v0的最小的結(jié)點(diǎn)的值。在有了操作（1）【不通過(guò)伸展操作找非根結(jié)點(diǎn)的前趨和后繼】以后，這個(gè)操作變得極為容易：先進(jìn)行普通的查找操作（查找值為v0的結(jié)點(diǎn)），如果能找到，則剩下的步驟就和操作（1）一樣了；如果找不到，則必然是找到某個(gè)空結(jié)點(diǎn)（0）處，假設(shè)在這里插入一個(gè)值為v0的結(jié)點(diǎn)（只是假設(shè)，不是真插入），則該結(jié)點(diǎn)顯然是沒(méi)有左子結(jié)點(diǎn)的，因此就是“從該結(jié)點(diǎn)開(kāi)始往上查找，直到找到第一個(gè)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)的結(jié)點(diǎn)為止，則這個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)就是該結(jié)點(diǎn)的前趨”，也就是v0的前趨；后繼類似。
在查找過(guò)程中可以進(jìn)行一個(gè)常數(shù)優(yōu)化：設(shè)點(diǎn)i為查找過(guò)程中“右轉(zhuǎn)”的最后一個(gè)結(jié)點(diǎn)（即找到該結(jié)點(diǎn)后，接下來(lái)是該結(jié)點(diǎn)的右子結(jié)點(diǎn)），每次往右子結(jié)點(diǎn)轉(zhuǎn)的時(shí)候就更新i，則最后結(jié)點(diǎn)i就是值v0的前趨；后繼類似。
<3>刪除所有值在某區(qū)間內(nèi)的結(jié)點(diǎn)（這個(gè)區(qū)間可以是開(kāi)區(qū)間、閉區(qū)間或半開(kāi)半閉區(qū)間）。
以開(kāi)區(qū)間為例：刪除樹(shù)中所有值在(l, r)范圍內(nèi)的結(jié)點(diǎn)。先找到l的前趨P和r的后繼S（注意這里的前趨和后繼是包括“等于”的），然后將P伸展到根，S伸展到P的右子結(jié)點(diǎn)處，則S的左子樹(shù)中就是所有值在(l, r)范圍內(nèi)的結(jié)點(diǎn)，直接刪掉這棵子樹(shù)即可（注意刪除后要更新S和P）；若改為閉區(qū)間，則將前趨和后繼中的“等于”去掉（即必須是小于或大于）；半開(kāi)半閉區(qū)間則一半按開(kāi)區(qū)間處理，一半按閉區(qū)間處理。問(wèn)題是，如果點(diǎn)P或點(diǎn)S不存在怎么辦。有兩種解決辦法，一是若P和S之一存在，則將其伸展到根，然后直接刪掉其左子樹(shù)或右子樹(shù)即可；若P和S都不存在，則樹(shù)為空，直接將root置為0即可；二是按照sequence的辦法，加入兩個(gè)邊界結(jié)點(diǎn)，當(dāng)前趨或后繼不存在時(shí)就認(rèn)為是邊界結(jié)點(diǎn)。
其實(shí)不光是刪除，在找到了這棵子樹(shù)后可以對(duì)它進(jìn)行一些整體操作，從而讓Splay Tree具有線段樹(shù)的功能（這個(gè)在下面的NOI2005 sequence那一題里面會(huì)總結(jié)）。
<4>插入一棵樹(shù)（當(dāng)然這棵樹(shù)也是Splay Tree，并且原樹(shù)中的結(jié)點(diǎn)值序列與新樹(shù)中的結(jié)點(diǎn)值序列不相交）。
有時(shí)候，題目中會(huì)連續(xù)出現(xiàn)很多插入操作，中間沒(méi)有其它操作，此時(shí)，與其一個(gè)一個(gè)插入，還不如將它們先建成一棵樹(shù)（建樹(shù)的方法在下一篇里總結(jié)），再整體插入。整體插入的方法：設(shè)L和R分別是新樹(shù)里值最小的結(jié)點(diǎn)和值最大的結(jié)點(diǎn)，在原樹(shù)中找到L的前趨P和R的后繼S，將P伸展到根，S伸展到P的右子結(jié)點(diǎn)處，由于原樹(shù)中的結(jié)點(diǎn)值序列與新樹(shù)中的結(jié)點(diǎn)值序列不相交（也就是原樹(shù)中的結(jié)點(diǎn)值要么小于L的值，要么大于R的值），因此S無(wú)左子結(jié)點(diǎn)，此時(shí)將新樹(shù)作為S的左子樹(shù)即可。