Cấu trúc dữ liệu và Giải thuật Bài 123: Hợp nhất cây phân đoạn (Segment Tree Merging) - Hợp nhất thông tin cây con linh hoạt và hỗ trợ trực tuyến.

Trong khi kỹ thuật DSU on Tree (Bài 122) giải quyết hiệu quả các bài toán thống kê cây con ngoại tuyến trong $O(N \log N)$ thời gian và $O(N)$ bộ nhớ, nó có một hạn chế lớn: chỉ trả lời được kết quả thống kê đơn giản tại thời điểm duyệt DFS và bắt buộc phải xóa trạng thái của các nhánh nhẹ. Khi bài toán đòi hỏi duy trì toàn bộ phân phối giá trị của từng cây con để phục vụ các truy vấn phức tạp hơn — ví dụ: tìm phần tử xuất hiện nhiều lần nhất kèm tổng giá trị của chúng, tìm giá trị nhỏ thứ $k$ trong cây con, hoặc kết hợp với quy hoạch động trên cây (Tree DP) — DSU on Tree trở nên cồng kềnh.

Hợp nhất cây phân đoạn (Segment Tree Merging) là kỹ thuật xây dựng cho mỗi nút một Cây phân đoạn động (Dynamic Segment Tree), sau đó hợp nhất (merge) cây của các nút con vào nút cha theo thứ tự hậu thứ tự (post-order traversal). Kỹ thuật này đạt độ phức tạp thời gian $O(N \log M)$ và mở ra khả năng xử lý linh hoạt vượt trội so với các phương pháp gộp tập hợp truyền thống.

1. Bản chất của Segment Tree Merging

Xét tập giá trị cần quản lý nằm trong miền $[1, M]$ . Với mỗi nút $u$ trên cây:

Ban đầu, khởi tạo một cây phân đoạn động chỉ chứa giá trị ban đầu của chính nút $u$ . Chiều cao của cây là $\lceil \log_2 M \rceil$ , tiêu tốn tối đa $O(\log M)$ nút nhớ mới.
Khi duyệt DFS đến $u$ , ta đệ quy giải quyết tất cả các nút con $v$ của $u$ .
Sau khi nút con $v$ đã có cây phân đoạn hoàn chỉnh đại diện cho toàn bộ cây con gốc $v$ , ta thực hiện phép gộp:

$\text{root}[u] = \text{Merge}(\text{root}[u], \text{root}[v], 1, M)$

        Cây con u                      Cây con v
       [1 -------- 4]                 [1 -------- 4]
       /            \                 /            \
    [1--2]         nil             [1--2]         [3--4]
    /    \                         /    \         /    \
  [1]    nil                     nil    [2]     [3]    nil

                        Sau khi Merge
                       [1 -------- 4]
                       /            \
                    [1--2]         [3--4]
                    /    \         /    \
                  [1]    [2]     [3]    nil

2. Phân tích độ phức tạp thời gian và không gian

Nhiều lập trình viên lầm tưởng việc đệ quy duyệt qua hai cây phân đoạn để gộp sẽ tốn $O(N^2 \log M)$ . Tuy nhiên, chi phí thực tế được chặn ở mức $O(N \log M)$ .

Chứng minh bằng phương pháp thế năng (Amortized Analysis)

Số lượng nút khởi tạo ban đầu: Có $N$ đỉnh, mỗi đỉnh chỉ chèn 1 phần tử vào cây phân đoạn động của nó. Tổng số nút của tất cả các cây phân đoạn được tạo ra trên toàn hệ thống tối đa là:

$S_{\text{initial}} \le N \lceil \log_2 M \rceil$
Hàm Merge(u, v) hoạt động theo quy tắc:
- Nếu một trong hai con trỏ u hoặc v rỗng (nil hoặc 0), hàm dừng ngay lập tức trong $O(1)$ và trả về con trỏ còn lại.
- Nếu cả u và v đều tồn tại, hàm thực hiện gộp thông tin và đệ quy xuống hai nhánh con. Tại bước này, một trong hai nút (u hoặc v) sẽ bị hấp thụ hoặc giải phóng.
Kết luận: Mỗi bước đệ quy tiêu tốn $O(1)$ thời gian và làm giảm tổng số lượng nút còn tồn tại trong toàn bộ hệ thống đi đúng 1 nút. Vì tổng số nút ban đầu là $O(N \log M)$ , tổng số lần hàm Merge đi vào trường hợp cả hai con trỏ đều khác rỗng trên toàn bộ quá trình chạy không bao giờ vượt quá $O(N \log M)$ .

Do đó, tổng thời gian của tất cả các thao tác hợp nhất là $O(N \log M)$ , và dung lượng bộ nhớ tối đa là $O(N \log M)$ .

3. Hiện thực hóa Segment Tree Merging bằng Golang

Bài toán kinh điển: Cho cây gồm $N$ đỉnh, mỗi đỉnh $u$ có một màu $C[u]$ . Với mỗi đỉnh $u$ , tìm tổng các màu có số lần xuất hiện nhiều nhất (maximum frequency) trong toàn bộ cây con của $u$ . (Bài toán kinh điển Codeforces 600E - Lomsat gelbral).

Đoạn mã Golang dưới đây sử dụng mảng tĩnh cấp phát trước (Node Pool) để tối ưu cache và tránh overhead của bộ gom rác (Garbage Collector):

package main

import (
	"bufio"
	"fmt"
	"os"
)

// Cấu trúc một nút trên Dynamic Segment Tree
type STNode struct {
	left, right int
	maxFreq     int   // Tần suất xuất hiện lớn nhất của một màu
	sumColors   int64 // Tổng các màu đạt tần suất lớn nhất đó
}

const MAXNODES = 4000000 // N * log(MAX_COLOR)

var (
	tree      []STNode
	nodeCount int
	roots     []int
)

func newNode() int {
	nodeCount++
	tree[nodeCount] = STNode{}
	return nodeCount
}

// Cập nhật thông tin từ hai con lên nút cha
func pushUp(u int) {
	l := tree[u].left
	r := tree[u].right

	if l == 0 {
		tree[u].maxFreq = tree[r].maxFreq
		tree[u].sumColors = tree[r].sumColors
		return
	}
	if r == 0 {
		tree[u].maxFreq = tree[l].maxFreq
		tree[u].sumColors = tree[l].sumColors
		return
	}

	if tree[l].maxFreq > tree[r].maxFreq {
		tree[u].maxFreq = tree[l].maxFreq
		tree[u].sumColors = tree[l].sumColors
	} else if tree[r].maxFreq > tree[l].maxFreq {
		tree[u].maxFreq = tree[r].maxFreq
		tree[u].sumColors = tree[r].sumColors
	} else {
		tree[u].maxFreq = tree[l].maxFreq
		tree[u].sumColors = tree[l].sumColors + tree[r].sumColors
	}
}

// Chèn một màu vào Dynamic Segment Tree: O(log M)
func update(node *int, l, r, color int) {
	if *node == 0 {
		*node = newNode()
	}
	if l == r {
		tree[*node].maxFreq++
		tree[*node].sumColors = int64(color)
		return
	}

	mid := (l + r) / 2
	if color <= mid {
		update(&tree[*node].left, l, mid, color)
	} else {
		update(&tree[*node].right, mid+1, r, color)
	}
	pushUp(*node)
}

// Hàm gộp hai Dynamic Segment Tree: Amortized O(1) cho mỗi nút bị triệt tiêu
func merge(u, v, l, r int) int {
	if u == 0 {
		return v
	}
	if v == 0 {
		return u
	}

	if l == r {
		tree[u].maxFreq += tree[v].maxFreq
		// Giữ nguyên sumColors = l vì cả hai đều biểu diễn cùng một màu
		return u
	}

	mid := (l + r) / 2
	tree[u].left = merge(tree[u].left, tree[v].left, l, mid)
	tree[u].right = merge(tree[u].right, tree[v].right, mid+1, r)
	pushUp(u)
	return u
}

var (
	n        int
	colors   []int
	adj      [][]int
	ans      []int64
	maxColor int
)

func dfs(u, p int) {
	// 1. Khởi tạo cây phân đoạn chứa màu của chính nút u
	update(&roots[u], 1, maxColor, colors[u])

	// 2. Duyệt các nút con và hợp nhất cây của con vào u
	for _, v := range adj[u] {
		if v != p {
			dfs(v, u)
			roots[u] = merge(roots[u], roots[v], 1, maxColor)
		}
	}

	// 3. Kết quả cho nút u chính là giá trị tại gốc sau khi hợp nhất
	ans[u] = tree[roots[u]].sumColors
}

func main() {
	// Khởi tạo cây mẫu gồm 4 đỉnh (1 đến 4)
	n = 4
	maxColor = 4
	colors = []int{0, 1, 2, 1, 1} // Index từ 1: Đỉnh 1 (màu 1), Đỉnh 2 (màu 2), Đỉnh 3 (màu 1), Đỉnh 4 (màu 1)

	adj = make([][]int, n+1)
	addEdge := func(u, v int) {
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	// Cấu trúc cây:
	//       1 (màu 1)
	//      / \
	// 2 (màu 2) 3 (màu 1)
	//    |
	// 4 (màu 1)
	addEdge(1, 2)
	addEdge(1, 3)
	addEdge(2, 4)

	tree = make([]STNode, MAXNODES)
	roots = make([]int, n+1)
	ans = make([]int64, n+1)
	nodeCount = 0

	dfs(1, 0)

	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()
	fmt.Fprintln(writer, "Tổng các màu có tần suất lớn nhất trong cây con của từng đỉnh:")
	for i := 1; i <= n; i++ {
		fmt.Fprintf(writer, "Đỉnh %d: %d\n", i, ans[i])
	}
}

4. Bảng so sánh giữa DSU on Tree và Segment Tree Merging

Tiêu chí	DSU on Tree (Sack)	Segment Tree Merging
Độ phức tạp thời gian	$O(N \log N)$	$O(N \log M)$ ( $M$ là miền giá trị)
Độ phức tạp bộ nhớ	$O(N)$	$O(N \log M)$
Hằng số thực thi	Rất nhỏ (mảng tuần tự)	Lớn hơn do cấu trúc cây động
Khả năng trả lời trực tuyến (Online)	Không (phải trả lời ngay khi duyệt DFS)	Có (giữ lại các gốc `roots[u]` để truy vấn sau)
Phạm vi bài toán giải quyết	Thống kê số lượng/tần suất cơ bản	Hỗ trợ tìm kiếm phân vị ( $K$ -th), Range Query trên miền giá trị, Tree DP
Khả năng phân tách (Split)	Không hỗ trợ	Hỗ trợ phân tách cây phân đoạn (Segment Tree Splitting)

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

Tối ưu hóa bài toán Quy hoạch động trên cây (Tree DP Optimization): Khi mảng trạng thái quy hoạch động tại mỗi nút con phụ thuộc vào một miền giá trị liên tục, việc gộp hai bảng DP có thể chuyển thành phép gộp hai cây phân đoạn kết hợp Lazy Propagation trong $O(N \log M)$ .
Hệ thống phân tích rủi ro trong mạng phân cấp (Hierarchical Risk Scoring): Trong hạ tầng tài chính, mỗi phòng giao dịch cấp dưới báo cáo danh mục rủi ro. Segment Tree Merging cho phép tổng hợp phân phối tổn thất cận biên (Value at Risk - VaR) theo từng cụm chi nhánh lên hội sở mà không cần gom dữ liệu thô về một chỗ.
Xử lý đồ thị động kết hợp Cây khung (Dynamic MST): Phối hợp với Disjoint Set Union để quản lý tập các cạnh ứng viên khi gộp các thành phần liên thông trong thuật toán Borůvka.

cấu trúc dữ liệu