Cấu trúc dữ liệu và Giải thuật Bài 58: Cây Phân Đoạn (Segment Tree) - Xử lý truy vấn khoảng dữ liệu (Range Queries) siêu tốc.

Bước sang Chương 12 với các cấu trúc dữ liệu nâng cao, chúng ta đối mặt với một bài toán kinh điển trong các hệ thống phân tích dữ liệu thời gian thực (Real-time Analytics) và giám sát hạ tầng: Range Query (Truy vấn khoảng dữ liệu).

Giả sử bạn đang quản lý hàng triệu bản ghi doanh số theo thời gian thực tại Hasaki. Hệ thống cần liên tục thực hiện 2 thao tác với tần suất cực cao:

1. Update (Cập nhật): Thay đổi doanh số của một mốc thời gian cụ thể khi có đơn hàng mới phát sinh.

2. Range Query (Truy vấn khoảng): Tính tổng (hoặc tìm giá trị lớn nhất/nhỏ nhất) doanh số trong một khoảng thời gian bất kỳ (ví dụ: từ phút thứ 100 đến phút thứ 500,000).

Nếu dùng Mảng tĩnh (Array): Cập nhật mất $O(1)$, nhưng truy vấn tổng khoảng phải quét qua toàn bộ mảng mất $O(n)$.

Nếu dùng Mảng cộng dồn (Prefix Sum Array): Truy vấn tổng khoảng siêu tốc $O(1)$, nhưng mỗi khi có một giá trị bị thay đổi (Update), bạn phải tính lại toàn bộ mảng cộng dồn mất $O(n)$.

Khi cả hai thao tác Read và Write đều diễn ra với tần suất hàng vạn lần mỗi giây, cả hai cách tiếp cận trên đều sụp đổ. Để đạt được tốc độ $O(\log n)$ cho cả hai thao tác Update và Range Query, chúng ta cần đến một trong những cấu trúc dữ liệu cây mạnh mẽ nhất: Cây Phân Đoạn (Segment Tree).

1. Giải phẫu Cây Phân Đoạn (Segment Tree)

Segment Tree là một Cây nhị phân hoàn chỉnh (Complete Binary Tree), trong đó mỗi Node đại diện cho một đoạn (segment / interval) [L, R] của mảng ban đầu.

• Node Gốc (Root): Đại diện cho toàn bộ mảng từ phần tử đầu tiên đến phần tử cuối cùng [0, n - 1].

• Các Node con: Một đoạn [L, R] sẽ được chia đôi thành hai nhánh con: Nhánh trái đại diện cho [L, Mid] và nhánh phải đại diện cho [Mid + 1, R] (với Mid = (L + R) / 2).

• Các Node lá (Leaf Nodes): Đại diện cho từng phần tử đơn lẻ [i, i] của mảng gốc.

Tính chất phân cấp:

Nếu bạn cần tính tổng của một khoảng bất kỳ [Q_Left, Q_Right], thay vì duyệt qua từng phần tử, Segment Tree cho phép bạn "cắt" khoảng đó thành một số ít các Node đoạn có sẵn trên cây, cộng dồn chúng lại với độ sâu tối đa chỉ là $\log_2(n)$.

2. Triển khai Segment Tree (Range Sum & Point Update) bằng Golang

Dưới đây là thiết kế chuẩn mực của một Segment Tree thực hiện bài toán Tính tổng khoảng (Range Sum Query) và Cập nhật điểm (Point Update):

Go

package main

import "fmt"

type SegmentTree struct {
    tree   []int
    n      int
}

// Khởi tạo và xây dựng Segment Tree từ mảng gốc
func NewSegmentTree(nums []int) *SegmentTree {
    n := len(nums)
    tree := make([]int, 4*n) // Cần dung lượng gấp 4 lần mảng gốc để an toàn
    st := &SegmentTree{tree: tree, n: n}
    st.build(nums, 0, 0, n-1)
    return st
}

// 1. Hàm đệ quy xây dựng cây (Build Tree) - Độ phức tạp: O(n)
func (st *SegmentTree) build(nums []int, node, start, end int) {
    if start == end {
        st.tree[node] = nums[start]
        return
    }
    mid := (start + end) / 2
    leftNode := 2*node + 1
    rightNode := 2*node + 2

    st.build(nums, leftNode, start, mid)
    st.build(nums, rightNode, mid+1, end)
    
    // Giá trị của node cha bằng tổng hai node con
    st.tree[node] = st.tree[leftNode] + st.tree[rightNode]
}

// 2. Truy vấn khoảng [L, R] (Range Query) - Độ phức tạp: O(log n)
func (st *SegmentTree) Query(l, r int) int {
    return st.queryRange(0, 0, st.n-1, l, r)
}

func (st *SegmentTree) queryRange(node, start, end, l, r int) int {
    // Trường hợp 1: Khoảng cần tìm nằm ngoài hoàn toàn đoạn hiện tại
    if r < start || end < l {
        return 0
    }
    // Trường hợp 2: Đoạn hiện tại nằm hoàn toàn bên trong khoảng cần tìm
    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.queryRange(2*node+1, start, mid, l, r)
    p2 := st.queryRange(2*node+2, mid+1, end, l, r)
    return p1 + p2
}

// 3. Cập nhật giá trị tại một vị trí (Point Update) - Độ phức tạp: O(log n)
func (st *SegmentTree) Update(index, val int) {
    st.updateVal(0, 0, st.n-1, index, val)
}

func (st *SegmentTree) updateVal(node, start, end, idx, val int) {
    if start == end {
        st.tree[node] = val
        return
    }
    mid := (start + end) / 2
    if idx <= mid {
        st.updateVal(2*node+1, start, mid, idx, val)
    } else {
        st.updateVal(2*node+2, mid+1, end, idx, val)
    }
    // Cập nhật lại giá trị node cha trên đường đi quay về gốc
    st.tree[node] = st.tree[2*node+1] + st.tree[2*node+2]
}

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

• Không gian RAM: $O(n)$ (thường cấp phát mảng có kích thước $4n$ để đảm bảo chứa đủ các node của cây nhị phân hoàn chỉnh).

• Thời gian Xây dựng (Build): $O(n)$

• Thời gian Truy vấn (Query): $O(\log n)$. Thay vì duyệt qua hàng triệu phần tử, cây chỉ ghé thăm các nhánh phân đoạn tương ứng với chiều cao $h \approx \log_2(n)$.

• Thời gian Cập nhật (Update): $O(\log n)$. Chỉ các node nằm trên đường đi từ nút lá lên đến gốc mới cần tính toán lại giá trị tổng.

4. Ứng dụng Thực tế trong Hệ thống Lớn

Segment Tree không chỉ là lý thuyết thuật toán, nó là công cụ đắc lực giải quyết các bài toán kỹ thuật phức tạp:

• Hệ thống Dashboard Giám sát thời gian thực (Metrics & Monitoring): Các hệ thống như Prometheus hoặc Datadog khi xử lý các chuỗi thời gian (Time-series data) để vẽ biểu đồ tổng lưu lượng request (Requests per Second) trong các khoảng thời gian tùy chỉnh (Zoom in/out biểu đồ) đều sử dụng các biến thể của Segment Tree để tính toán cực nhanh mà không làm nghẽn CPU.

• Hệ thống OLAP và Báo cáo Tài chính: Cho phép truy vấn tổng doanh thu, lợi nhuận hoặc tồn kho theo bất kỳ dải thời gian nào (từ ngày X đến ngày Y) ngay lập tức dù cơ sở dữ liệu có hàng tỷ bản ghi giao dịch.

Tuy nhiên, Segment Tree cơ bản vẫn có giới hạn: Nếu bài toán yêu cầu cập nhật giá trị cho cả một khoảng lớn cùng một lúc (Range Update, ví dụ: tăng tất cả các phần tử từ vị trí 1 triệu lên vị trí 2 triệu thêm 10 đơn vị), việc cập nhật từng phần tử một sẽ làm mất thời gian $O(n \log n)$. Để giải quyết điểm yếu này, các kỹ sư phải nâng cấp cấu trúc với một kỹ thuật gọi là Lazy Propagation.