柚子快報(bào)邀請(qǐng)碼778899分享：[藍(lán)橋杯學(xué)習(xí)] 樹鏈剖分

http://yzkb.51969.com/

定義

將樹分割成若干條鏈，以維護(hù)樹上的信息，若無(wú)特殊需求，一般是重鏈剖分。

重鏈剖分

如何重鏈剖分

兩個(gè)dfs

第一個(gè)dfs是預(yù)處理各個(gè)結(jié)點(diǎn)的基本信息，第二個(gè)dfs是利用信息進(jìn)行剖分（dfs序）

操作步驟

第一次dfs

更新當(dāng)前結(jié)點(diǎn)信息（子樹個(gè)數(shù)、父結(jié)點(diǎn)信息、深度）對(duì)子結(jié)點(diǎn)進(jìn)行dfs子結(jié)點(diǎn)dfs之后，把子結(jié)點(diǎn)的子樹個(gè)數(shù)加到父結(jié)點(diǎn)，更新重兒子。

第二次dfs

因?yàn)閐fs序連續(xù)的值是一條鏈，所以，我們需要讓樹在進(jìn)行dfs時(shí)，優(yōu)先對(duì)重兒子進(jìn)行dfs，之后再對(duì)其它輕兒子進(jìn)行dfs

重鏈剖分的應(yīng)用

將剖分的重鏈放在線段數(shù)組或者樹狀數(shù)組上，然后在這個(gè)數(shù)據(jù)結(jié)構(gòu)上進(jìn)行維護(hù)。

對(duì)某條鏈上的節(jié)點(diǎn)進(jìn)行更新

用數(shù)據(jù)結(jié)構(gòu)對(duì)節(jié)點(diǎn)信息進(jìn)行維護(hù)，進(jìn)行區(qū)間查詢，區(qū)間更新。

對(duì)某節(jié)點(diǎn)子樹進(jìn)行更新/查詢

由dfs序可知，某節(jié)點(diǎn)的入序和出序之間的連續(xù)數(shù)就是該節(jié)點(diǎn)的子樹。

查詢兩節(jié)點(diǎn)的最近公共祖先LCA

操作步驟：

當(dāng)兩節(jié)點(diǎn)不在同一條鏈上時(shí)，選擇深度更淺的結(jié)點(diǎn)，跳到父鏈（鏈?zhǔn)椎母附Y(jié)點(diǎn)）當(dāng)兩節(jié)點(diǎn)在同一條鏈上時(shí)，深度更淺的點(diǎn)就是最近公共祖先LCA

查詢、修改兩節(jié)點(diǎn)之間路徑的信息

主體還是尋找LCA，就是如果跳到父鏈（或是其它點(diǎn)），把x到它首結(jié)點(diǎn)（其它點(diǎn)）之間結(jié)點(diǎn)信息進(jìn)行更新。

柚子快報(bào)邀請(qǐng)碼778899分享：[藍(lán)橋杯學(xué)習(xí)] 樹鏈剖分

http://yzkb.51969.com/

參考文章