長鏈剖分之O(nlgn)-O(1)求k級祖先

本文解決的問題是：

給定一棵n個點的有根樹，在線詢問某個點的k級祖先（即一個點向上跳k次走到的點）。

前置技能：

• 輕重鏈剖分
• 倍增

什麼是長鏈剖分：

它和輕重鏈剖分的區別就是重兒子的定義從所在子樹最大的兒子變成了所在子樹最深的兒子。（子樹深度定義為該子樹內最深的葉子的深度）

為什麼要長鏈剖分：

我們利用的性質是：任意一個點的k級祖先所在鏈的鏈長一定大於等於k。

證明：

如果這個點和他的k級祖先在一條鏈上，那麼結論顯然成立。

反之，如果不在一條鏈上，那麼一開始這個祖先沒有選擇這棵子樹是因為別的子樹更深，故而所在鏈一定是大於k的，結論仍然成立。

演算法步驟：

首先我們進行預處理（時間/空間複雜度）：

1. 對樹進行長鏈剖分，記錄每個點的鏈頭和深度

2. 倍增預處理出每個點2^n級祖先
3. 如果某條鏈的長度是len，那麼在鏈頭處記錄鏈頭向上的len個祖先，並記錄向下的len個鏈的元素
4. 記錄每個數最高位1是多少

對於每次詢問級祖先，我們執行以下步驟：

1. 先利用倍增數組跳的最高位的1層，設剩餘層數為，可以發現

2. 利用之前證明的性質，我們可以發現當前節點所在鏈鏈長一定嚴格大於。如果鏈頭在當前節點的級祖先上面，那麼我們利用鏈頭向下的數組可以得到答案，否則利用向上的數組同樣可以得到答案。

總結：

我們利用了長鏈剖分的特殊性質，以的時間複雜度解決了靜態樹上在線詢問任意點的k級祖先問題。

致謝：

• 感謝@yanQval幫我理清思路

• 感謝@場子提供題圖

推薦閱讀：