Cấu trúc dữ liệu và Giải thuật Bài 115: Cây phân đoạn bền vững (Persistent Segment Tree) - Lưu trữ và truy vấn mọi phiên bản lịch sử của dữ liệu

Trong các bài toán hệ thống lưu trữ và cơ sở dữ liệu phân tán, nhu cầu truy vấn dữ liệu theo trục thời gian (Time-travel Query, Snapshot Isolation, cơ chế MVCC) xuất hiện liên tục. Giả sử hệ thống cần trả lời các truy vấn như: "Giá trị của tài khoản X vào thời điểm phiên bản thứ $k$ là bao nhiêu?" hoặc bài toán kinh điển trong xử lý dữ liệu: "Tìm phần tử nhỏ thứ $k$ trong đoạn từ $L$ đến $R$ mà không làm biến đổi mảng gốc".

Nếu mỗi lần cập nhật dữ liệu, hệ thống sao chép toàn bộ một cây phân đoạn mới (Deep Copy), chi phí bộ nhớ và thời gian sẽ là $O(N)$ cho mỗi thao tác — hoàn toàn bất khả thi khi có hàng trăm nghìn phiên bản. Cây phân đoạn bền vững (Persistent Segment Tree) giải quyết trọn vẹn thách thức này nhờ cơ chế Chia sẻ nút (Node Sharing / Path Copying), chỉ tiêu tốn đúng $O(\log N)$ bộ nhớ và thời gian cho mỗi phiên bản mới.

1. Nguyên lý Chia sẻ nút (Path Copying)

Khi một phần tử tại chỉ số $idx$ thay đổi giá trị trong một Segment Tree có chiều cao $H = \lceil \log_2 N \rceil$ :

Chỉ có đúng một đường đi từ nút gốc (Root) đi xuống nút lá chứa $idx$ bị ảnh hưởng.
Tất cả các nhánh cây con còn lại nằm ngoài đường đi này đều giữ nguyên cấu trúc và giá trị so với phiên bản trước.

Thay vì nhân bản toàn bộ cây, Persistent Segment Tree chỉ tạo mới đúng các nút nằm trên đường đi từ gốc xuống lá bị thay đổi. Đối với các nhánh con không thay đổi, con trỏ của nút mới sẽ trỏ trực tiếp sang các nút con của phiên bản trước đó.

Bộ nhớ phụ trợ: Mỗi phiên bản mới tạo thêm tối đa $\approx \log_2 N$ nút. Với $M$ lần cập nhật trên mảng kích thước $N$ , tổng số nút cần cấp phát chỉ là $O(N + M \log N)$ .
Quản lý phiên bản: Hệ thống chỉ cần lưu một mảng các con trỏ gốc: roots[0], roots[1], roots[2], $\dots$ , roots[m]. Mỗi con trỏ đại diện cho toàn bộ trạng thái của cây tại thời điểm đó.

2. Các thao tác cốt lõi trên Persistent Segment Tree

A. Xây dựng cây phiên bản 0 (Build)

Khởi tạo cấu trúc cây cơ sở ban đầu từ mảng đầu vào bằng đệ quy phân chia khoảng, tương tự Segment Tree tiêu chuẩn. Nút gốc trả về sẽ là roots[0].

B. Cập nhật tạo phiên bản mới (Update with Path Copying)

Hàm cập nhật nhận vào con trỏ của nút ở phiên bản trước (prevNode) và trả về một con trỏ nút mới (newNode):

Tạo bản sao nút mới: Sao chép giá trị và con trỏ từ prevNode.
Nếu đã tới nút lá: Cập nhật giá trị mới cho lá.
Nếu chưa tới lá:
- Nếu vị trí cần sửa nằm ở nhánh trái: Tạo mới con trái bằng cách đệ quy xuống prevNode.Left, giữ nguyên con trỏ sang prevNode.Right.
- Nếu vị trí cần sửa nằm ở nhánh phải: Giữ nguyên con trỏ sang prevNode.Left, tạo mới con phải bằng cách đệ quy xuống prevNode.Right.
Cập nhật lại giá trị tổng (hoặc min/max) của newNode từ hai con và trả về newNode.

C. Truy vấn theo phiên bản (Versioned Query)

Để truy vấn thông tin trên bất kỳ phiên bản $v$ nào trong lịch sử, chỉ cần truyền con trỏ gốc roots[v] vào hàm truy vấn khoảng thông thường. Mọi thao tác đọc dữ liệu diễn ra hoàn toàn độc lập với các phiên bản khác trong thời gian $O(\log N)$ .

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

Đoạn code Golang dưới đây cài đặt Persistent Segment Tree hỗ trợ lưu trữ nhiều phiên bản và truy vấn tổng khoảng trên từng phiên bản độc lập:

package main

import (
	"fmt"
)

// Cấu trúc một nút trên Persistent Segment Tree
type Node struct {
	Left  *Node
	Right *Node
	Sum   int
}

type PersistentSegmentTree struct {
	roots []*Node
	n     int
}

func NewPersistentSegmentTree(arr []int) *PersistentSegmentTree {
	n := len(arr)
	pst := &PersistentSegmentTree{
		roots: make([]*Node, 0),
		n:     n,
	}
	// Khởi tạo phiên bản gốc Version 0
	root0 := pst.build(arr, 0, n-1)
	pst.roots = append(pst.roots, root0)
	return pst
}

// Xây dựng cây phiên bản 0 ban đầu: O(N)
func (pst *PersistentSegmentTree) build(arr []int, start, end int) *Node {
	node := &Node{}
	if start == end {
		node.Sum = arr[start]
		return node
	}
	mid := (start + end) / 2
	node.Left = pst.build(arr, start, mid)
	node.Right = pst.build(arr, mid+1, end)
	node.Sum = node.Left.Sum + node.Right.Sum
	return node
}

// Cập nhật giá trị tại idx thành val, sinh ra một phiên bản mới: O(log N)
func (pst *PersistentSegmentTree) Update(version int, idx int, val int) int {
	prevRoot := pst.roots[version]
	newRoot := pst.update(prevRoot, 0, pst.n-1, idx, val)
	pst.roots = append(pst.roots, newRoot)
	return len(pst.roots) - 1 // Trả về chỉ số phiên bản mới
}

func (pst *PersistentSegmentTree) update(prev *Node, start, end, idx, val int) *Node {
	curr := &Node{}
	if start == end {
		curr.Sum = val
		return curr
	}

	mid := (start + end) / 2
	if idx <= mid {
		// Nhánh trái thay đổi -> tạo nút mới cho nhánh trái, tái sử dụng nhánh phải cũ
		curr.Left = pst.update(prev.Left, start, mid, idx, val)
		curr.Right = prev.Right
	} else {
		// Nhánh phải thay đổi -> tái sử dụng nhánh trái cũ, tạo nút mới cho nhánh phải
		curr.Left = prev.Left
		curr.Right = pst.update(prev.Right, mid+1, end, idx, val)
	}

	curr.Sum = curr.Left.Sum + curr.Right.Sum
	return curr
}

// Truy vấn tổng trên một phiên bản cụ thể: O(log N)
func (pst *PersistentSegmentTree) Query(version int, l, r int) int {
	if version < 0 || version >= len(pst.roots) {
		return 0
	}
	return pst.query(pst.roots[version], 0, pst.n-1, l, r)
}

func (pst *PersistentSegmentTree) query(node *Node, start, end, l, r int) int {
	if node == nil || r < start || end < l {
		return 0
	}
	if l <= start && end <= r {
		return node.Sum
	}
	mid := (start + end) / 2
	leftSum := pst.query(node.Left, start, mid, l, r)
	rightSum := pst.query(node.Right, mid+1, end, l, r)
	return leftSum + rightSum
}

func main() {
	// Mảng ban đầu: [1, 2, 3, 4]
	initialData := []int{1, 2, 3, 4}
	pst := NewPersistentSegmentTree(initialData)

	fmt.Printf("Version 0 - Tổng đoạn [0, 3]: %d\n", pst.Query(0, 0, 3)) // 1 + 2 + 3 + 4 = 10

	// Version 1: Thay đổi phần tử tại index 1 từ 2 thành 10 -> [1, 10, 3, 4]
	v1 := pst.Update(0, 1, 10)
	fmt.Printf("Version 1 (sửa index 1 = 10) - Tổng đoạn [0, 3]: %d\n", pst.Query(v1, 0, 3)) // 1 + 10 + 3 + 4 = 18

	// Version 2: Xuất phát từ Version 1, sửa phần tử tại index 3 từ 4 thành 20 -> [1, 10, 3, 20]
	v2 := pst.Update(v1, 3, 20)
	fmt.Printf("Version 2 (sửa index 3 = 20) - Tổng đoạn [0, 3]: %d\n", pst.Query(v2, 0, 3)) // 1 + 10 + 3 + 20 = 34

	// Kiểm tra tính bất biến: Truy vấn lại Version 0 và Version 1
	fmt.Println("\n--- Kiểm tra tính bất biến của các phiên bản lịch sử ---")
	fmt.Printf("Truy vấn lại Version 0 đoạn [0, 3]: %d (Không đổi)\n", pst.Query(0, 0, 3))
	fmt.Printf("Truy vấn lại Version 1 đoạn [0, 3]: %d (Không đổi)\n", pst.Query(v1, 0, 3))
}

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

Bài toán Range $k$ -th Smallest Query: Khi kết hợp Persistent Segment Tree với kỹ thuật nén tọa độ và lưu trữ tần suất tích lũy (Prefix Trees), ta có thể tìm phần tử nhỏ thứ $k$ trên bất kỳ đoạn con $[L, R]$ nào trong thời gian $O(\log N)$ bằng cách trừ hai cây: $\text{Tree}[R] - \text{Tree}[L-1]$ .
Hệ thống cơ sở dữ liệu (Database Snapshots & MVCC): Cung cấp khả năng cô lập giao dịch (Snapshot Isolation) mà không cần khóa bảng (table locks), cho phép các luồng đọc dữ liệu lịch sử song song với các luồng ghi phiên bản mới.
Audit Logging & Undo/Redo Engine: Lưu trữ dấu vết kiểm toán tài chính và các trạng thái rollback giao dịch cực kỳ tiết kiệm RAM nhờ tính chất chia sẻ nút.

Persistent Segment Tree là ví dụ điển hình cho tư duy cấu trúc dữ liệu hàm (Functional Data Structures) — biến một cấu trúc cây tĩnh thành một hệ thống lưu trữ lịch sử đa phiên bản hiệu năng cao.

cấu trúc dữ liệu