[ Minimum Spanning Tree, kruskal, prim ] 最小生成樹經典演算法

以前覺得這應該是很簡單的東西，但我發現網路上使用priority_queue的prim演算法相關程式碼我覺得寫不好，我就把我自己的放上來。這裡順便也放上kruskal的程式碼。

prim $\ord{\left(\abs{V}+\abs{E}\right)\log{\abs{V}}}$:
kruskal $\ord{\abs{V}+\abs{E}\log{\abs{E}}}$:

[ inorder postorder construct tree ] 用中序、後序建樹保證$\ord{N}$的方法

昨天我學長因為要面試，所以努力地刷leetcode的題目，寫到了一題:

• 106. Construct Binary Tree from Inorder and Postorder Traversal  

他雖然AC了但是用的方法不太好，因此跑來問我有沒有看起來很帥速度又快的方法。

因為網路上的code都用一些很慢的方法來建樹，很多都$\ord{N^2}$，雖然也有看似$\ord{N}$的方法，但是用到像是unordered_map之類常數很大也不保證複雜度是$\ord{1}$(codeforces會卡內建hash)。

因為我查到的code都太糟糕了，因此我決定自己寫一個複雜度保證為$\ord{N}$又好寫的方法。

首先是找$root$的部分，因為有給後序的關係很容易就是到是誰了，但是找左右子樹就會出問題。經過觀察，只需要在dfs的過程用stack紀錄一些特別點就可以好好地維護左右子樹。

假設現在dfs在點$u$，stack紀錄的點就是從$root$到$u$的路徑所有點中，除了那些左小孩也在該路徑中的點之外的所有點，有點複雜看個圖會比較明白，紅色的點就是記錄在stack中的點。

至於為什麼記錄這些點就可以在dfs時判斷現在是不是NULL的節點，以及如果給的是preorder的情況就交給讀者思考了
以下附上程式碼:

[ Steiner tree problem in graphs ] 斯坦納樹

斯坦納樹問題是一個世界知名的NP-hard問題。在圖論上的斯坦納樹是對於一張無向圖$G=(V,E)$以及一個點集合$P \subseteq V$，通常會稱$P$集合為$terminal \; set$，對於每條邊$e=(u,v) \in E$，令$w(e)$表示它的權重。我們的目標是要從$G$的所有子圖中找出一棵生成樹$T=(V',E')$，使得$P \subseteq V'$且$\sum_{e \in E'} w(e)$最小。

簡單來說就是在圖$G$上找一棵子樹，可以把$P$中的點連通起來，且邊權總和最小

如果我們枚舉所有子圖，對每個子圖做最小生成樹演算法，就一定可以找到斯坦納樹，但是複雜度是$\ord{(\abs E + \abs V log \abs V ) \times 2^{\abs V}}$，非常糟糕。

如果$w(e)>0 ,e \in E$，且$\abs P \ll \abs V$，我們可以找到一個動態規劃的方法：
令$dp[S][i]$表示以點$i$為根，以$S \subseteq P$為$terminal \; set$構造出來的斯坦納樹，這樣我們最後的答案就會是$dp[P][u \in P]$

狀態轉移式可以寫成這樣

• $dp[S][i]=min(dp[T][j]+dp[S-T][j]+dis(i,j)\; : \; j \in V,T \subset S)$
  $dis(i,j)$表示$i \sim j$的最短路徑

 

任兩點間的最短路徑可以用floyd在$\ord {\abs V^3}$預先算出來，狀態有$2^{\abs P}\times \abs V$個，狀態轉移為$\ord{\abs V \times 枚舉子集合的時間}$，因此總複雜度為$\ord{\abs V^3+2^{\abs P} \times \abs V^2 \times 枚舉子集合的時間 }$

其中 $2^{\abs P} \times 枚舉子集合的時間$ 只是粗略的計算，實際上它是
$$\sum_{i=1}^{\abs P} \binom{\abs P}{i} \times (2^i -1) \simeq \sum_{i=0}^{\abs P} \binom{\abs P}{i} \times 2^i = (1+2)^{\abs P} = 3^{\abs P}$$因此總複雜度可以表示為$\ord{V^3+3^{\abs P} \times \abs V^2}$，但是這其實還可以優化，令$H[j] = min(dp[T][j]+dp[S-T][j] \; : \;T \subset S)$
則$dp[S][i]=min(H[j]+dis(i,j)\; : \;j \in \abs V)$
$H$是可以被預先算出來的，因此總複雜度就降為$\ord{\abs V^3 + \abs V 3^{\abs P}+\abs V^2 2^{\abs P}}$
以下附上程式碼:

有的時候圖是稀疏圖，也就是$\ord V=\ord E$，這種時候用這種算法效率其實不是很好，我們可以在dp的過程才用一些單源最短路徑算法算出最短路徑，這樣複雜度可以變成$$\ord{\abs V 3^{\abs P}+ShortestPath(G) 2^{\abs P}}$$其中$ShortestPath(G)$是在圖$G$中計算最短路徑的時間，用dijkstra的話是$\ord{\abs E+\abs V log \abs V}$，這裡我用SPFA實作:

[ Minimum Arborescence / zhu_liu ] 朱劉算法 - 最小樹形圖

在有向圖中，給定一個點$r$作為生成樹的根，找出有向圖最小生成樹。

首先我們要能保證從$r$能夠走到圖上的所有點，這樣生成樹才會存在，這很簡單，一次DFS即可，再來是把圖上的所有自環移除，因為一顆樹裡面很明顯是不會有自環的。

之後就是算法的主要步驟了，可以先想一下，除了$r$以外的每一個點都有一條儘可能小的邊指向自己，最好的情況就是我們枚舉每一個點（除了根節點）並找到最小的一條指向這個點的邊，如果這些邊不構成有向環，就形成了一個所求的最小樹形圖。

但是實際上會出現環啊，但是這些環一定是獨立的，為甚麼呢？因為只有$|V|-1$條邊啊，只有是一棵樹的時候才會是連通的狀態。換句話說，如果圖連通了，就一定是最小樹形圖。

我們嘗試去換一些邊，使圖連通，在換的過程中我們總是選擇較小的邊，那麼得到的就是最小樹形圖。你可能會去枚舉一些邊把有向環拆掉，但是這樣的話可能會產生新的有向環，不是一個好做法。

朱劉算法就不直接去換邊，它也不去拆掉環，而是在不增加邊的情況下讓圖連通，怎麼做呢？就是用一個新的點代替原來圖的一個環（也就是所謂的「縮點」，和強連通分量有點像），並且修改跟這個環裡的點有關的邊的權值。

為何要修改邊的權重呢？當我們每更換一個點的入邊的時候我們就要去掉原來那個入邊，於是我們把這個點所有可能的入邊全部減少原來選取的那個入邊的權值，這樣每增加一條入邊無形中就刪去了原來那條邊。

上圖中紅色部分是要進行縮點的有向環

每個環上的點所有可能的入邊全部減少原來選取的那個入邊的權值

接著把環縮成一個點就可以了

假設我們想要把原來縮環之前3那條邊換成4那條邊，那我們換完的結果如下:

可以發現修改邊權後，不需要把邊刪掉，直接去計算選取邊的權重和就會和換邊的結果一樣

朱劉算法主算法的過程就是：找最小入邊->判斷有沒有環(沒有環就退出，算法成功)->縮點，改權值，如此反覆，一般來說為了方便不會去記錄縮點後虛擬節點裡包含了那些點，如果需要找出最小樹形圖包含的邊，就必須要真的去記錄他。

時間複雜度來說的話，用當時論文提出的實作方式，修改邊權的部分為$\ord{|E|}$，縮點最多執行$|V|-1$次，所以總複雜度是$\ord{|V|*|E|}$。
我自己有想了一個$\ord{|E| \; log \; |E|}$的方法，需要用到一種可以合併和把裡面所有元素加上某個值 的heap，又因為每個點最多只會連出去$|V|-1$條邊，也就是heap裡面只有$|V|$個元素是有用的，所以可以在heap大小為$2|V|$時把後$|V|$個元素刪掉，用斐式堆可以做到$\ord{|E|+|V| \; log|V|}$。

以下為$\ord{|V|*|E|}$的code:
接著是$\ord{|E| \; log^2|E|}$的code，使用啟發式合併(感謝59491、編譯器幫忙debug):
接著是$\ord{|E| \; log|E|}$的code，使用skew heap:

[ Earley parser ] Earley語法解析器

有一天蚯蚓跟我說CYK算法很慢，推薦了這個東西，所以我就把他寫出來了。
他主要是先建構出類似於自動機的圖，有很多個狀態在跳來跳去，在我的實作裡有將其轉成語法樹的方法。
這裡需要自己實作的有lexer，還有最後的語法一定要有一個gamma rule，gamma rule就是有一個$gamma \Longrightarrow S$，$S$是初始符號。
首先是語法規則的部分:

這是分析器的本體，lexer的部分要自己去完成，lexer的結果會是parse的第二個參數，計算出來一些資料會存在table裡面
以下為模板:

最後是構造語法樹的部分，因為div是一顆左兄弟右兒子的樹，所以要將她轉換成正常的語法樹，還要去記錄曖昧文法的部分:

[ tree centroid ] 樹重心

一棵無向樹\(T=(V,E)\)，定義:
\(w_v(u)\)為點\(u\)的權重，\(u \in V\)
\(w_e(e)\)為邊\(e\)的權重，\(e \in E\)
\(d(u,v)\)為\(u\)到\(v\)路徑的權重和，\(u,v \in V\)

重心的定義是:
以這個點為根，那麼所有的子樹(不算整個樹自身)的大小都不超過整個樹大小的一半
即為最大的子樹最小的點

廣義的樹的重心:
無向樹\(T=(V,E)\)滿足
 \(w_v(u)≧0, \; \forall u \in V \)
 \(w_e(e)>0, \; \forall e \in E \)
設
\(c(u)=\sum_{v \in V}d(u,v)*w_v(v)\)
則樹重心 \(tree \; centroid=u \; | \; min(\{c(u):u \in V\})\)

在
 \(w_v(u)=1, \; \forall u \in V \)
 \(w_e(e)=1, \; \forall e \in E \)
的情況下，就是一般的樹重心

性質:

1. 把兩個樹通過一條邊相連得到一個新的樹，那麼新的樹的重心在連接原來兩個樹的重心的路徑上。
2. 把一個樹添加或刪除一個葉子，那麼它的重心最多只移動一條邊的距離。

用途:
樹分治、動態求樹重心等

可以利用DFS找出最大的子樹最小的點，即為樹重心
樹重心求法(用vector存無向樹):

[ dynamic kd tree ] 動態kd樹模板

參考資料:

• k-d tree教學投影片
• http://andrewd.ces.clemson.edu/courses/cpsc805/references/nearest_search.pdf
• https://cw.fel.cvut.cz/wiki/_media/courses/a4m33pal/paska13.pdf
• 在二維空間的查找優化
• K-D Tree在信息学竞赛中的应用
• K-D tree的估价
• 从K近邻算法、距离度量谈到KD树、SIFT+BBF算法 
• 感謝Morris大大的模板

kd樹的資料在網路上其實滿多的，但很多code效率不高或是功能不全，所以這邊稍微講解一下kd樹基本的一些操作

1. 構造
   現在有一個point序列S[0~n-1]，每個point都包含一個序列d[0~kd-1]表示維度，S[i].d[j]表示第i個點的第j維。
   節點的資料型別定義為node，裡面有l,r兩個指標分別指向左右兩顆子樹，還有一個point pid表示所存的point。
   構造的過程是一個遞迴結構，大致代碼如下:
   當前這個節點的k稱為分裂維度
   
2. 查找
   kd樹支援兩種查找法:
   一、給定一個點p和一個數字k，求離p前k近的點有哪些
   二、給定一個範圍，求範圍內有哪些點
   兩種方法跟一般爆搜有點像，但是利用了kd樹可以做到有效的剪枝，有時候可以判斷被切分出來的範圍內有沒有機會存在前k近點或是在範圍內，直接看模板應該就懂了
3. 刪除
   模板裡沒有附刪除的code所以會寫在這裡。
   首先如果找到要刪除的節點是葉節點直接刪除就好了；如果不是葉節點，假設現在這個點的分裂維度是k，就拿他右子樹第k維最小節點mi去替代他，接著遞迴刪除右子樹的mi；如果沒有右子樹，就拿他左子樹第k維最小節點mi去替代他，然後把左右子樹互換，接著遞迴刪除右子樹的mi。
   
   找到要刪除的點用查找中的第一種方法就好了，這裡p=要刪除的點，k=1，查找的時候順便維護最近節點其位置與其對p的距離，若最近距離!=0則刪除失敗。
   
   那對一個子樹找第k維最小節點呢?方法很簡單，也是遞迴定義的:
   首先如果當前節點o的分裂維度剛好是第k維，則若o有右子樹的話答案必在o的右子樹，否則答案為o，如果o的分裂維度!=k，則遞迴搜尋左右子樹，把得到的答案和o自己進行比較，求最小。
   接下來附上只有刪除操作的模板:
   
   

插入刪除通常配合替罪羊樹使用，插入很簡單模板有就不說了，接下來講一下複雜度:
設N=size(root)

• 構造:
  很明顯就是\(\ord{N \; log \; N}\)就不說了
• 查找:
  已經有人證明了，假設現在的維度有k維，則查找的最差複雜度是\(\ord{N^{1-1/k}}\)
  但是平均狀況下為\(\ord{log \; N}\)
• 插入:
  複雜度為\(\ord{樹的高度}\)，因為是套替罪羊樹，而且重構的時間是\(\ord{N \; log \; N}\)，所以單次插入的均攤時間複雜度是\(\ord{log \; N \; * \; log \; N}\)
• 刪除:
  有三個步驟需要分析，假設現在的維度有k維
  1. findmin:
     最多會遍歷\(\alpha^{(k-1)*(log_{\alpha}N)/k}=N^{1-1/k}\)個節點，所以是\(\ord{N^{1-1/k}}\)
     但實際操作量為\(N^{1-1/k}-n^{1-1/k}\)，n是最小值的子樹大小
  2. nearest:
     就是查找操作，所以是\(\ord{N^{1-1/k}}\)
     但因為是找相同點，可以優化code，所以實際操作量為\(N^{1-1/k}-n^{1-1/k}\)，n是相同點的子樹大小
  3. 刪除操作本身:
     看code明顯就是重複findmin直到把刪除的點變成葉節點為止，會感覺做了很多操作，但是我們發現把所有操作加起來後會=\(\ord{N^{1-1/k}}\)
     設\(o_1,o_2,...,o_d\)=findmin(root)找到的點,findmin(\(o_1\))找到的點,\(...\),要刪除的葉節點，\(n_1,n_2,...,n_d\)=findmin(root)找到的點的子樹大小,findmin(\(o_1\))找到的點的子樹大小,findmin(\(o_2\))找到的點的子樹大小,\(...\),要刪除的葉節點的子樹大小，\(d\)為樹的高度
     複雜度為:
     $$ N^{1-1/k}-n1^{1-1/k}+n1^{1-1/k}-n2^{1-1/k}+n2^{1-1/k}...-nd^{1-1/k}=\ord{N^{1-1/k}} $$

模板裡的code找的是曼哈頓距離，如果要找歐基里德距離只需要修改point裡的dist跟kd tree裡的heuristic即可，以下提供修改方法:
這樣查找時回傳的就是歐基里德距離的平方

以下附只有插入操作的模板:

以下附支援插入刪除的模板:
模板的使用方法請參考:

日月卦長的解題紀錄 [ IOICAMP2016 ] 動態曼哈頓最短距離

[ Maze generation-Randomized Kruskal's algorithm ] 迷宮生成-隨機Kruskal算法

說得通俗點，就是"隨機拆牆"。
一開始假設所有牆都在，也就是圖的每個點都不連通。如果當前不滿足“任意兩個格子間都有唯一路徑”，那麼就隨機選擇一堵牆，要求牆兩端的格子不連通，即它們對應的兩個頂點在兩個不同的連通分量。把這堵牆拆掉，即在後牆兩端的格子對應的頂點間建立一條邊。重複作下去，直到所有的點都在同一個連通分量裡面。
會發現這就是隨機合併點的Kruskal演算法，需要用到並查集

範例生成圖:
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
＃　　　＃　　　　　　　＃　　　＃　　　　　　　＃
＃＃＃　＃　＃　＃　＃＃＃　＃＃＃＃＃＃＃　＃＃＃
＃　　　　　＃　＃　　　＃　　　＃　＃　　　　　＃
＃＃＃＃＃＃＃＃＃　＃＃＃　＃　＃　＃＃＃＃＃　＃
＃　　　　　　　＃　＃　　　＃　　　＃　　　　　＃
＃＃＃　＃＃＃　＃　＃　＃　＃＃＃　＃＃＃　＃＃＃
＃　　　＃　　　＃　　　＃　　　＃　　　　　　　＃
＃＃＃　＃　＃＃＃＃＃　＃＃＃　＃＃＃＃＃　＃＃＃
＃　　　＃　　　　　　　＃　＃　　　　　＃　＃　＃
＃＃＃＃＃＃＃　＃　＃＃＃　＃　＃＃＃＃＃＃＃　＃
＃　　　＃　＃　＃　　　＃　　　　　　　＃　＃　＃
＃　＃＃＃　＃＃＃　＃＃＃　＃　＃＃＃＃＃　＃　＃
＃　＃　　　　　＃　＃　　　＃　＃　＃　＃　＃　＃
＃　＃　＃＃＃　＃　＃＃＃　＃＃＃　＃　＃　＃　＃
＃　＃　＃　　　　　＃　　　＃　　　　　　　　　＃
＃　＃　＃＃＃　＃＃＃＃＃＃＃＃＃　＃　＃＃＃＃＃
＃　　　＃　　　＃　＃　＃　　　　　＃　　　＃　＃
＃＃＃＃＃＃＃　＃　＃　＃　＃　＃＃＃　＃＃＃　＃
＃　　　　　＃　　　　　　　＃　　　＃　　　　　＃
＃　＃　＃＃＃＃＃　＃＃＃＃＃＃＃＃＃　＃　＃＃＃
＃　＃　　　　　　　　　　　　　　　＃　＃　　　＃
＃＃＃　＃　＃　＃＃＃　＃　＃＃＃＃＃＃＃　＃＃＃
＃　　　＃　＃　　　＃　＃　　　＃　　　　　　　＃
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

code(n,m必須是奇數):

[ min-max heap ] 最小-最大堆

最小-最大堆(Min-Max Heaps)是一個完整二元樹。此二元樹是交替的階層方式呈現，分別為最小階層 ( min level ) 和最大階層 ( max level ) ，這裡實作樹根為最小鍵值。

最小-最大堆是一種堆積支援以下幾種操作:

1. 求最大值 - max()
2. 求最小值 - min()
3. 刪除最大值 - pop_max()
4. 刪除最小值 - pop_min()
5. 元素入堆 - push()

詳細演算法可以參考原始論文
Min-Max Heaps and Generalized Priority Queues

如果不懂敘述就看code吧
以下提供模板:

[ link-cut tree ] 動態樹教學+模板

因為code太多容易顯示不出來，這裡有Gist連結
動態樹，一種支持斷邊、連邊的資料結構（要保證是樹或森林），可以維護路徑、但不能維護子樹。
類似於樹鏈剖分（建議先學完樹鏈剖分，再學LCT）。
只不過樹鏈剖分的輕重邊是根據子樹大小而決定的，這棵樹只能是靜態的。
而LCT中的“輕重邊”是根據最後一次操作決定的，最後一次處理了x這個點，那麼從x到根的路徑就是重鏈（每個父親只與一個兒子的連邊為重邊）。
用splay來維護每一條重鏈，以點的深度為關鍵字，即splay中的每個點左兒子深度都比他小，右兒子的深度都比他大（若只有一個點，那麼這個點單獨是一棵splay）。
如果還不知道splay tree的可以參考這裡

splay tree及其節點的一些函數:

定義：

1. Preferred child：
   如果一個點是他父親結點的所有兒子中最後被訪問的，那麼他是他父親的Preferred child。
   每個點最多有一個Preferred child。如果x結點是最後被訪問的點，那麼他沒有Preferred child。
2. Preferred edge:
   每個點到自己的Preferred child的邊叫Preferred edge（相當於樹鏈剖分中的重邊）
3. Preferred path:
   由Preferred edge組成的鏈叫Preferred path（相當於樹鏈剖分的重鏈）

簡單來說就是一個節點在重鏈上的直接兒子定義為preferred child，連向該兒子的邊定義為preferred edge。

access(x):
我們用操作access(x)來表示訪問節點x為LCT的最基礎操作，使x到根結點的路徑成為重鏈。

如上圖，粗邊為重邊。

首先把x旋到他所在的splay的根部。
因為當前的x點是最後一個被訪問的點，所以他沒有Preferred child，因此要把右兒子與他斷開，右兒子成為新的一條鏈。
x的父親是y，把y旋到他所在splay的根結點，把此時y的右兒子與他斷開，把x連過來即可，相當於合併y和x所在的splay。
然後，再找y的父親，合併y與y的父親所在的splay，一直到根結束。
最終，x到根結點的路徑成為新的Preferred edge，而曾經的Preferred child都被拋棄。
有了access操作後，其他的操作就更容易實現了

make_root(x):
將x設為其所在的樹的根
首先access(x)，這樣x與根結點處在同一棵splay中。
設a=access(x)，而a是splay tree的根，因為要讓x成為整棵樹的根，所以x的深度要最小，我們只要在a上加一個區間反轉的標記rev就可以完成。
這裡提供兩種方式，最後都會把節點x轉到splay tree根的位置(這很重要)
1.
2.
link(x,y):
連接x與y所在的兩棵樹。
先判斷是否在同一棵splay tree裡，如果是的話就不做任何事
首先Makeroot(x)，x就成為了他所在樹的根。
然後直接把x的父親賦值為y即可。
cut(x,y):
斷開x與y所相連的邊。
首先Makeroot(x)，然後Access(y)，此時x與y在同一棵splay中，再Splay(y)，此時x是y的左兒子，然後將其左兒子及左兒子的父母設成空節點即可。
cut_parents(x):
跟cut類似，斷掉x和其父親節點之間的邊。首先access節點x。然後讓x旋轉到所在輔助樹的根節點上。斷掉左子樹。
find_root(x):
尋找點x在所在樹的根節點。這個操作很簡單，我們只要對x做一次access操作，這樣x和它的根就應該在一個splay中了。那麼此時的根就應該是這個splay最左邊的節點。
因為是splay tree，所以在搜尋完後仍要進行splay操作
對於很多問u到v的路徑問題，我們可以將u到v的路徑構造成一顆splay tree並求出其根節點維護的值即可。
如果要不改變根節點的話可以求出LCA再進行處理，以下用u,v路徑上的點權總和為例:
修改點權:
將一棵有邊權的樹構建成link cut tree:
查詢這棵樹的邊權，因為不能改變root，所以要對access函數作一點修改，以下以u,v路徑上的最大值為例:
查詢只需要這樣寫就好了:

[ Lowest Common Ancestor , LCA Euler Tour Technique ] 最近共同祖先樹壓平轉RMQ算法

想法就是把樹壓平，然後紀錄當前節點u的深度在dep[u]，紀錄時間戳記，進入的時候要紀錄一次，出來的時候也要記錄，把當前點u進入的時間戳紀錄在in[u]中，時間戳的大小為2*n，所以必須用兩倍的記憶體來維護。之後就轉成RMQ問題
查詢a,b兩點的LCA=dep[in[a]]到dep[in[b]]中，最小深度的時間戳經過的那個點
查詢:
RMQ的部分就要自己維護了，使用線段樹效能會非常差，在n,q<=100000的情況下使用稀疏表的效能與使用樹鏈剖分的效能差不多

[ Lowest Common Ancestor , LCA Doubling Search ] 最近共同祖先倍增演算法

首先建立一張倍增表，pa[i][x]表示x的第\(2^i\)的祖先，若不存在則為\(-1\)，可以在DFS或BFS的過程中求得，複雜度為\(\ord{N*MAX\_LOG}\)

對於每筆詢問，我們可以利用剛剛求得的倍增表，在\(\ord{MAX\_LOG}\)的時間在線查詢
先將要查詢的a,b兩點較深的點移至較淺的點的深度，之後二分搜LCA的位置
附上模板:

[ Lowest Common Ancestor , LCA Tarjan's Algorithm ] 最近共同祖先tarjan演算法

tarjan算法的步驟是(當dfs到節點u時):

在並查集中建立僅有u的集合,設置該集合的祖先為u
對u的每個孩子v:

1. 遞迴處理v
2. 合併v的集合到父節點u的集合,確保集合的祖先是u

設置u為已遍歷
處理關於u的查詢,若查詢(u,x)中的x已遍歷過,則LCA(u,x) = x所在的集合的祖先

因為只進行過一次DFS，所以複雜度為\(\ord{(N+Q)*\alpha(N)}\)，為了優化並查集，這裡採用啟發式合併，因此為了記錄集合的祖先而外增加了一個數組head
其雖為線性，但是效率並不怎麼好，跟倍增法的效能差不多
使用方法也很簡單，只需要將每個詢問的兩點記錄起來即可

[ Heavy-Light Decomposition ] 樹鏈剖分模板+LCA

在某些狀況下，我們希望對樹上a點到b點的路徑進行修改或查詢的動作，而且這些動作用一般的樹壓平RMQ或是離線處理無法完成的，這個時候我們可以利用特殊的方法將樹拆成長鏈。
長鏈可以搭配良好的資料結構。只要找出樹上所有長鏈，每條長鏈套用線段樹、BIT、Sparse Table、BST、Heap，就能降低時間複雜度。

可以利用簡單的做法將dfs序切成許多長鏈:

1. 首先先設定其中一點為根，算出每個子樹有多少節點
2. 樹上每個節點各自連向最大的子樹，相連的部分會自然形成鏈

通常步驟二會進行一次dfs，每次朝著最大的子樹走，每個節點記錄其時間戳記及所在的鏈(通常是記鏈首)，這樣就可以將樹壓平的結果切成許多鏈，使得樹鏈剖分同時可以做到樹壓平的操作。

我們可以進行一個簡單的證明:

• 假設節點數為V，由根往任意葉節點走，一旦遇到新鏈，新鏈的子樹必小於等於原鏈子樹，剩下的節點數量不到一半，所以沿途最多遇到 logV 條鏈。

因為一條路徑藉由 LCA 拆成兩段，沿途最多遇到 2*logV 條鏈，所以在任意兩點a,b間最多只需要進行2*logV次的區間操作，若是套線段樹之類的結構可以做到\(\ord{log^2V}\)
這些操作都可以在求LCA的過程中完成:

若樹鏈剖分的目的只是為了求LCA，build_link()及find_lca()有更好的做法:
這就只需進行一次DFS

[ Persistent Binary Index Tree ] 持久化BIT

(二分索引樹)BIT是一種容易實現的資料結構，但在持久化的應用上是非常困難的，但我們可以犧牲些許的複雜度來簡化其實現方式

一般區間和的BIT長這樣:

這是持久化的版本(也可以用pair來實作):
可以知道其更新的複雜度為\(\ord{logN}\)，查詢複雜度為\(\ord{logN*logQ}\)，Q是查詢次數

[ Suffix Automaton ] 後綴自動機

定義字串S的後綴自動機是一種自動機可以接受S的所有後綴，其狀態最多為2*strlen(s)-1個，雖然理論複雜，但其構造方式十分簡單，且它可以用來處理一些後綴數組或事後綴樹的問題，因此是一個十分強大的資料結構。
後綴自動機大致的構造方式是將字串擔一字元按順序進行插入，插入的均攤時間為\(\ord 1\)，關於詳細的情形可以在 http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html 這個網站中得到
而關於複雜度及詳細的證明請參考陈立杰的簡報
關於狀態數為線性的證明在19~21頁，有詳細的圖文解說
這個網站包含其一些延伸資料結構http://maskray.me/blog/2013-05-10-suffix-automaton
為了減少記憶體的使用，以vector代替指標維護狀態
以下提供模板:

[ Aho-Corasick Automaton ] AC自動機

Aho-Corasick Automaton，該算法在1975年產生於貝爾實驗室，是著名的多模匹配算法之一
在了解AC自動機之前，必須先學會字典樹Trie的使用，簡單的來說，他是將KMP的fail函數應用在Trie做為失敗邊。
有\(n\)個字串\(B_0,B_1,...,B_{n-1}\) 要匹配字串\(A\)，則一般用KMP的算法會得到\(\ord{\sum_{i=0}^{n-1}(|A|+|B_i|)}\)，使用AC自動機的演算法其複雜度為\(\ord{|A|+\sum_{i=0}^{n-1}|B_i|}\)，必須用DP

關於AC自動機的介紹請看這裡

以下為AC自動機的模板

[ skew heap ] implementation 斜堆 實作

斜堆(Skew heap)也叫自適應堆(self-adjusting heap)，它是(重量)左偏樹的一個變種。
相較於(重量)左偏樹，斜堆不需記錄其高度或是節點個數(size)等附加域，其合併(merge)的方式也較為簡潔，效率也較高。和(重量)左偏樹一樣，斜堆的push、pop的時間複雜度為\(\ord{log \; n}\)、查詢最值為\(\ord 1\)。
關於複雜度分析
以下提供斜堆的實作，使用方法與STL priority_queue相似

[ basic operation of naive order statistic tree ] 樸素二元搜尋樹 名次樹的基本操作

一般的名次樹支援以下幾種操作:

1.插入
2.刪除
3.查找
4.求節點大小
5.求元素名次
6.求第k大
7.求前驅
8.求後繼

之前寫的模板已經有了前六種操作，因此我會在本模板中附上求前驅跟後繼的操作
前驅與後繼並不是名次樹才有的操作，在不記錄節點大小的情形下也能求得
關於求前驅跟後繼操作的說明可以參考 随机平衡二叉查找树Treap的分析与应用 這篇文章

以下提供模板:

[ AA tree ] AA樹

AA樹是紅黑樹的一種變種，是Arne Andersson教授在1993年年在他的論文"Balanced search trees made simple"中介紹，設計的目的是減少紅黑樹考慮的不同情況。區別於紅黑樹的是，AA樹的紅結點只能作為右葉子。另外AA樹為實現方便，不再使用紅黑兩種顏色，而是用level標記結點，結點中的level相當於紅黑樹中結點的黑高度。

其主要透過skew和split兩種旋轉來進行平衡的，插入時只能為紅節點，故會出現不符合其規定則進行平衡操作

若想進一步了解其平衡操作請參考維基百科
在實作中，skew為右璇，split為左旋。本模板以rotate(o,0)、rotate(o,1)代表

以下提供模板: