Cấu trúc dữ liệu và Giải thuật Bài 74: Phân rã Đậm-Nhạt (Heavy-Light Decomposition - HLD) - Trải phẳng Cây để truy vấn khoảng siêu tốc.

Trong Bài 58 và 59, chúng ta đã sử dụng Cây Phân Đoạn (Segment Tree) để thực hiện các truy vấn siêu tốc $O(\log N)$ trên một Mảng tuyến tính (1D Array). Tuy nhiên, dữ liệu trong thế giới thực hiếm khi nằm thẳng hàng. Khi hệ thống quản lý một sơ đồ mạng lưới máy chủ, cây phân cấp tổ chức nhân sự, hay cây DOM của một trang web, dữ liệu được tổ chức dưới dạng Đồ thị dạng Cây (Tree).

Bài toán đặt ra: Làm sao để tính tổng hoặc tìm giá trị lớn nhất trên một đường đi từ đỉnh $u$ đến đỉnh $v$ bất kỳ trên Cây?

Nếu dùng thuật toán duyệt DFS/BFS thông thường, mỗi truy vấn sẽ tốn $O(N)$ thời gian. Khi hệ thống phải nhận hàng triệu truy vấn, nó sẽ sụp đổ. Giải pháp tối thượng chính là Phân rã Đậm-Nhạt (Heavy-Light Decomposition - HLD) — một kỹ thuật bẻ gãy không gian Cây, "trải phẳng" nó thành các đoạn mảng 1 chiều để có thể áp dụng trực tiếp Segment Tree, ép thời gian truy vấn xuống mức $O(\log^2 N)$ .

1. Giải phẫu HLD: Cạnh Nặng và Cạnh Nhẹ

Ý tưởng cốt lõi của HLD là phân rã một cái cây khổng lồ thành một tập hợp các đường đi thẳng (Paths/Chains) rời rạc. Để thực hiện điều này, thuật toán đánh giá trọng lượng dựa trên Kích thước cây con (Subtree size).

Đối với mỗi một Đỉnh (Node) $u$ trên cây:

Tính kích thước: Đếm tổng số lượng các đỉnh nằm trong toàn bộ nhánh cây con bên dưới nó.
Cạnh Nặng (Heavy Edge): Trong số tất cả các đỉnh con của $u$ , đỉnh con nào sở hữu cây con lớn nhất sẽ được chọn làm "con cưng". Cạnh nối từ $u$ đến đỉnh con đó gọi là Cạnh Nặng. (Nếu có nhiều đỉnh con cùng kích thước max, chọn bất kỳ).
Cạnh Nhẹ (Light Edge): Tất cả các cạnh nối từ $u$ đến các đỉnh con còn lại đều là Cạnh Nhẹ.

Khi liên kết các Cạnh Nặng liền kề nhau, chúng ta tạo ra các Chuỗi Nặng (Heavy Chains). Nhờ vậy, toàn bộ cái Cây phân nhánh phức tạp giờ đây được chia thành các đường thẳng tuyến tính.

2. Bí mật Toán học: Tại sao HLD lại có tốc độ logarit?

Sức mạnh của HLD nằm ở một định lý toán học cực kỳ chặt chẽ về Cạnh Nhẹ:

Định lý: Khi đi từ Nút gốc (Root) xuống bất kỳ một Nút lá (Leaf) nào trên cây, bạn sẽ bước qua không quá $\log_2(N)$ Cạnh Nhẹ.

Chứng minh: Bất cứ khi nào bạn đi qua một Cạnh Nhẹ để xuống một đỉnh con, theo định nghĩa, đỉnh con đó không phải là đứa con lớn nhất. Nghĩa là kích thước cây con của nó bắt buộc phải nhỏ hơn hoặc bằng một nửa ( $\le \frac{1}{2}$ ) kích thước cây con của đỉnh cha. Bạn chỉ có thể chia đôi một tập hợp $N$ phần tử tối đa $\log_2(N)$ lần trước khi nó chạm về $1$ .

Hệ quả: Bất kỳ đường đi nào từ đỉnh $u$ đến đỉnh $v$ trên cây cũng sẽ bị cắt ngang bởi tối đa $O(\log N)$ Chuỗi Nặng. Thay vì duyệt từng đỉnh, ta nhảy cóc qua các Chuỗi Nặng và dùng Segment Tree để tính toán trên mỗi chuỗi trong thời gian $O(\log N)$ .

Tổng thời gian truy vấn: $O(\log N) \times O(\log N) = \mathbf{O(\log^2 N)}$ .

3. Triển khai HLD bằng Golang

Thuật toán HLD đòi hỏi 2 lần chạy DFS:

DFS 1: Thu thập dữ liệu meta (độ sâu, đỉnh cha, kích thước cây con, đỉnh con nặng nhất).
DFS 2: Xây dựng các Chuỗi Nặng và đánh số thứ tự mới (trải phẳng cây thành mảng tuyến tính).

package main

import "fmt"

type HLD struct {
	n          int
	adj        [][]int // Danh sách kề của Cây
	parent     []int   // Đỉnh cha
	depth      []int   // Độ sâu của đỉnh
	heavy      []int   // Đỉnh con nặng nhất (-1 nếu là lá)
	head       []int   // Đỉnh đầu tiên của Chuỗi Nặng mà đỉnh hiện tại thuộc về
	pos        []int   // Vị trí của đỉnh trên Mảng 1D (Dùng cho Segment Tree)
	currentPos int     // Biến đếm để gán vị trí trên Mảng 1D
}

func NewHLD(n 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),
	}
	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) // Giả định cây vô hướng
}

// DFS 1: Tính toán kích thước, độ sâu, cha và đỉnh con nặng nhất
func (h *HLD) dfs1(v, p, d int) int {
	h.parent[v] = p
	h.depth[v] = d
	size := 1
	maxSubtree := 0

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

// DFS 2: Hình thành Chuỗi Nặng và trải phẳng cây
func (h *HLD) dfs2(v, p, currentHead int) {
	h.head[v] = currentHead
	h.pos[v] = h.currentPos
	h.currentPos++

	// Ưu tiên đi theo Cạnh Nặng trước để đảm bảo chúng nằm liền kề nhau trên Mảng 1D
	if h.heavy[v] != -1 {
		h.dfs2(h.heavy[v], v, currentHead)
	}

	// Sau đó mới duyệt các Cạnh Nhẹ (Bắt đầu một Chuỗi Nặng hoàn toàn mới)
	for _, to := range h.adj[v] {
		if to != p && to != h.heavy[v] {
			h.dfs2(to, v, to)
		}
	}
}

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

// Giả lập hàm truy vấn đường đi từ u đến v (Kết hợp với Segment Tree)
func (h *HLD) QueryPath(u, v int) {
	// Di chuyển u và v lên trên cho đến khi chúng nằm trên cùng một Chuỗi Nặng
	for h.head[u] != h.head[v] {
		// Luôn chọn đỉnh có nhánh nằm sâu hơn để nhảy lên
		if h.depth[h.head[u]] < h.depth[h.head[v]] {
			u, v = v, u
		}
		// Gọi hàm Segment Tree Query từ h.pos[h.head[u]] đến h.pos[u] tại đây
		fmt.Printf("Truy vấn mảng từ index %d đến %d (Chuỗi của %d)\n", h.pos[h.head[u]], h.pos[u], h.head[u])
		
		// Nhảy lên đỉnh cha của đỉnh đầu chuỗi
		u = h.parent[h.head[u]]
	}
	
	// Khi u và v đã nằm trên cùng một chuỗi, thực hiện truy vấn cuối cùng
	if h.depth[u] > h.depth[v] {
		u, v = v, u
	}
	fmt.Printf("Truy vấn mảng từ index %d đến %d (Trên cùng chuỗi)\n", h.pos[u], h.pos[v])
}

4. Phân tích Hiệu năng (Big-O)

Thời gian Xây dựng (Preprocessing): $O(N)$ . Hai vòng quét DFS chỉ đi qua mỗi đỉnh và mỗi cạnh đúng một lần, thiết lập cấu trúc mảng 1 chiều ngay lập tức.
Thời gian Truy vấn đường đi (Path Query / Update): $O(\log^2 N)$ . Phân rã đường đi mất $O(\log N)$ bước nhảy (qua các chuỗi). Tại mỗi chuỗi, việc truy vấn Cây phân đoạn (Segment Tree) mất thêm $O(\log N)$ .
Không gian (Space Complexity): $O(N)$ cho các mảng phụ trợ lưu trữ thông tin meta của hệ thống cây.

5. Ứng dụng Thực tế trong Hệ thống Enterprise

Heavy-Light Decomposition là vũ khí tối tân cho các hệ thống phần mềm cần xử lý dữ liệu phân cấp động:

Tối ưu hóa Truyền tuyến mạng (Network Routing Topology): Khi tính toán băng thông khả dụng nhỏ nhất hoặc độ trễ lớn nhất dọc theo đường truyền giữa hai node server xa xôi trong kiến trúc liên kết dạng cây.
Hệ thống Quản lý Quyền truy cập phân cấp (Hierarchical RBAC/IAM): Tính toán và cập nhật các chính sách (policies) bảo mật ghi đè từ tập đoàn tổng xuống công ty con, phòng ban, và từng nhân viên, đảm bảo kiểm tra quyền truy cập theo thời gian thực với độ trễ nano-giây.
Mô phỏng Phân tử & Đồ họa Máy tính (Scene Graphs): Trong việc render không gian 3D, sự thay đổi ánh sáng hoặc vị trí của một khớp xương (node) ảnh hưởng đến toàn bộ các chi bên dưới, HLD giúp quản lý và cập nhật chuỗi render siêu tốc.

cấu trúc dữ liệu

1. Giải phẫu HLD: Cạnh Nặng và Cạnh Nhẹ

2. Bí mật Toán học: Tại sao HLD lại có tốc độ logarit?

3. Triển khai HLD bằng Golang

4. Phân tích Hiệu năng (Big-O)

5. Ứng dụng Thực tế trong Hệ thống Enterprise

Table of contents