1. 從一次線上故障說起為什么LCA值得你花時(shí)間搞懂去年幫一個(gè)朋友排查他們內(nèi)部工具的一個(gè)性能問題場景很典型一個(gè)組織架構(gòu)樹大概三萬多節(jié)點(diǎn)每次要計(jì)算兩個(gè)員工在組織樹里的最近共同上級。他們最初的實(shí)現(xiàn)是暴力往上爬——把A的所有祖先塞進(jìn)一個(gè)集合然后B從自己開始往上走遇到的第一個(gè)在集合里的節(jié)點(diǎn)就是答案。單次查詢看著不慢幾十毫秒但架不住前端一個(gè)頁面要批量算幾百對頁面直接卡到轉(zhuǎn)圈。這個(gè)問題的本質(zhì)就是LCALowest Common Ancestor最近公共祖先。聽起來像是算法競賽里的東西但只要你處理過任何樹形結(jié)構(gòu)——組織架構(gòu)、文件目錄、DOM節(jié)點(diǎn)、分類體系、依賴關(guān)系圖——你遲早會撞上它。而且一旦數(shù)據(jù)量上去暴力解法就會原形畢露。這篇內(nèi)容我打算把LCA這件事從頭到尾講透。不是那種背個(gè)倍增模板就完事的講法而是把為什么會有多種解法、每種解法到底在權(quán)衡什么、什么場景該選哪個(gè)、寫的時(shí)候哪里最容易翻車這些真正影響你落地的東西說清楚。適合已經(jīng)會寫基礎(chǔ)樹遍歷、但一遇到樹上路徑查詢就發(fā)怵的開發(fā)者也適合想系統(tǒng)梳理一遍這塊知識的老手。看完你應(yīng)該能做到拿到一個(gè)問題先判斷它是不是LCA再根據(jù)數(shù)據(jù)規(guī)模和查詢次數(shù)直接選出合適的方案而不是無腦套模板。2. LCA到底在解決什么問題把共同祖先翻譯成人話2.1 用家族樹理解最近公共祖先先把這個(gè)概念用最樸素的方式說清楚。想象一棵家族樹根節(jié)點(diǎn)是最老的祖先往下每一層是下一代。現(xiàn)在給你兩個(gè)人問他倆血緣關(guān)系最近的那個(gè)共同長輩是誰注意最近兩個(gè)字是關(guān)鍵。往上數(shù)所有共同的長輩都算公共祖先但我們要的是**深度最大離他倆最近**的那一個(gè)。比如你和你堂哥你們的爺爺是LCA但曾祖父也是共同祖先只不過曾祖父更遠(yuǎn)不是最近的。形式化一點(diǎn)給定一棵有根樹對于節(jié)點(diǎn)u和vLCA(u, v)是同時(shí)滿足是u的祖先且是v的祖先的節(jié)點(diǎn)中深度最大的那個(gè)。這里祖先通常包含節(jié)點(diǎn)自己——也就是說如果u本身就是v的祖先那LCA就是u。這個(gè)約定很重要很多實(shí)現(xiàn)細(xì)節(jié)都跟它有關(guān)。2.2 為什么暴力爬樹會崩復(fù)雜度賬要算清楚最直覺的做法有兩種。第一種是剛才說的集合法把u到根的路徑全標(biāo)記然后v往上走找第一個(gè)標(biāo)記點(diǎn)。第二種是先把兩個(gè)節(jié)點(diǎn)提到同一深度然后一起往上走直到相遇。這兩種做法單次查詢的復(fù)雜度都是O(樹高)。問題就出在這個(gè)樹高上。如果樹比較平衡高度是log級別那還行但現(xiàn)實(shí)中的樹經(jīng)常退化成一條鏈——比如一個(gè)層層審批的組織、一個(gè)深度嵌套的目錄、一條長依賴鏈。這時(shí)候樹高就是節(jié)點(diǎn)數(shù)n單次查詢O(n)查詢m次就是O(nm)。三萬個(gè)節(jié)點(diǎn)、幾百次查詢直接就是千萬級操作卡頓是必然的。所以LCA的核心矛盾就一句話能不能把單次查詢從O(樹高)壓到O(log n)甚至O(1)代價(jià)是預(yù)處理。后面講的所有算法本質(zhì)上都是在這條權(quán)衡線上找不同的位置。2.3 哪些真實(shí)場景會用到LCA別以為這只是刷題用的。我梳理幾個(gè)實(shí)際會碰到的組織架構(gòu)/權(quán)限系統(tǒng)判斷兩個(gè)員工的共同上級用于審批流、權(quán)限繼承、匯報(bào)關(guān)系展示。文件系統(tǒng)求兩個(gè)路徑的最近公共目錄做相對路徑計(jì)算、文件同步的差異定位。前端DOM操作找兩個(gè)節(jié)點(diǎn)的最近公共父節(jié)點(diǎn)用于事件委托、選區(qū)處理、虛擬DOM diff。版本控制/依賴分析在提交歷史或依賴樹里找共同基點(diǎn)判斷分支從哪分叉。生物信息學(xué)進(jìn)化樹里找物種的共同祖先。網(wǎng)絡(luò)路由在某些樹形拓?fù)淅镎夜餐嫌喂?jié)點(diǎn)。看出來了吧只要你的數(shù)據(jù)是樹形或者能轉(zhuǎn)成樹形LCA就是個(gè)繞不開的基礎(chǔ)操作。理解了它等于拿到了一把處理樹形查詢的萬能鑰匙。3. 倍增法最通用的LCA解法也是面試最愛問的3.1 倍增的核心思想用二進(jìn)制跳躍代替一步步爬倍增法Binary Lifting是我最推薦的入門方案因?yàn)樗ㄓ?、好寫、好調(diào)而且能順帶解決一堆衍生問題比如求路徑上第k個(gè)祖先、路徑長度等。它的核心思想特別巧妙與其一步一步往上爬不如一次跳2的冪次步。就像你要走1000米不會一米一米挪而是先走512米、再256米……用二進(jìn)制拆分快速到達(dá)。具體做法是預(yù)處理一個(gè)跳表up[i][j]表示節(jié)點(diǎn)i往上跳2^j步后到達(dá)的祖先。這個(gè)表可以遞推出來up[i][0] parent[i] // 跳1步就是父節(jié)點(diǎn) up[i][j] up[ up[i][j-1] ][j-1] // 跳2^j步 先跳2^(j-1)再跳2^(j-1)第二行的遞推是整個(gè)算法的靈魂。它把跳一大步拆成跳兩小步從而能用已經(jīng)算好的小步結(jié)果推出大步結(jié)果。這就是典型的動(dòng)態(tài)規(guī)劃思想也是倍增法名字的由來。3.2 預(yù)處理一遍DFS把跳表建起來預(yù)處理分兩步。第一步是DFS/BFS求出每個(gè)節(jié)點(diǎn)的深度depth[i]和直接父節(jié)點(diǎn)parent[i]。第二步就是按上面的遞推式填up表。關(guān)于j的上界取LOG ceil(log2(n)) 1就夠了。因?yàn)闃渥罡遪層任何跳躍需求都能用不超過log2(n)位的二進(jìn)制表示。多留一位是防止邊界越界。import sys sys.setrecursionlimit(300000) def preprocess(n, adj, root): LOG (n).bit_length() # 等價(jià)于 ceil(log2(n1)) depth [0] * (n 1) up [[0] * LOG for _ in range(n 1)] # 迭代式DFS避免遞歸爆棧 parent [0] * (n 1) order [] stack [root] visited [False] * (n 1) visited[root] True while stack: u stack.pop() order.append(u) for v in adj[u]: if not visited[v]: visited[v] True parent[v] u depth[v] depth[u] 1 stack.append(v) # 填跳表 for i in range(1, n 1): up[i][0] parent[i] for j in range(1, LOG): for i in range(1, n 1): up[i][j] up[ up[i][j-1] ][j-1] return depth, up, LOG這里有個(gè)實(shí)操細(xì)節(jié)值得說我強(qiáng)烈建議用迭代式DFS而不是遞歸。遞歸寫起來是簡潔但樹一深比如退化成鏈Python默認(rèn)遞歸深度1000直接爆棧C雖然棧大一些但幾萬層也懸。迭代式雖然代碼長一點(diǎn)但穩(wěn)。這個(gè)坑我踩過不止一次線上環(huán)境可不會給你調(diào)遞歸深度的機(jī)會。3.3 查詢先對齊深度再一起往上跳查詢LCA(u, v)分兩個(gè)階段邏輯非常清晰階段一把深的那個(gè)提到和淺的一樣深。假設(shè)depth[u] depth[v]那就把u往上跳depth[u] - depth[v]步。這個(gè)差值用二進(jìn)制拆解對應(yīng)到跳表上就是如果差值的第j位是1就跳2^j步。階段二如果此時(shí)u v說明v本來就是u的祖先直接返回。否則兩個(gè)節(jié)點(diǎn)一起往上跳從大到小嘗試。關(guān)鍵技巧是只要跳完之后兩個(gè)節(jié)點(diǎn)還不相等就跳。這樣最后一定會停在LCA的正下方再往上一步就是答案。def lca(u, v, depth, up, LOG): if depth[u] depth[v]: u, v v, u # 階段一對齊深度 diff depth[u] - depth[v] for j in range(LOG): if diff (1 j): u up[u][j] if u v: return u # 階段二一起往上跳 for j in range(LOG - 1, -1, -1): if up[u][j] ! up[v][j]: u up[u][j] v up[v][j] return up[u][0]階段二那個(gè)從大到小的循環(huán)方向特別重要必須從高位往低位試。因?yàn)槲覀円M可能跳得遠(yuǎn)但又不能跳過LCA。從大往小試能保證最后停在最近的位置。如果從小到大試會跳得不夠遠(yuǎn)邏輯就錯(cuò)了。這個(gè)細(xì)節(jié)很多人第一次寫會搞反。3.4 倍增法的復(fù)雜度與適用邊界預(yù)處理時(shí)間O(n log n)空間O(n log n)單次查詢O(log n)。這個(gè)復(fù)雜度對于絕大多數(shù)場景都夠用了。它的優(yōu)勢是通用性極強(qiáng)不要求樹是靜態(tài)的雖然動(dòng)態(tài)更新跳表比較麻煩能處理任意形態(tài)的樹還能順便支持求第k個(gè)祖先這類操作。缺點(diǎn)是空間是n log n如果n到了百萬級內(nèi)存會有點(diǎn)吃緊。提示如果n特別大比如10^6以上而查詢次數(shù)不多其實(shí)暴力法反而更劃算。別迷信高級算法選型要看具體數(shù)據(jù)規(guī)模。4. Tarjan離線算法查詢多、樹不動(dòng)時(shí)的效率之王4.1 離線思維把所有查詢攢起來一起算倍增法是在線的——來一個(gè)查詢答一個(gè)。但如果你的場景是一次性拿到所有查詢?nèi)缓笈砍鼋Y(jié)果那Tarjan離線算法往往更快。Tarjan的核心是DFS 并查集。它利用DFS的回溯特性在遍歷樹的過程中順便把所有查詢都解決了。單次查詢的均攤復(fù)雜度接近O(1)整體是O(n m·α(n))其中α是并查集的反阿克曼函數(shù)實(shí)際可以當(dāng)成常數(shù)。這個(gè)思路的巧妙之處在于它把查詢這件事融進(jìn)了遍歷里而不是遍歷完再單獨(dú)查。對于查詢量巨大的場景比如m和n同量級甚至更大這個(gè)優(yōu)勢非常明顯。4.2 并查集在這里扮演什么角色理解Tarjan的關(guān)鍵是搞懂并查集維護(hù)的是什么。在DFS過程中每個(gè)節(jié)點(diǎn)有三種狀態(tài)未訪問、正在訪問在遞歸棧里、已訪問完子樹處理完畢。并查集維護(hù)的是已訪問完的節(jié)點(diǎn)的集合并且每個(gè)集合的代表元指向它當(dāng)前能追溯到的、還在遞歸棧里的那個(gè)祖先。當(dāng)DFS訪問到節(jié)點(diǎn)u處理所有跟u相關(guān)的查詢(u, v)時(shí)如果v還沒訪問跳過等以后v被訪問時(shí)再處理這對查詢。如果v已經(jīng)訪問完了那么v所在并查集集合的代表元就是LCA(u, v)。為什么因?yàn)関已經(jīng)處理完說明v的整棵子樹都遍歷過了而u還在棧里說明u是v的某個(gè)祖先方向上的節(jié)點(diǎn)。此時(shí)v能追溯到的、還在棧里的最深祖先恰好就是它和u的分叉點(diǎn)也就是LCA。4.3 完整實(shí)現(xiàn)與關(guān)鍵細(xì)節(jié)def tarjan_lca(n, adj, root, queries): # queries[u] [(v, query_id), ...] parent list(range(n 1)) # 并查集 ancestor [0] * (n 1) # 集合代表元對應(yīng)的祖先 visited [False] * (n 1) answer [0] * len(queries) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] # 路徑壓縮 x parent[x] return x def dfs(u): visited[u] True ancestor[find(u)] u for v in adj[u]: if not visited[v]: dfs(v) parent[find(v)] find(u) # 合并子樹到u ancestor[find(u)] u # 處理與u相關(guān)的查詢 for (v, qid) in queries[u]: if visited[v]: answer[qid] ancestor[find(v)] dfs(root) return answer幾個(gè)容易翻車的點(diǎn)第一ancestor的更新時(shí)機(jī)。每次合并完子樹后要把合并后集合的ancestor重新指向u。因?yàn)楹喜⒑蟠碓赡茏兞瞬桓戮蜁玫藉e(cuò)誤的祖先。第二查詢要存雙向。因?yàn)樘幚?u,v)時(shí)可能v還沒訪問得等v被訪問時(shí)從v那邊再處理一次。所以queries[u]和queries[v]都要存這條查詢。第三遞歸深度問題。跟倍增法一樣深樹會爆棧。生產(chǎn)環(huán)境建議改迭代或者手動(dòng)加大?？臻g。4.4 什么時(shí)候該選Tarjan而不是倍增判斷標(biāo)準(zhǔn)很簡單維度倍增法Tarjan離線查詢模式在線來一個(gè)答一個(gè)離線必須預(yù)先知道所有查詢單次查詢O(log n)均攤O(α(n))≈O(1)預(yù)處理O(n log n)無獨(dú)立預(yù)處理空間O(n log n)O(n m)實(shí)現(xiàn)難度中等中等偏上并查集易錯(cuò)適用場景查詢少、需在線查詢海量、可離線如果你的查詢次數(shù)m遠(yuǎn)大于nTarjan的均攤優(yōu)勢會非常明顯。但如果查詢是流式的、必須即時(shí)回答那只能選倍增。選型的第一原則永遠(yuǎn)是先搞清楚你的查詢模式。5. 歐拉序 RMQ把LCA變成區(qū)間最值問題5.1 一個(gè)漂亮的轉(zhuǎn)化LCA等價(jià)于區(qū)間最小值這是我覺得LCA里最優(yōu)雅的一個(gè)思路。它把樹上問題轉(zhuǎn)化成了數(shù)組上的區(qū)間查詢問題。做法是對樹做一次DFS記錄歐拉序也叫DFS序的擴(kuò)展版——每次進(jìn)入一個(gè)節(jié)點(diǎn)記一次每次從子樹返回父節(jié)點(diǎn)時(shí)也記一次。這樣得到的序列長度是2n-1。同時(shí)記錄每個(gè)節(jié)點(diǎn)在序列中第一次出現(xiàn)的位置first[u]。關(guān)鍵結(jié)論LCA(u, v)就是歐拉序中first[u]到first[v]這段區(qū)間里深度最小的那個(gè)節(jié)點(diǎn)。為什么因?yàn)閺膗走到v在歐拉序上必然經(jīng)過它們的LCA而且LCA是這段路徑上深度最小的點(diǎn)。這個(gè)性質(zhì)把LCA問題完美地轉(zhuǎn)化成了**RMQ區(qū)間最小值查詢**問題。5.2 稀疏表ST表實(shí)現(xiàn)O(1)查詢既然變成了RMQ那就可以用經(jīng)典的ST表Sparse Table來做到O(1)查詢。ST表的預(yù)處理是O(n log n)查詢O(1)。import math def build_euler(n, adj, root): euler [] # 歐拉序存節(jié)點(diǎn) depth_arr [] # 對應(yīng)深度 first [0] * (n 1) visited [False] * (n 1) def dfs(u, d): visited[u] True first[u] len(euler) euler.append(u) depth_arr.append(d) for v in adj[u]: if not visited[v]: dfs(v, d 1) euler.append(u) depth_arr.append(d) dfs(root, 0) return euler, depth_arr, first def build_st(depth_arr): m len(depth_arr) LOG m.bit_length() # st[i][j] 存區(qū)間 [i, i2^j-1] 中深度最小的節(jié)點(diǎn)在depth_arr中的下標(biāo) st [[0] * LOG for _ in range(m)] for i in range(m): st[i][0] i for j in range(1, LOG): for i in range(m - (1 j) 1): left st[i][j-1] right st[i (1 (j-1))][j-1] st[i][j] left if depth_arr[left] depth_arr[right] else right return st def query_lca(u, v, first, depth_arr, st, euler): l, r first[u], first[v] if l r: l, r r, l length r - l 1 k length.bit_length() - 1 left st[l][k] right st[r - (1 k) 1][k] idx left if depth_arr[left] depth_arr[right] else right return euler[idx]5.3 歐拉序方案的取舍這個(gè)方案的優(yōu)勢是查詢O(1)比倍增的O(log n)還快。而且思路清晰一旦理解了歐拉序的性質(zhì)代碼其實(shí)不難寫。但它有幾個(gè)明顯的代價(jià)空間更大歐拉序長度是2n-1ST表又是(2n) log(2n)比倍增的n log n大一倍左右。預(yù)處理常數(shù)大建ST表的雙重循環(huán)實(shí)際跑起來比倍增的預(yù)處理慢。只適合靜態(tài)樹樹一變整個(gè)歐拉序和ST表都要重建。所以我的經(jīng)驗(yàn)是如果查詢量極大且樹完全靜態(tài)歐拉序ST表是最優(yōu)解否則倍增法更省心。別為了那點(diǎn)查詢速度提升把代碼復(fù)雜度拉高一大截維護(hù)成本也是成本。注意歐拉序的DFS同樣有遞歸深度問題。而且歐拉序長度是2n如果n很大光是存這個(gè)序列就要不少內(nèi)存選型前先估一下。6. 四種解法橫向?qū)Ρ纫粡埍韼湍阕鲞x型決策前面講了四種主流方案這里做個(gè)系統(tǒng)對比方便你直接查表決策。方案預(yù)處理單次查詢空間在線/離線最適合的場景暴力爬樹O(1)O(樹高)O(n)在線樹淺、查詢極少倍增法O(n log n)O(log n)O(n log n)在線通用首選查詢中等Tarjan離線無均攤O(α(n))O(nm)離線查詢海量、可離線歐拉序STO(n log n)O(1)O(n log n)在線查詢極多、樹靜態(tài)選型的決策鏈路我一般是這么走的第一步看查詢模式。流式在線查詢排除Tarjan能批量離線Tarjan值得考慮。第二步看數(shù)據(jù)規(guī)模。n小幾千以內(nèi)且查詢少暴力法最省事別過度設(shè)計(jì)。n大且查詢多上倍增或歐拉序。第三步看樹是否靜態(tài)。樹會動(dòng)態(tài)變化倍增法改起來相對可控雖然也麻煩歐拉序基本要重建。第四步看查詢次數(shù)。查詢次數(shù)遠(yuǎn)超n歐拉序的O(1)優(yōu)勢才體現(xiàn)得出來否則倍增的O(log n)完全夠用。我見過太多人一上來就寫歐拉序ST表結(jié)果數(shù)據(jù)規(guī)模才幾千純屬殺雞用牛刀代碼還容易寫錯(cuò)。選型要匹配問題規(guī)模這是工程思維和刷題思維最大的區(qū)別。7. 實(shí)戰(zhàn)中那些文檔不會告訴你的坑7.1 根節(jié)點(diǎn)的父節(jié)點(diǎn)處理這是最經(jīng)典的坑。根節(jié)點(diǎn)沒有父節(jié)點(diǎn)那up[root][0]填什么填0假設(shè)節(jié)點(diǎn)編號從1開始還是填自己填0的話如果查詢時(shí)不小心跳到了0后續(xù)up[0][j]全是0可能掩蓋邏輯錯(cuò)誤。填自己的話跳過頭會原地打轉(zhuǎn)。我的建議是填0并且在查詢邏輯里保證永遠(yuǎn)不會真正用到0這個(gè)越界值——因?yàn)閷R深度和一起跳的過程理論上不會讓節(jié)點(diǎn)跳到根之上。但為了保險(xiǎn)可以在填表時(shí)把up[0][j]都設(shè)成0讓越界訪問有個(gè)確定的兜底。7.2 深度對齊時(shí)的循環(huán)方向階段一對齊深度時(shí)for j in range(LOG)從小到大還是從大到小其實(shí)都可以因?yàn)槲覀兪前炊M(jìn)制位判斷的每一位獨(dú)立。但階段二一起跳的時(shí)候必須從大到小。這兩個(gè)循環(huán)方向不一樣很多人寫著寫著就混了。記住口訣對齊深度看位一起跳看大小。7.3 多組測試數(shù)據(jù)的初始化如果是在競賽或批量處理場景多組測試數(shù)據(jù)之間一定要徹底重置所有數(shù)組。我見過因?yàn)閡p表沒清干凈上一組數(shù)據(jù)殘留導(dǎo)致答案錯(cuò)誤的案例。Python里重新分配數(shù)組最省心C里記得memset或者重新構(gòu)造。7.4 節(jié)點(diǎn)編號從0還是從1開始這個(gè)看似小事實(shí)則影響巨大。從1開始的話0可以當(dāng)哨兵從0開始的話就沒有天然的哨兵值了。我個(gè)人的習(xí)慣是統(tǒng)一從1開始編號把0留作哨兵能省掉很多邊界判斷。如果輸入是從0開始的讀入時(shí)統(tǒng)一加1。7.5 遞歸改迭代的通用套路前面反復(fù)提到遞歸爆棧。改迭代的通用做法是手動(dòng)維護(hù)一個(gè)棧棧里存(節(jié)點(diǎn), 父節(jié)點(diǎn), 狀態(tài))狀態(tài)標(biāo)記是第一次訪問還是回溯?；蛘吒唵蜗扔肂FS求出遍歷順序和父節(jié)點(diǎn)再按逆序處理回溯邏輯。對于倍增法其實(shí)只需要父節(jié)點(diǎn)和深度BFS一遍就夠了根本不需要DFS。這個(gè)優(yōu)化能同時(shí)解決爆棧和效率問題。8. 從LCA延伸出去幾個(gè)高頻衍生問題搞懂了LCA很多樹上查詢問題都能順手解決。這里列幾個(gè)最常見的延伸算是給你指個(gè)方向。樹上兩點(diǎn)距離。有了LCA距離公式就是depth[u] depth[v] - 2 * depth[lca(u,v)]。這個(gè)公式極其常用路徑長度、樹上最遠(yuǎn)點(diǎn)對之類的問題都靠它。樹上路徑第k個(gè)節(jié)點(diǎn)。從u到v的路徑上第k個(gè)點(diǎn)先判斷k是否超過u到LCA的距離分兩種情況用倍增跳。這是倍增法跳表能力的直接應(yīng)用。判斷一個(gè)點(diǎn)是否在兩點(diǎn)路徑上。點(diǎn)w在u-v路徑上當(dāng)且僅當(dāng)lca(u,w)w且lca(w,v)ww是u的祖先且是v的祖先方向或者更準(zhǔn)確地用距離公式驗(yàn)證。這類判斷在路徑覆蓋、樹上差分里很常見。樹上差分。給u到v的路徑上所有點(diǎn)加一個(gè)值可以用差分diff[u] 1, diff[v] 1, diff[lca] - 1, diff[parent(lca)] - 1最后子樹求和。這個(gè)技巧配合LCA能解決一大批路徑統(tǒng)計(jì)問題。這些延伸的共同點(diǎn)是LCA是它們的地基。地基打牢了上面的樓怎么蓋都行。所以別急著刷各種花哨的樹上問題先把LCA這幾種解法吃透后面會輕松很多。我個(gè)人在實(shí)際項(xiàng)目里的體會是真正高頻用到的其實(shí)就是倍增法這一種因?yàn)樗ㄓ?、在線、好維護(hù)。Tarjan和歐拉序更像是特定場景的優(yōu)化手段知道原理、需要時(shí)能撿起來就行不必強(qiáng)求每種都背得滾瓜爛熟。把一種方案寫到閉著眼睛都不出錯(cuò)比每種都半懂不懂要值錢得多。