I. Giới thiệu về Cây Phân Đoạn

Cây phân đoạn (Segment Tree) là một cấu trúc dữ liệu rất hữu ích trong lập trình, đặc biệt là trong các bài toán về truy vấn đoạn (range query). Nó cho phép chúng ta thực hiện các truy vấn tìm kiếm hoặc cập nhật dữ liệu trong một mảng một cách hiệu quả. Bài viết này sẽ tập trung vào việc hướng dẫn bạn về cách sử dụng cây phân đoạn, đặc biệt là cho bài toán tìm phần tử nhỏ nhất trong một đoạn (RMQ).

1. Tại Sao Nên Sử Dụng Cây Phân Đoạn?

Cây phân đoạn rất cần thiết trong các bài toán cần truy vấn hoặc cập nhật dữ liệu nhiều lần mà không muốn duyệt qua toàn bộ mảng mỗi lần. Ví dụ điển hình là bài toán RMQ: bạn cần trả lời câu hỏi về chỉ số của phần tử nhỏ nhất trong đoạn A[i,j]. Với dãy số A = [18, 17, 13, 19, 15, 11, 20], bạn có thể dễ dàng tìm thấy RMQ(1,3) = 3.

2. Các Loại Truy Vấn

Trong bài viết này, chúng ta sẽ làm quen với hai loại truy vấn:

• Truy vấn cập nhật: Gán giá trị cho phần tử tại chỉ số x.
• Truy vấn tìm kiếm: Tìm giá trị nhỏ nhất trong đoạn từ l đến r.

3. Cấu trúc Cây Phân Đoạn

Cây phân đoạn được tổ chức dưới dạng cây nhị phân, mỗi nút chứa thông tin cho một đoạn của mảng. Nút gốc quản lý toàn bộ dãy số, trong khi các nút con quản lý các đoạn con.

4. Cách Xây Dựng Cây Phân Đoạn

Chúng ta có thể xây dựng cây phân đoạn theo phương pháp đệ quy. Bạn sẽ bắt đầu từ nút gốc và chia mảng thành hai nửa cho đến khi đạt tới các nút lá. Mỗi nút lá sẽ chứa giá trị của một phần tử trong mảng.

5. Cập Nhật và Truy Vấn Dữ Liệu

Khi cần cập nhật phần tử trong mảng, chỉ cần cập nhật nút lá tương ứng và sau đó cập nhật lại giá trị cho các nút cha. Đối với truy vấn tìm kiếm, chúng ta sẽ tìm kiếm trên các nút có giao nhau với đoạn cần tìm, và từ đó tính toán giá trị nhỏ nhất.

6. Mã Nguồn Cơ Bản

#include <bits/stdc++.h>
using namespace std;

void build_tree(int id, int l, int r, vector<int> &st, vector<int> &a) {
    // ...
}

void update(int id, int l, int r, int i, int val, vector<int> &st) {
    // ...
}

int get(int id, int l, int r, int u, int v, vector<int> &st) {
    // ...
}

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    // ...
}

II. Đánh Giá Hiệu Suất

1. Tối Ưu Bộ Nhớ

Cây phân đoạn có thể được lưu trữ hiệu quả trong một mảng với không gian gần 4*n.

2. Thời Gian Thực Hiện

Thao tác xây dựng cây mất O(n), trong khi các truy vấn và cập nhật chỉ yêu cầu O(log n) thời gian, làm cho cây phân đoạn trở thành một giải pháp tối ưu cho nhiều bài toán.

III. Kết Luận

Cây phân đoạn là một công cụ mạnh mẽ trong lập trình để xử lý các truy vấn trên dãy số. Người đọc có thể tiếp tục tìm hiểu thêm về các ứng dụng khác cũng như cải tiến của cấu trúc dữ liệu này trong các bài viết tiếp theo.

source: viblo