樹
建議閱讀順序（有些沒有嚴格的順序關系）：
線段樹 \(\rightarrow\) 輕重鏈剖分（長短鏈剖分） \(\rightarrow\) \(LCA\&LA\) \(\rightarrow\) 全域平衡二叉樹 \(\rightarrow\) 動態樹
資料結構
線段樹
https://www.cnblogs.com/efX-bk/p/segment_tree.html
動態樹
https://www.cnblogs.com/efX-bk/p/basic_dynamic_tree.html
全域平衡二叉樹
需要會樹鏈剖分
先重鏈剖分，重鏈剖分中，跳輕邊的次數為 \(O(\log n)\) 的，然后用一個資料結構（線段樹之類的）維護了重鏈上的資訊
但在重鏈上維護資訊可以做到更優，考慮把重鏈表示成一顆二叉樹，滿足：
1.這棵樹的中序遍歷是重鏈按深度遍歷的結果，
2.二叉樹上的節點關于輕子樹的大小是最平衡的
第一點容易滿足，第二點可以用更為形象的解釋：把重鏈轉為序列，以每個點輕子樹的大小+1 為加權求加權中點作為根，然后遞回到左右兩邊
稱二叉樹上的邊為重邊，其余邊為輕邊
由于是重鏈剖分，跳一次輕邊 \(size_{當前點}\) 至少加倍，至多跳 \(O(\log n)\) 次
由性質2，跳一次重邊 \(size_{\text{輕子樹}}\) 至少加倍，至多跳 \(O(\log n)\) 次
于是一共只會跳 \(O(\log n)\) 次，但比起重鏈剖分的好處是我們用子樹替代了序列，而子樹操作常常容易做到 \(O(1)\)（細節還是很多的，比如要判斷有沒有右子樹什么的）
上面說的只適用于鏈的操作，如果是子樹操作就需要把所有輕兒子往上放，訪問到時就取出來，子樹操作就對于所有輕兒子都打一個標記，重兒子特判一下
Trick
輕重鏈剖分
從某個點出發 dfs 整顆樹，遇到一個新點就給它一個新的編號，這樣一個子樹就是連續的一段編號，這種方式被稱為 \(dfs\) 序
\(dfs\) 序雖然解決了子樹問題，但不能解決鏈上的問題，考慮把一條鏈拆成若干段連續的 \(dfs\) 序
\(siz_x\) 表示以 \(x\) 為根的子樹的大小
定義一個點 \(u\) 所有子樹中 \(siz\) 最大的是 \(u\) 的重兒子，記為 \(son_u\)，其他兒子都是輕兒子
這樣，從一個點出發，我們優先遍歷重兒子，這樣顯然不會破壞 \(dfs\) 序的性質
一個點到重兒子的邊記為重邊，其他邊記為輕邊
發現
\[siz_{son}>siz_{\text{輕兒子}} siz_u=siz_{son_u}+\sum siz_{u\text{的輕兒子}} \]轉化一下就是
\[siz_{u\text{的輕兒子}}\le \frac 12siz_u \]所以跳一次輕邊 \(siz\) 至少加倍，且不會超過 \(n\)，于是從任意節點到根節點至多跳 \(O(\log n)\) 次輕邊，而重邊上的 \(dfs\) 序是連續的，于是就可以把任意一段樹鏈分為 \(O(\log n)\) 段連續的 \(dfs\) 序區間了
長短鏈剖分
就是把上面重兒子的定義改為深度最大的兒子
LCA&LA
都很容易做到在線 \(O(\log n)\)
但可以在靜態樹的情形下優化到 \(O(n)\) 預處理，\(O(1)\) 在線詢問
首先介紹歐拉序：
就是遍歷所有節點，掃到一次就往一個序列尾部插入該節點，這個序列就是歐拉序，（很多時候只記錄第一次和最后一次就夠了）
不難說明歐拉序的大小為 \(O(n)\)
在歐拉序上關于深度建立 ST 表就可以做到 \(O(n\log n)-O(1)\) 的復雜度做 LCA
為了避免建表的復雜度，對于序列進行塊長為 \(\frac {\log n}{2}\) 的分塊，對于塊間建立 ST 表，就抵消了建表的 \(\log n\)，變成 \(O(n)\) 了
再考慮散塊，對于歐拉序，相鄰節點的深度差只能為 \(\pm1\)，而我們只關心最大/小值所在的位置，即我們只關注塊內的差分，于是本質不同的塊的種數只有
\[2^{\frac{\log n}{2}}=\sqrt n \]塊內暴力處理所有可能的區間只是 \(O(\log^2 n)\) 的，復雜度為 \(O(\sqrt n\log^2 n)\)，不是瓶頸
然后 LCA 就優化到了理論最優
再來看 LA
樸素的做法是先長鏈剖分，預處理每個點的 \(2^i\) 級祖先
有如下引理
一個點的 \(k\) 級祖先所在的長鏈長度不小于 \(k\)
如果該點和其 \(k\) 級祖先在一條長鏈上，結論顯然成立
如果不在一條長鏈上，顯然可以把該點映射到祖先所在長鏈上深度相同的位置（因為長鏈是最深的，該點不是長鏈，一定不可能更深），然后就轉化為上一種情況了
利用上述引理，對于所有鏈頂，設其對應鏈長為 \(len\)，記錄上下 \(len\) 個點
對于一次詢問，先向上跳 \(2^{highbit(k)}\) 步，設
\[k=k^\prime+2^{highbit(k)} \]則只需再跳 \(k^\prime\) 步，發現
\[k^\prime<\frac k2 \]由引理，此時已經在祖先所在的長鏈上了，按照鏈頂存盤的點就可以 \(O(1)\) 查找了
與 LCA 類似，暴力做法也是 \(O(n\log n)-O(1)\) 的，依然考慮減小樹的規模
可以暴力的把大小恰好不超過 \(\frac {\log n}{4}\) 的子樹從原樹上剪下來，就得到一顆葉子結點數目不超過 \(O(\frac {n}{\log n})\) 的新樹
每個點都可以 \(O(1)\) 對應到葉子上，設詢問節點到任一葉子的距離為 \(d\)，那么對應葉子的 \(k+d\) 的級祖先就是詢問節點的 \(k\) 級祖先
于是只需要對葉子做暴力的預處理，復雜度 \(O(n)\)
如果詢問的是剪下來的小樹上的節點，依然是一樣的思路：考慮本質不同的大小為 \(\frac {\log n}{4}\) 的有根樹有多少種
然后發現就是括號序列的種數，于是就是
\[B=\frac {\log n}{4}\\ S=\frac {C_{2B}^B}{B+1} \]\(S\) 就是答案
用 \(dep\) 表示一種樹的最大深度，如果 \(k>dep\) 那就轉換到減去了子樹的新樹上，否則就暴力預處理，復雜度
\[O(SB^2)=O(4^{\frac{\log n}{4}}\log^2n)=O(\sqrt n\log^2n)<O(n) \]然后就可以 \(O(n)-O(1)\) 了
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/482113.html
標籤：C++
下一篇：C++ string 字串類詳解