Cấu trúc dữ liệu và Giải thuật Bài 119: Phân rã cây nặng - nhẹ (Heavy-Light Decomposition - HLD) - Chuyển đổi truy vấn đường đi trên cây thành thao tác trên mảng.

Khi làm việc với các bài toán truy vấn trên cây (Tree Queries) — chẳng hạn như tính tổng, tìm giá trị lớn nhất, hoặc cập nhật giá trị của tất cả các nút dọc theo đường đi ngắn nhất giữa hai đỉnh bất kỳ $u$ và $v$ — việc duyệt tuần tự theo đường đi mất $O(N)$ thời gian cho mỗi truy vấn là nút thắt cổ chai lớn trong các hệ thống đòi hỏi độ trễ thấp.

Nếu dữ liệu nằm trên một mảng tuyến tính, ta có thể dễ dàng dùng Segment Tree hoặc Fenwick Tree để giải quyết trong $O(\log N)$ . Tuy nhiên, cấu trúc cây lại phân nhánh phức tạp. Phân rã cây nặng - nhẹ (Heavy-Light Decomposition - HLD) là kỹ thuật phân rã toàn bộ cây thành một tập hợp các chuỗi đường đi rời rạc (gọi là các Heavy Chains), sau đó "trải phẳng" (flatten) cây thành một mảng 1 chiều. Khi đó, bất kỳ đường đi nào giữa hai nút trên cây cũng chỉ bị cắt thành tối đa $O(\log N)$ đoạn con liên tiếp trên mảng, cho phép ta dùng Segment Tree để giải quyết mọi truy vấn đường đi chỉ trong $O(\log^2 N)$ .

1. Trực giác toán học: Cạnh nặng, Cạnh nhẹ và Định lý $O(\log N)$

Xét một cây có gốc gồm $N$ đỉnh. Với mỗi đỉnh $u$ , ta gọi $\text{size}[u]$ là số lượng nút trong cây con có gốc tại $u$ .

Ta phân loại các cạnh nối từ cha $u$ xuống con $v$ :

Cạnh nặng (Heavy Edge): Nối từ $u$ tới nút con $v$ có $\text{size}[v]$ lớn nhất trong tất cả các con của $u$ . Do mỗi nút chỉ có tối đa một nút con có kích thước lớn nhất, nên mỗi nút có tối đa đúng một cạnh nặng đi xuống.
Cạnh nhẹ (Light Edge): Tất cả các cạnh còn lại nối từ $u$ tới các con khác.
Chuỗi nặng (Heavy Chain): Một đường đi liên tục gồm các cạnh nặng nối tiếp nhau. Mỗi đỉnh trên cây thuộc về đúng một chuỗi nặng (chuỗi có thể chỉ gồm 1 đỉnh nếu không có cạnh nặng nào đi tiếp).

Tính chất đột phá về số lượng chuỗi

Nếu ta đi từ một nút con $v$ lên nút cha $u$ qua một cạnh nhẹ, kích thước cây con sẽ tăng ít nhất gấp đôi:

$\text{size}[u] > 2 \cdot \text{size}[v]$

Bởi vì nếu $\text{size}[v] > \frac{\text{size}[u]}{2}$ , thì $v$ bắt buộc phải là con nặng nhất của $u$ .

Do kích thước cây con không thể vượt quá $N$ , nên trên bất kỳ đường đi nào từ một đỉnh bất kỳ lên gốc của cây, ta chỉ có thể đi qua tối đa $\lfloor \log_2 N \rfloor$ cạnh nhẹ. Điều này đồng nghĩa với việc đường đi từ một đỉnh lên gốc chỉ bị ngắt quãng bởi tối đa $O(\log N)$ chuỗi nặng!

2. Quy trình hai lượt DFS để trải phẳng cây

Để ánh xạ cây sang mảng tuyến tính cho Segment Tree quản lý, ta thực hiện đúng 2 lượt duyệt DFS:

Lượt DFS 1: Thu thập cấu trúc và phát hiện Cạnh nặng

Tính độ sâu $\text{depth}[u]$ và nút cha $\text{parent}[u]$ .
Đếm số lượng nút con $\text{size}[u]$ .
Tìm nút con $v$ có $\text{size}[v]$ lớn nhất để đánh dấu là $\text{heavyChild}[u]$ .

Lượt DFS 2: Đánh số thứ tự mảng phẳng và Gán đỉnh đầu chuỗi

Duy trì biến đếm toàn cục timer. Gán vị trí của $u$ trên mảng phẳng là $\text{pos}[u] = \text{timer}++$ .
Lưu trữ đỉnh cao nhất của chuỗi nặng hiện tại vào $\text{head}[u]$ .
Nguyên tắc then chốt: Khi gọi đệ quy các con của $u$ , bắt buộc phải thăm $\text{heavyChild}[u]$ đầu tiên và gán $\text{head}[\text{heavyChild}[u]] = \text{head}[u]$ . Nhờ vậy, tất cả các đỉnh nằm trên cùng một chuỗi nặng sẽ có các giá trị $\text{pos}$ liên tiếp nhau trên mảng.
Sau đó mới duyệt qua các nút con nhẹ, với $\text{head}[v] = v$ (khởi đầu một chuỗi nặng mới).

3. Thuật toán xử lý truy vấn đường đi giữa $u$ và $v$

Để tính toán trên đường đi giữa $u$ và $v$ :

So sánh đỉnh đầu chuỗi $\text{head}[u]$ và $\text{head}[v]$ .
Nếu $\text{head}[u] \neq \text{head}[v]$ , đỉnh nào có $\text{head}$ nằm ở độ sâu lớn hơn (xa gốc hơn) sẽ thực hiện truy vấn trên Segment Tree cho đoạn từ $\text{pos}[\text{head}]$ đến $\text{pos}$ của đỉnh đó. Sau đó, nhảy đỉnh đó lên cha của $\text{head}$ (u = parent[head[u]]).
Lặp lại cho đến khi cả $u$ và $v$ cùng thuộc một chuỗi nặng ( $\text{head}[u] == \text{head}[v]$ ).
Lúc này, $u$ và $v$ nằm liên tục trên cùng một đoạn mảng. Ta chỉ cần gọi Segment Tree truy vấn một lần duy nhất cho đoạn $[\min(\text{pos}[u], \text{pos}[v]), \max(\text{pos}[u], \text{pos}[v])]$ .

4. Hiện thực hóa Heavy-Light Decomposition bằng Golang

Đoạn mã dưới đây cài đặt đầy đủ cấu trúc HLD tích hợp Segment Tree để truy vấn tổng và cập nhật giá trị nút trên đường đi giữa hai đỉnh bất kỳ:

package main

import (
	"fmt"
)

// Segment Tree hỗ trợ Point Update và Range Sum Query
type SegmentTree struct {
	tree []int
	n    int
}

func NewSegmentTree(n int) *SegmentTree {
	return &SegmentTree{
		tree: make([]int, 4*n),
		n:    n,
	}
}

func (st *SegmentTree) Update(node, start, end, idx, val int) {
	if start == end {
		st.tree[node] = val
		return
	}
	mid := (start + end) / 2
	if idx <= mid {
		st.Update(2*node, start, mid, idx, val)
	} else {
		st.Update(2*node+1, mid+1, end, idx, val)
	}
	st.tree[node] = st.tree[2*node] + st.tree[2*node+1]
}

func (st *SegmentTree) Query(node, start, end, l, r int) int {
	if r < start || end < l {
		return 0
	}
	if l <= start && end <= r {
		return st.tree[node]
	}
	mid := (start + end) / 2
	return st.Query(2*node, start, mid, l, r) + st.Query(2*node+1, mid+1, end, l, r)
}

// Cấu trúc quản lý HLD
type HLD struct {
	n          int
	adj        [][]int
	parent     []int
	depth      []int
	heavy      []int
	head       []int
	pos        []int
	curPos     int
	segTree    *SegmentTree
	nodeValues []int
}

func NewHLD(n int, values []int) *HLD {
	hld := &HLD{
		n:          n,
		adj:        make([][]int, n),
		parent:     make([]int, n),
		depth:      make([]int, n),
		heavy:      make([]int, n),
		head:       make([]int, n),
		pos:        make([]int, n),
		curPos:     0,
		segTree:    NewSegmentTree(n),
		nodeValues: values,
	}
	for i := 0; i < n; i++ {
		hld.heavy[i] = -1
	}
	return hld
}

func (h *HLD) AddEdge(u, v int) {
	h.adj[u] = append(h.adj[u], v)
	h.adj[v] = append(h.adj[v], u)
}

// DFS 1: Tính size, depth, parent và tìm heavy child
func (h *HLD) dfs1(u, p, d int) int {
	size := 1
	maxChildSize := 0
	h.parent[u] = p
	h.depth[u] = d

	for _, v := range h.adj[u] {
		if v != p {
			childSize := h.dfs1(v, u, d+1)
			size += childSize
			if childSize > maxChildSize {
				maxChildSize = childSize
				h.heavy[u] = v
			}
		}
	}
	return size
}

// DFS 2: Đánh số pos và gán head của chuỗi nặng
func (h *HLD) dfs2(u, hHead int) {
	h.head[u] = hHead
	h.pos[u] = h.curPos
	h.curPos++

	// Khởi tạo giá trị vào Segment Tree tại vị trí pos[u]
	h.segTree.Update(1, 0, h.n-1, h.pos[u], h.nodeValues[u])

	// Ưu tiên duyệt nút con nặng nhất trước
	if h.heavy[u] != -1 {
		h.dfs2(h.heavy[u], hHead)
	}

	// Duyệt các nút con nhẹ sau
	for _, v := range h.adj[u] {
		if v != h.parent[u] && v != h.heavy[u] {
			h.dfs2(v, v) // Mỗi nút con nhẹ bắt đầu một chuỗi nặng mới
		}
	}
}

func (h *HLD) Init(root int) {
	h.dfs1(root, -1, 0)
	h.dfs2(root, root)
}

// Cập nhật giá trị một nút
func (h *HLD) UpdateNode(u, val int) {
	h.nodeValues[u] = val
	h.segTree.Update(1, 0, h.n-1, h.pos[u], val)
}

// Truy vấn tổng giá trị trên đường đi giữa u và v: O(log^2 N)
func (h *HLD) QueryPath(u, v int) int {
	sum := 0
	for h.head[u] != h.head[v] {
		// Đỉnh nào có head ở tầng sâu hơn thì nhảy trước
		if h.depth[h.head[u]] < h.depth[h.head[v]] {
			u, v = v, u
		}
		// Cộng dồn đoạn từ head[u] đến u
		sum += h.segTree.Query(1, 0, h.n-1, h.pos[h.head[u]], h.pos[u])
		u = h.parent[h.head[u]]
	}

	// Khi u và v cùng một chuỗi nặng
	if h.depth[u] > h.depth[v] {
		u, v = v, u
	}
	sum += h.segTree.Query(1, 0, h.n-1, h.pos[u], h.pos[v])
	return sum
}

func main() {
	// Cây gồm 6 đỉnh (0 đến 5)
	// Giá trị ban đầu của các đỉnh: [10, 20, 30, 40, 50, 60]
	nodeValues := []int{10, 20, 30, 40, 50, 60}
	n := len(nodeValues)
	hld := NewHLD(n, nodeValues)

	// Các cạnh: (0-1), (0-2), (1-3), (1-4), (2-5)
	hld.AddEdge(0, 1)
	hld.AddEdge(0, 2)
	hld.AddEdge(1, 3)
	hld.AddEdge(1, 4)
	hld.AddEdge(2, 5)

	hld.Init(0)

	// Truy vấn tổng đường đi từ 3 đến 5 (3 -> 1 -> 0 -> 2 -> 5)
	// Giá trị: 40 + 20 + 10 + 30 + 60 = 160
	fmt.Printf("Tổng đường đi từ 3 đến 5: %d\n", hld.QueryPath(3, 5))

	// Cập nhật đỉnh 0 tăng từ 10 thành 100
	fmt.Println("Cập nhật đỉnh 0 thành 100...")
	hld.UpdateNode(0, 100)

	// Truy vấn lại đường đi từ 3 đến 5 sau cập nhật: 40 + 20 + 100 + 30 + 60 = 250
	fmt.Printf("Tổng đường đi từ 3 đến 5 sau cập nhật: %d\n", hld.QueryPath(3, 5))
}

5. Ứng dụng thực tế

Giám sát độ trễ mạng backbone phân cấp: Tính toán tổng độ trễ hoặc tìm nút có nguy cơ tắc nghẽn lớn nhất (Path Max Query) giữa hai trạm mạng bất kỳ khi cấu trúc mạng viễn thông có dạng cây phân cấp.
Hệ thống phân quyền & Phân bổ ngân sách tổ chức: Kiểm tra hoặc cập nhật hạn mức chi tiêu dọc theo chuỗi báo cáo quản lý từ nhân viên lên đến tổng giám đốc trong tích tắc.
Tìm Tổ tiên chung gần nhất (LCA): HLD tự động cung cấp thuật toán tìm LCA trong thời gian $O(\log N)$ với hằng số thực thi nhỏ hơn và không cần tạo bảng thưa Sparse Table cồng kềnh.

cấu trúc dữ liệu

1. Trực giác toán học: Cạnh nặng, Cạnh nhẹ và Định lý O(log⁡N)O(\log N)O(logN)