樹上任意兩點只有一條簡單路徑,但該路徑未必在遍歷次序中形成連續區間。重輕剖分把樹排列成每條路徑都只需對數個區間的並集,於是可用一般區間查詢結構逐段回答。
剖分本身不計算總和,也不維護線段樹;它負責證明一條樹路徑有小而正確的分割。本節會證明分段數界限,建立位置編號,再處理數值放在頂點或放在邊上的邊界分別。實作回傳適用於總和等可交換聚合的區間;輸出次序不是原路徑的行走次序。
按子樹大小選重子節點
定義 13.1.1
(有根子樹大小、重邊與鏈首)
把無向樹根定在 。設 是以 為根的子樹頂點數,包括 。每個非葉頂點,選一個子樹最大的子節點作重子節點;本節平手時選頂點識別碼較小者。
連到該子節點的邊是重邊,連到其他子節點的邊是輕邊。沿重邊向下延伸的極大連續路段形成鏈。每個頂點恰屬一條鏈,第一個頂點稱為鏈首。根是鏈首,其他鏈首則是其父節點的輕子節點。
常見錯誤
(「重」指子樹大小)
「重」指所選子樹大小,不是輸入邊權、頂點深度或直接子節點數。建立剖分不需要任何數值權重。
定理 13.1.2
(輕邊數目的上界)
若 是 的輕子頂點,則 。因此每條由根出發的路徑至多含 條輕邊,兩個頂點之間的每條路徑至多經過 條重鏈。
證明
(沿輕邊使子樹大小減半)
設 是 的輕子節點, 是所選重子節點。因為 ,
子樹大小維持正數,所以根至任一頂點的路徑最多含 條輕邊。沿重鏈可以跨過很多頂點,但每跨一條輕邊,大小尺度便按幾何比例改變。
任意兩點路徑在最低共同祖先分成兩段根路徑的一部分,因此最多跨 條輕邊,並接觸至多 段重鏈。
證明透視
唯一需要最大子頂點的不等式
選取最大的子頂點只用在一處,即不等式 。其餘都是計數:子樹大小是正整數,每經過一條輕邊就減少一半以上,而一條路徑由兩段根路徑組成。重邊從不進入計數,所以長鏈無傷大雅。任意選一個偏好的子頂點就會破壞這個不等式:若 的頂點 有大小為 和 的兩個子頂點,而偏好的是大小為 的那個,則輕子頂點的大小 ,減半論證便失效。
這個界限來自選最大子節點。隨意偏好某個子節點,並不保證其餘子樹不足父子樹的一半。常數是上界,不是預測每條路徑都恰有這麼多段。
優先走重子節點,建立區間
按前序遍歷分配位置:先訪問頂點,再訪問其重子節點的子樹,最後訪問輕子節點的子樹。儲存 pos[v]、head[v]、parent[v]、depth[v],以及反向陣列 vertices[position]。
定理 13.1.3
(鏈與子樹的連續性)
按前序遍歷分配位置:先訪問頂點,再訪問其重子頂點的子樹,最後訪問各輕子頂點的子樹。則重鏈上相鄰的頂點得到連續遞增的位置,而 的子樹恰好佔用位置 。
證明
(先走完子樹再離開)
這給出兩項區間性質。第一,重鏈相鄰頂點得到連續遞增位置:每次都在父節點後立即訪問重子節點,直至鏈尾。第二,整棵子樹連續,因為遍歷會先完成該子樹,才回到外部頂點。其半開區間是
兩者相關但不同。一般前序已令子樹連續;優先重子節點另外令重鏈連續。任意兩點的路徑仍不一定是一個區間。
上述子樹區間包含頂點 。若把邊值儲存在其較深端點,而查詢只計完全位於該子樹內的邊,就略去 的位置,使用 ,不把連到父節點的邊計入。
例題 13.1.4
(七頂點有根樹中的三條鏈)
根為 0,邊為 。依實作的輕子節點堆疊次序,得到以下排列:
| 頂點 | 子樹大小 | 重子節點 | 鏈首 | 位置 |
|---|---|---|---|---|
| 無 | ||||
| 無 | ||||
| 無 |
反向位置次序是 。鏈為 、、。頂點 1 的子樹區間是 ,含 ;頂點 2 的子樹為 ,含 。
根的兩個子節點大小都是三,平手選 1;頂點 1 的兩個葉子平手,選 3。其他合法平手或輕子樹次序可以改變位置,但不改變保證。
移除較深鏈首,而不是較深端點
對目前端點 ,若鏈首不同,選鏈首較深的端點。假設是 ,輸出 [pos[head[u]], pos[u]+1),再把 改為 parent[head[u]]。重複至鏈首相同,剩餘路徑便是兩位置之間、包含兩端的一個區間。
定理 13.1.5
(移除鏈首操作的正確性)
設 是鏈首不同的當前端點,並設 的鏈首不比另一個鏈首淺。則從 到 的鏈段位於路徑上,且嚴格在 LCA 之下,而剩下的路徑是從 到 。當鏈首相同時,兩端點在同一條鏈上之間的頂點構成最後一段,其較淺端點就是 LCA。因此輸出的區間分割了路徑上的頂點,每個頂點恰好計算一次。
證明
(每段被移除的鏈段都在 LCA 之下)
鏈首不同時,所選較深鏈首必嚴格位於目前最低共同祖先之下。若祖先在所選鏈段內,另一端點就必須位於另一個輕子節點邊界之下,其鏈首會更深,與選擇矛盾。
因此,從所選端點向上至鏈首的整段都在路徑上,並在共同祖先之下。移除後從鏈首父節點繼續,得到較小的剩餘路徑,已移除頂點不再重算。該父邊是輕邊,因為所選鏈首不是根鏈首。
兩端同鏈後,剩餘頂點全在該鏈兩端之間,較淺端點就是共同祖先。包含最後區間,便完成路徑所有頂點的互不重疊分割,並把共同祖先恰好計一次。輕邊界限控制輸出段數。
證明透視
為甚麼由鏈首深度而非端點深度決定
唯一不尋常的事實是較深的鏈首嚴格在 LCA 之下。若 LCA 在被選的鏈上,另一個端點要麼經由輕邊掛在它下面,要麼就在同一條鏈上;前一種情形使該端點的鏈首嚴格比被選者深,後一種情形與鏈首不同相矛盾。鏈首深度相同時,任選一個端點都可以,因為兩條鏈都不可能含有 LCA。每次移除都使路徑變短,所以迴圈會結束;而 LCA 只出現在最後一段,這就是邊模式只調整最後一段的原因。
反例模式
端點同深度,不代表可以隨意選鏈
例題頂點 3、4 的深度都是二,但鏈首分別是深度零的 0、深度二的 4。若把 3 至鏈首 0 的整鏈移除,就會錯把不在路徑 的頂點 0 納入。
應比較鏈首深度,先移除 4 的單點鏈,再完成 1 至 3 的同鏈區間。只看端點深度,不能證明整鏈在共同祖先之下。
追蹤路徑分段及靜態總和
例題 13.1.6
(從 4 到 6 的路徑及其靜態總和)
對路徑 ,分段程序輸出:
| 目前端點 | 選中頂點 | 半開位置 | 下一端點 |
|---|---|---|---|
| 完成 |
真正路徑次序為 。區間分割了其頂點,卻以另一個次序輸出。若頂點 的值為 ,攤平陣列是 ,路徑總和是 。
對靜態總和陣列 base,建立 prefix[0] = 0、prefix[i+1] = prefix[i] + base[i],每段貢獻 prefix[right] - prefix[left]。所以毋須在本節實作線段樹,剖分已能完成靜態路徑總和查詢。
邊值只在最後區間排除共同祖先位置
定義 13.1.7
(存於較深端點的邊值)
把邊值存於有根樹中較深端點;根沒有入邊,可存零。路徑的邊值便對應其頂點中除共同祖先以外的部分,因為其餘每個路徑頂點,都代表一條在路徑上的父邊。
每個非最後區間仍必須包含鏈首:鏈首至父節點的邊,正是正在跨越的輕邊。只有最後同鏈區間,把較低位置端點加一,以排除共同祖先。若 ,邊路徑為空,不輸出最後區間;頂點路徑則包含該頂點。
反例模式
刪去每個鏈首會遺漏真正的輕邊
根為 0,葉子為 1、2,選子節點 1 為重子節點。頂點 2 是單點輕鏈,從 0 到 2 的邊路徑包含儲存在頂點 2 的邊。
若邊模式把每段鏈首都排除,就會刪去這整個單點貢獻,即使邊權非零也回傳零。只在最後一段排除共同祖先;其他鏈首代表必需的路徑邊。
例題 13.1.8
(從 4 到 3 的點路徑與邊路徑)
七頂點例子中,路徑 的頂點區間是 、。頂點值為 時,總和 。若非根子節點的邊值儲存為 ,區間改為 、,總和 。被排除位置屬於共同祖先頂點 1。
迭代建立剖分及拆分區間
輸入以前提要求使用整數頂點識別碼及端點配對。建立時檢查正大小、合法根及端點、邊數、自環、環與連通性。重子節點平手選較小識別碼,輕子樹次序依輸入邊的堆疊次序。查詢之間不可修改回傳的排列數據。
def heavy_light(n, edges, root=0):
edges = tuple(edges)
if n < 1 or not 0 <= root < n or len(edges) != n - 1:
raise ValueError("a valid root and n-1 tree edges are required")
adjacency = [[] for _ in range(n)]
for u, v in edges:
if not 0 <= u < n or not 0 <= v < n or u == v:
raise ValueError("tree endpoints must be valid and distinct")
adjacency[u].append(v)
adjacency[v].append(u)
parent = [-1] * n
depth = [0] * n
parent[root] = root
stack = [root]
order = []
while stack:
u = stack.pop()
order.append(u)
for v in adjacency[u]:
if v == parent[u]:
continue
if parent[v] != -1:
raise ValueError("edges must form a tree")
parent[v] = u
depth[v] = depth[u] + 1
stack.append(v)
if len(order) != n:
raise ValueError("the tree must be connected")
size = [1] * n
heavy = [-1] * n
for u in reversed(order):
for v in adjacency[u]:
if parent[v] != u:
continue
size[u] += size[v]
h = heavy[u]
if h == -1 or size[v] > size[h] or (size[v] == size[h] and v < h):
heavy[u] = v
head = [-1] * n
position = [-1] * n
vertices = []
stack = [(root, root)]
while stack:
u, chain_head = stack.pop()
head[u] = chain_head
position[u] = len(vertices)
vertices.append(u)
for v in adjacency[u]:
if parent[v] == u and v != heavy[u]:
stack.append((v, v))
if heavy[u] != -1:
stack.append((heavy[u], chain_head))
return {"parent": parent, "depth": depth, "size": size,
"heavy": heavy, "head": head, "pos": position, "vertices": vertices}
def path_intervals(layout, u, v, edge_mode=False):
parent, depth = layout["parent"], layout["depth"]
head, position = layout["head"], layout["pos"]
n = len(parent)
if not 0 <= u < n or not 0 <= v < n:
raise ValueError("path endpoints must be valid vertices")
result = []
while head[u] != head[v]:
if depth[head[u]] < depth[head[v]]:
u, v = v, u
result.append((position[head[u]], position[u] + 1))
u = parent[head[u]]
if position[u] > position[v]:
u, v = v, u
left = position[u] + int(edge_mode)
right = position[v] + 1
if left < right:
result.append((left, right))
return result
使用 layout = heavy_light(7, [(0,1),(0,2),(1,3),(1,4),(2,5),(5,6)]),path_intervals(layout, 4, 6) 會回傳 [(3,4),(4,7),(0,2)]。建立 base = [vertex+1 for vertex in layout["vertices"]] 及其前綴和,再把各區間相加,便得 24。傳入 edge_mode=True 會使用上述最後邊界規則,但不會重新解讀輸入值陣列的儲存方法。
說清楚後端成本及次序假設
命題 13.1.9
(重輕剖分路徑查詢的開銷)
建立剖分需時 、佔用 空間,而一次路徑查詢至多分成 個區間。若一次區間查詢需時 ,則路徑聚合需時 ,每段另加常數工作。
證明
(計算區間數與後端調用次數)
建立只把每條樹邊掃描常數次,所以時間與空間都為 。當 ,查詢拆分回傳 個區間,單頂點樹則有常數輸出。若每個區間查詢需 時間,路徑聚合需 ,另有每段常數合併成本。
靜態前綴和給出 ,因此路徑總和為 。支援單點更新、區間查詢 的線段樹,給出路徑查詢 、單點更新 。子樹查詢只用一個連續區間。值改變後必須重建或替換前綴和,剖分本身不維護它;樹的拓撲改變也要另用方法或重建。
常見錯誤
(結合律並不允許改變次序)
輸出區間適合總和、最小值、最大值等不受次序影響的可交換組合,並須配合適當區間後端,必要時指定空路徑單位元。只有結合律,不足以支持忽略次序。例如把 的頂點標籤按輸出區間的正向次序串接,得到 425601,真正路徑卻是 410256。有序乘積需要有方向的區間、兩個端點方向各自的累積量,以及適當正向、反向區間聚合。以上程式沒有實作此擴展。
練習與詳解
快速檢查
(1. 證明輕邊收縮,而不只憑名稱判斷)
c 是 p 的輕子節點,h 是最大的重子節點,為甚麼 c 的子樹不足 p 的一半?甚麼限制根路徑上的輕邊數?
解答 · 解答 1
由 ,得 ,所以 。正整數子樹大小從 開始,不能反覆減半超過對數次。因此,根路徑最多有 條輕邊。
快速檢查
(2. 從區間集合重建例題路徑)
對 4 至 6 的路徑,列出三個輸出區間及其頂點。它們是否按行走次序輸出?頂點 v 的值為 v 加一時,總和是多少?
解答 · 解答 2
區間是含 4 的 、含 的 、含 的 。它們分割路徑,卻不按真正次序 。各段和為 5、16、3,總計 24。
快速檢查
(3. 端點同深時比較鏈首)
為甚麼 3 至 4 的路徑必須先移除頂點 4 的鏈,而不能因端點同深就任選?錯誤選擇會納入哪個不應有的頂點?
解答 · 解答 3
鏈首深度為零與二。4 的較深鏈首位於共同祖先 1 之下,可以安全移除。若先取 3 至鏈首 0 的整鏈,會包含不在 上的頂點 0。應比較鏈首深度,而不是端點深度。
快速檢查
(4. 邊模式排除正確的頂點)
對例題樹中由 4 至 3 的路徑,頂點與邊區間有甚麼變化?為甚麼非最後輕鏈的鏈首必須保留?從同一頂點到自己的邊查詢包含甚麼?
解答 · 解答 4
頂點區間為 、,邊區間為 、,只在最後一段排除共同祖先 1。非最後鏈首儲存其入輕邊,那條邊在路徑上。同端點邊查詢沒有邊,所以回傳空區間列表。
快速檢查
(5. 把一個子樹區間接到所選後端)
求頂點 1 的子樹區間。若區間後端需對數時間,比較子樹查詢與一般路徑查詢。單點改值後,靜態前綴和可否不作維護直接使用?
解答 · 解答 5
子樹為 ,包含 。一次後端查詢需 ,一般路徑有 段,所以需 。改值令靜態前綴和過時,必須重建或改用適當可更新後端。
快速檢查
(6. 不要用結合律代替路徑次序)
為甚麼按輸出區間的正向次序直接串接,會令 4 至 6 路徑錯誤?列出兩個字串,以及有序聚合需要的額外資訊。
解答 · 解答 6
輸出次序得到 425601,真路徑是 410256。串接可結合,卻受次序影響。正確擴展必須保留區間方向與兩個端點方向的相對次序,配合有序累積量及正向、反向區間資訊。本節所述可交換聚合,才可直接使用這個無序區間列表。