Cấu trúc dữ liệu và Giải thuật Bài 127: Cây phân nhánh toàn cục (Balanced Top Trees / Global Balanced Tree) - Tối ưu hóa DDP và duy trì cấu trúc động trong $O(\log N)$

Ở Bài 126, phương pháp Quy hoạch động động trên cây (Dynamic Tree DP - DDP) kết hợp Phân rã cây nặng - nhẹ (HLD) và Cây phân đoạn (Segment Tree) đã giảm độ phức tạp cập nhật từ $O(N)$ xuống $O(\log^2 N)$. Tuy nhiên, hệ số $\log^2 N$ xuất hiện do sự phân tách giữa hai tầng cấu trúc độc lập: mỗi lần cập nhật phải leo qua tối đa $O(\log N)$ chuỗi nặng, và tại mỗi chuỗi nặng lại tiêu tốn $O(\log N)$ để truy vấn Segment Tree.

Để phá vỡ giới hạn này và đạt độ phức tạp tối ưu $O(\log N)$ cho mỗi thao tác cập nhật, chúng ta cần hợp nhất hai tầng phân cấp này thành một cấu trúc duy nhất: Cây cân bằng toàn cục (Global Balanced Tree - GBT) hoặc mô hình hình thức tổng quát hơn là Balanced Top Trees (Rake-Compress Trees).

1. Nút thắt của HLD và Nguyên lý Cây cân bằng toàn cục (GBT)

Trong mô hình HLD truyền thống, mỗi chuỗi nặng được quản lý bởi một Segment Tree độc lập. Khi một đỉnh con nhẹ thay đổi, kết quả được đẩy lên đỉnh cha trên chuỗi nặng khác thông qua một bước nhảy rời rạc.

Mô hình HLD + SegTree (2 tầng riêng biệt):
Chuỗi nặng 1: [SegTree 1]  (chi phí O(log N))
      ^ (nhảy cạnh nhẹ)
Chuỗi nặng 2: [SegTree 2]  (chi phí O(log N))
=> Tổng chi phí leo lên gốc: O(log N) * O(log N) = O(log^2 N)

Global Balanced Tree (GBT) giải quyết vấn đề này bằng cách:

1. Không dùng Segment Tree thông thường với phép chia đôi chỉ số mảng ($mid = (l + r) / 2$).

2. Trên mỗi chuỗi nặng, xây dựng một Cây tìm kiếm nhị phân cân bằng theo trọng số (Weight-Balanced BST). Trọng số của mỗi đỉnh $u$ trên chuỗi được định nghĩa là kích thước của các nhánh con nhẹ đổ vào nó:

   $$w(u) = sz[u] - sz[hc(u)]$$

   (với $hc(u)$ là con nặng của $u$).

3. Điểm chia đôi (gốc của cây con BST) được chọn là trọng tâm theo trọng số (Weighted Median) của chuỗi, sao cho tổng trọng số hai nửa trái và phải xấp xỉ bằng nhau.

4. Gốc của các cây BST nhánh nhẹ được nối trực tiếp vào các nút tương ứng trên chuỗi nặng cha qua liên kết cạnh nhẹ.

Định lý chặn chiều cao toàn cục $O(\log N)$

Khi leo từ một đỉnh $u$ bất kỳ lên gốc toàn cục của GBT:

• Nếu đi lên một nút cha trong cùng một chuỗi nặng (cạnh BST nội bộ): Trọng số của cây con BST tăng lên ít nhất theo tỷ lệ cân bằng.

• Nếu đi qua một cạnh nhẹ lên chuỗi nặng cha: Kích thước cây con thực tế tăng ít nhất gấp đôi do tính chất của cạnh nhẹ trong HLD.

Vì tổng kích thước của toàn bộ cây bị chặn bởi $N$, tổng số bước leo từ bất kỳ nút nào lên đến gốc duy nhất của GBT không bao giờ vượt quá $C \cdot \log_2 N$. Mọi cập nhật chỉ cần một vòng lặp đơn đi thẳng lên gốc trong đúng $O(\log N)$ phép nhân ma trận.

2. Mô hình hình thức: Hai toán tử Rake và Compress

Lý thuyết Top Trees (Alstrup, Holm, de Lichtenberg, Thorup) tổng quát hóa cấu trúc cây động thông qua việc co cây (Tree Contraction) bằng hai toán tử cơ bản:

               (v)                              (u)
              /   \                              |
            (u)   (w)                         [Compress]
             |     |                             |
          [Compress]                            (w)
          Ghép 2 đoạn đường đi              Nén chuỗi cạnh

                  (u)                           (u)
                 /   \                           |
               (v)   (w)                      [Rake]
                |     |                          |
              (nhánh con nhẹ)              Gom cụm nhánh nhẹ

1. Compress (Nén đường đi): Gộp hai cụm đường đi nối tiếp nhau thành một cụm đường đi lớn hơn. Trong DDP, thao tác này tương ứng với phép nhân ma trận chuyển trạng thái dọc theo chuỗi:

   $$P = P_{\text{left}} \otimes M_u \otimes P_{\text{right}}$$

2. Rake (Cào / Gom cụm nhánh): Gộp một cụm nhánh con (không nằm trên đường đi chính) vào một đỉnh nằm trên đường đi. Trong DDP, thao tác này tương ứng với việc tích lũy các giá trị DP của nhánh nhẹ vào vector $g[u]$:

   $$g[u][0] = \sum_{v \in \text{Light}(u)} \max(dp[v][0], dp[v][1])$$

Trong GBT, các liên kết trái/phải (ls, rs) trong cây BST nội bộ chính là toán tử Compress, còn liên kết giữa các chuỗi con nhẹ với đỉnh trên chuỗi nặng chính là toán tử Rake.

3. Hiện thực hóa Global Balanced Tree (GBT) bằng Golang

Chương trình dưới đây cài đặt hoàn chỉnh GBT để giải quyết bài toán Tập độc lập trọng số cực đại (MWIS) với thời gian cập nhật $O(\log N)$:

Go

package main

import (
	"fmt"
	"math"
)

const INF = math.MaxInt64 / 4

// Matrix 2x2 trên Vành bán nhiệt đới (max, +)
type Matrix [2][2]int64

func NewMatrix() Matrix {
	var m Matrix
	m[0][0], m[0][1] = -INF, -INF
	m[1][0], m[1][1] = -INF, -INF
	return m
}

func Multiply(a, b Matrix) Matrix {
	c := NewMatrix()
	for i := 0; i < 2; i++ {
		for k := 0; k < 2; k++ {
			if a[i][k] <= -INF {
				continue
			}
			for j := 0; j < 2; j++ {
				if b[k][j] <= -INF {
					continue
				}
				val := a[i][k] + b[k][j]
				if val > c[i][j] {
					c[i][j] = val
				}
			}
		}
	}
	return c
}

type GBTNode struct {
	ls, rs int // Con trái, con phải trong BST của chuỗi nặng (Compress)
	p      int // Nút cha trong GBT toàn cục
	isRoot bool // True nếu nút là gốc của một BST chuỗi nặng (nối với cha qua cạnh nhẹ)

	mat  Matrix // Ma trận riêng của đỉnh u (chứa g-values)
	prod Matrix // Tích ma trận của toàn bộ cây con BST: prod(ls) * mat * prod(rs)
}

type GBT struct {
	n          int
	adj        [][]int
	weight     []int64
	sz         []int
	heavy      []int
	parent     []int
	g          [][2]int64
	dp         [][2]int64
	nodes      []GBTNode
	globalRoot int
}

func NewGBT(n int, weights []int64) *GBT {
	return &GBT{
		n:      n,
		adj:    make([][]int, n+1),
		weight: weights,
		sz:     make([]int, n+1),
		heavy:  make([]int, n+1),
		parent: make([]int, n+1),
		g:      make([][2]int64, n+1),
		dp:     make([][2]int64, n+1),
		nodes:  make([]GBTNode, n+1),
	}
}

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

func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

// DFS 1: Xác định kích thước và con nặng
func (gbt *GBT) dfs1(u, p int) {
	gbt.sz[u] = 1
	gbt.parent[u] = p
	gbt.heavy[u] = 0
	maxChild := 0

	for _, v := range gbt.adj[u] {
		if v != p {
			gbt.dfs1(v, u)
			gbt.sz[u] += gbt.sz[v]
			if gbt.sz[v] > maxChild {
				maxChild = gbt.sz[v]
				gbt.heavy[u] = v
			}
		}
	}
}

// DFS 2: Tính toán g-values và giá trị DP ban đầu
func (gbt *GBT) dfs2(u int) {
	gbt.g[u][0] = 0
	gbt.g[u][1] = gbt.weight[u]
	gbt.dp[u][0] = 0
	gbt.dp[u][1] = gbt.weight[u]

	if gbt.heavy[u] != 0 {
		gbt.dfs2(gbt.heavy[u])
		gbt.dp[u][0] += max(gbt.dp[gbt.heavy[u]][0], gbt.dp[gbt.heavy[u]][1])
		gbt.dp[u][1] += gbt.dp[gbt.heavy[u]][0]
	}

	for _, v := range gbt.adj[u] {
		if v != gbt.parent[u] && v != gbt.heavy[u] {
			gbt.dfs2(v)
			gbt.g[u][0] += max(gbt.dp[v][0], gbt.dp[v][1])
			gbt.g[u][1] += gbt.dp[v][0]
			gbt.dp[u][0] += max(gbt.dp[v][0], gbt.dp[v][1])
			gbt.dp[u][1] += gbt.dp[v][0]
		}
	}
	gbt.updateMatrix(u)
}

func (gbt *GBT) updateMatrix(u int) {
	gbt.nodes[u].mat[0][0] = gbt.g[u][0]
	gbt.nodes[u].mat[0][1] = gbt.g[u][0]
	gbt.nodes[u].mat[1][0] = gbt.g[u][1]
	gbt.nodes[u].mat[1][1] = -INF
}

// Cập nhật giá trị prod của một nút từ hai con
func (gbt *GBT) pushUp(u int) {
	prod := gbt.nodes[u].mat
	if gbt.nodes[u].ls != 0 {
		prod = Multiply(gbt.nodes[gbt.nodes[u].ls].prod, prod)
	}
	if gbt.nodes[u].rs != 0 {
		prod = Multiply(prod, gbt.nodes[gbt.nodes[u].rs].prod)
	}
	gbt.nodes[u].prod = prod
}

// Xây dựng BST cân bằng theo trọng số cho một chuỗi nặng
func (gbt *GBT) buildChainBST(chain []int, l, r int) int {
	if l > r {
		return 0
	}

	totW := 0
	for i := l; i <= r; i++ {
		u := chain[i]
		totW += gbt.sz[u] - gbt.sz[gbt.heavy[u]]
	}

	// Tìm Weighted Median
	currW := 0
	mid := l
	for i := l; i <= r; i++ {
		u := chain[i]
		currW += gbt.sz[u] - gbt.sz[gbt.heavy[u]]
		if currW*2 >= totW {
			mid = i
			break
		}
	}

	root := chain[mid]
	gbt.nodes[root].ls = gbt.buildChainBST(chain, l, mid-1)
	if gbt.nodes[root].ls != 0 {
		gbt.nodes[gbt.nodes[root].ls].p = root
		gbt.nodes[gbt.nodes[root].ls].isRoot = false
	}

	gbt.nodes[root].rs = gbt.buildChainBST(chain, mid+1, r)
	if gbt.nodes[root].rs != 0 {
		gbt.nodes[gbt.nodes[root].rs].p = root
		gbt.nodes[gbt.nodes[root].rs].isRoot = false
	}

	gbt.pushUp(root)
	return root
}

// Đệ quy dựng GBT từ đỉnh đầu chuỗi nặng
func (gbt *GBT) buildGBT(top int) int {
	// 1. Duyệt và dựng GBT cho tất cả các nhánh nhẹ phát sinh từ chuỗi này
	var chain []int
	for u := top; u != 0; u = gbt.heavy[u] {
		chain = append(chain, u)
		for _, v := range gbt.adj[u] {
			if v != gbt.parent[u] && v != gbt.heavy[u] {
				subRoot := gbt.buildGBT(v)
				gbt.nodes[subRoot].p = u
				gbt.nodes[subRoot].isRoot = true
			}
		}
	}

	// 2. Dựng BST cân bằng cho chính chuỗi nặng này
	bstRoot := gbt.buildChainBST(chain, 0, len(chain)-1)
	return bstRoot
}

func (gbt *GBT) Init() {
	gbt.dfs1(1, 0)
	gbt.dfs2(1)
	gbt.globalRoot = gbt.buildGBT(1)
	gbt.nodes[gbt.globalRoot].isRoot = true
}

// Cập nhật trọng số đỉnh: Đi thẳng một mạch lên gốc toàn cục trong O(log N)
func (gbt *GBT) UpdateWeight(u int, newWeight int64) {
	gbt.g[u][1] += newWeight - gbt.weight[u]
	gbt.weight[u] = newWeight
	gbt.updateMatrix(u)

	curr := u
	for curr != 0 {
		if gbt.nodes[curr].isRoot {
			gbt.pushUp(curr)
			p := gbt.nodes[curr].p
			if p == 0 {
				break
			}
			// Nhảy qua cạnh nhẹ: Lấy DP cũ của chuỗi con
			oldP0 := max(gbt.nodes[curr].prod[0][0], gbt.nodes[curr].prod[0][1])
			oldP1 := max(gbt.nodes[curr].prod[1][0], gbt.nodes[curr].prod[1][1])

			// Tính DP mới của chuỗi con
			gbt.pushUp(curr)
			newP0 := max(gbt.nodes[curr].prod[0][0], gbt.nodes[curr].prod[0][1])
			newP1 := max(gbt.nodes[curr].prod[1][0], gbt.nodes[curr].prod[1][1])

			// Cập nhật g-values cho nút cha trên chuỗi khác
			gbt.g[p][0] += max(newP0, newP1) - max(oldP0, oldP1)
			gbt.g[p][1] += newP0 - oldP0
			gbt.updateMatrix(p)

			curr = p
		} else {
			gbt.pushUp(curr)
			curr = gbt.nodes[curr].p
		}
	}
}

// Lấy kết quả MWIS của toàn bộ cây trong O(1)
func (gbt *GBT) QueryMWIS() int64 {
	rootMat := gbt.nodes[gbt.globalRoot].prod
	ans0 := max(rootMat[0][0], rootMat[0][1])
	ans1 := max(rootMat[1][0], rootMat[1][1])
	return max(ans0, ans1)
}

func main() {
	// Cây gồm 5 đỉnh (đỉnh 1 đến 5)
	weights := []int64{0, 5, 2, 8, 3, 4}
	n := 5
	gbt := NewGBT(n, weights)

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

	gbt.Init()

	fmt.Printf("Trọng số MWIS ban đầu: %d\n", gbt.QueryMWIS())

	// Cập nhật trọng số đỉnh 3 thành 50 trong O(log N)
	fmt.Println("Cập nhật: Đỉnh 3 đổi trọng số thành 50...")
	gbt.UpdateWeight(3, 50)
	fmt.Printf("Trọng số MWIS sau khi cập nhật đỉnh 3: %d\n", gbt.QueryMWIS())

	// Cập nhật trọng số đỉnh 1 thành 100
	fmt.Println("Cập nhật: Đỉnh 1 đổi trọng số thành 100...")
	gbt.UpdateWeight(1, 100)
	fmt.Printf("Trọng số MWIS sau khi cập nhật đỉnh 1: %d\n", gbt.QueryMWIS())
}

4. Bảng so sánh hiệu năng các cấu trúc DDP

Trong đó $c$ là kích thước ma trận chuyển trạng thái ($c = 2$ đối với bài toán MWIS).

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

• Hệ thống giao dịch tài chính tần suất cao (HFT Risk Engine): Tính toán lại rủi ro danh mục phụ thuộc dạng cây phân tầng ngay lập tức khi giá của một tài sản cơ sở biến động liên tục trong micro-giây.

• Cân bằng tải lưới điện thông minh (Smart Grid Dynamic Load): Khi một trạm biến áp hoặc đường dây truyền tải thay đổi công suất, cấu trúc GBT cho phép tính toán lại bài toán dòng công suất tối ưu (Optimal Power Flow) tức thời với số lượng phép toán tối thiểu.

• Mô phỏng vật lý đồ họa & Động học ngược (Inverse Kinematics): Tính toán ma trận biến dạng xương (Skeletal Transform Hierarchy) của các mô hình nhân vật phức tạp trong game engine khi các khớp cử động liên tục.