Cấu trúc dữ liệu và Giải thuật Bài 101: Cây phân đoạn (Segment Tree) - Vũ khí tối thượng cho bài toán truy vấn khoảng (Range Queries).

Bước sang giai đoạn nâng cao của chuỗi thuật toán, chúng ta đối mặt với một bài toán kinh điển trong khoa học máy tính: Bài toán Truy vấn Khoảng (Range Query Problem) kèm theo Cập nhật dữ liệu động (Dynamic Updates).

Giả sử bạn có một mảng gồm $1,000,000$ phần tử (ví dụ: số dư tài khoản của khách hàng hoặc lượng tồn kho theo thời gian thực). Hệ thống liên tục nhận được hai loại yêu cầu hỗn hợp:

Update: Thay đổi giá trị tại một vị trí bất kỳ ( $A[i] = v$ ).
Query: Tính tổng (hoặc tìm giá trị nhỏ nhất/lớn nhất) của các phần tử từ vị trí $L$ đến $R$ ( $A[L \dots R]$ ).

Nếu sử dụng Mảng thông thường: Cập nhật mất $O(1)$ , nhưng tính tổng khoảng $L \to R$ mất $O(N)$ trong trường hợp xấu nhất.

Nếu sử dụng Mảng cộng dồn (Prefix Sum): Tính tổng khoảng mất $O(1)$ , nhưng khi có một phần tử thay đổi, bạn phải tính lại toàn bộ mảng Prefix Sum với độ phức tạp $O(N)$ .

Khi tần suất cập nhật và truy vấn đều cao, cả hai cách tiếp cận trên đều sập nguồn. Cây phân đoạn (Segment Tree) ra đời để giải quyết bài toán này với độ phức tạp cực kỳ tối ưu: $O(\log N)$ cho cả hai thao tác Update và Query.

1. Cấu trúc của một Segment Tree

Segment Tree là một cây nhị phân hoàn chỉnh (Binary Tree) trong đó:

Mỗi nút (node) đại diện cho một Khoảng (Segment) $[L, R]$ trên mảng ban đầu.
Nút gốc (Root) đại diện cho toàn bộ mảng $[0, N-1]$ .
Mỗi nút không phải nút lá sẽ chia đôi khoảng của nó thành hai nhánh con: Nhánh trái $[L, \text{mid}]$ và Nhánh phải $[\text{mid}+1, R]$ .
Các nút lá đại diện cho từng phần tử đơn lẻ $[i, i]$ của mảng.

Giả sử mảng ban đầu có 4 phần tử: [1, 3, 5, 7]. Cây phân đoạn lưu trữ tổng các khoảng sẽ có dạng:

Root [0, 3]: Giá trị tổng = 16 (Toàn bộ mảng)
- Trái [0, 1]: Giá trị tổng = 4 (Khoảng [1, 3])
- - Lá [0, 0]: 1
- - Lá [1, 1]: 3
- Phải [2, 3]: Giá trị tổng = 12 (Khoảng [5, 7])
- - Lá [2, 2]: 5
- - Lá [3, 3]: 7

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

A. Xây dựng cây (Build Tree)

Ta bắt đầu từ nút gốc và đệ quy chia đôi mảng cho đến khi gặp nút lá. Giá trị của một nút cha bằng tổng (hoặc min/max) của hai nút con trái và phải.

Độ phức tạp thời gian: $O(N)$ vì mỗi phần tử được ghé thăm một số lần hằng số.

B. Truy vấn khoảng (Range Query)

Khi cần tìm tổng từ $L$ đến $R$ , ta xuất phát từ Root và so sánh khoảng của nút hiện tại với khoảng $[L, R]$ cần tìm:

Nằm hoàn toàn ngoài ( $[L, R]$ không giao nhau với nút hiện tại): Trả về giá trị trung hòa (0 đối với tổng, $\infty$ đối với min).
Nằm hoàn toàn trong ( $[L, R$ chứa trọn vẹn khoảng của nút hiện tại): Trả về luôn giá trị đã được lưu sẵn tại nút đó mà không cần đi sâu xuống dưới.
Giao nhau một phần: Chia đôi, đệ quy gọi xuống cả hai con trái và phải, sau đó cộng kết quả lại.

Độ phức tạp thời gian: $O(\log N)$ vì thuật toán chỉ duyệt qua một số ít nhánh giao nhau ở mỗi tầng của cây.

C. Cập nhật điểm (Point Update)

Khi một phần tử tại vị trí $idx$ thay đổi giá trị, ta đi từ nút lá chứa $idx$ đi ngược lên nút gốc (Upward Update), cập nhật lại giá trị tổng cho các nút cha trên đường đi.

Độ phức tạp thời gian: $O(\log N)$ tương ứng với chiều cao của cây.

4. Hiện thực hóa Segment Tree (Range Sum Query) bằng Golang

Đoạn code Golang dưới đây cài đặt đầy đủ cấu trúc một Segment Tree bằng mảng (Array-based representation, thường lưu trữ trong mảng kích thước $4N$ ), hỗ trợ cả hai thao tác truy vấn tổng khoảng và cập nhật giá trị:

package main

import (
	"fmt"
)

type SegmentTree struct {
	tree []int
	arr  []int
	n    int
}

// Khởi tạo và xây dựng Segment Tree
func NewSegmentTree(arr []int) *SegmentTree {
	n := len(arr)
	tree := make([]int, 4*n)
	st := &SegmentTree{
	tree: tree,
		arr:  arr,
		n:    n,
	}
	st.build(0, 0, n-1)
	return st
}

// Hàm đệ quy xây dựng cây (Build)
func (st *SegmentTree) build(node, start, end int) {
	if start == end {
		// Nút lá lưu giá trị của mảng gốc
		st.tree[node] = st.arr[start]
		return
	}
	mid := (start + end) / 2
	leftNode := 2*node + 1
	rightNode := 2*node + 2

	st.build(leftNode, start, mid)
	st.build(rightNode, mid+1, end)

	// Giá trị nút cha bằng tổng hai nút con
	st.tree[node] = st.tree[leftNode] + st.tree[rightNode]
}

// Truy vấn tổng khoảng từ L đến R (Range Query [L, R])
func (st *SegmentTree) Query(node, start, end, l, r int) int {
	// Trường hợp 1: Ngoài khoảng cần truy vấn
	if r < start || end < l {
		return 0
	}
	// Trường hợp 2: Nằm trọn vẹn trong khoảng cần truy vấn
	if l <= start && end <= r {
		return st.tree[node]
	}
	// Trường hợp 3: Giao nhau một phần -> Chia đôi tiếp tục tìm kiếm
	mid := (start + end) / 2
	p1 := st.Query(2*node+1, start, mid, l, r)
	p2 := st.Query(2*node+2, mid+1, end, l, r)
	return p1 + p2
}

// Cập nhật giá trị phần tử tại vị trí idx thành val (Point Update)
func (st *SegmentTree) Update(node, start, end, idx int, val int) {
	if start == end {
		// Đã tìm đến nút lá chứa idx, tiến hành cập nhật
		st.arr[idx] = val
		st.tree[node] = val
		return
	}
	mid := (start + end) / 2
	leftNode := 2*node + 1
	rightNode := 2*node + 2

	if idx <= mid {
		st.Update(leftNode, start, mid, idx, val)
	} else {
		st.Update(rightNode, mid+1, end, idx, val)
	}

	// Cập nhật lại giá trị nút cha trên đường đi ngược lên (Upward Update)
	st.tree[node] = st.tree[leftNode] + st.tree[rightNode]
}

func main() {
	// Mảng ban đầu
	data := []int{1, 3, 5, 7, 9, 11}
	st := NewSegmentTree(data)

	// 1. Truy vấn tổng khoảng từ index 1 đến 4 (tương ứng các số: 3, 5, 7, 9)
	sum := st.Query(0, 0, st.n-1, 1, 4)
	fmt.Printf("Tổng khoảng [1, 4] ban đầu: %d\n", sum) // Kết quả: 3+5+7+9 = 24

	// 2. Cập nhật phần tử tại index 2 (đang là 5) thành 20
	fmt.Println("Cập nhật phần tử index 2 thành 20...")
	st.Update(0, 0, st.n-1, 2, 20)

	// 3. Truy vấn lại khoảng từ 1 đến 4 sau khi cập nhật
	sumAfterUpdate := st.Query(0, 0, st.n-1, 1, 4)
	fmt.Printf("Tổng khoảng [1, 4] sau khi cập nhật: %d\n", sumAfterUpdate) // Kết quả: 3+20+7+9 = 39
}

5. Ứng dụng thực tế và Mở rộng

Hệ thống phân tích thời gian thực (Real-time Analytics): Thống kê lượng truy cập website hoặc doanh thu theo các khung giờ tùy biến mà không cần tính lại từ đầu.
Đồ họa máy tính và Xử lý ảnh: Quản lý không gian lưới 2D (2D Segment Tree / QuadTree) để phát hiện va chạm hoặc tối ưu hóa truy vấn vùng hiển thị (Viewport Culling).
Mở rộng (Lazy Propagation): Khi bài toán yêu cầu cập nhật cả một khoảng thay vì chỉ một điểm đơn lẻ (ví dụ: Tăng tất cả các phần tử từ $L$ đến $R$ lên một lượng $X$ ), ta sử dụng kỹ thuật Lazy Propagation để hoãn việc cập nhật xuống các nút con, giữ vững độ phức tạp $O(\log N)$ .

Cây phân đoạn là cầu nối tuyệt vời đưa tư duy thuật toán của Hiếu tiến sâu hơn vào các cấu trúc dữ liệu hình cây nâng cao.

cấu trúc dữ liệu