Cây Đoạn (Segment Tree) là gì?

Cây Đoạn (Segment Tree) là một cấu trúc dữ liệu mạnh mẽ và rất hữu ích trong lập trình, đặc biệt là trong lập trình thi đấu. Nếu bạn đã bao giờ cảm thấy khó khăn với các bài toán liên quan đến mảng, cây đoạn sẽ là một giải pháp hiệu quả giúp bạn xử lý vấn đề một cách nhanh chóng và đơn giản.

Vườn Cây Ăn Quả - Minh Họa Cho Cây Đoạn

Hãy tưởng tượng bạn là một quản lý của một vườn cây ăn quả khổng lồ. Mỗi sáng, nhiệm vụ đầu tiên của bạn là đếm số lượng quả trên từng cây. Nhưng với hàng ngàn cây, bạn không thể dành cả ngày để đếm phải không? Để giải quyết, bạn quyết định tuyển một nhóm trợ lý. Mỗi người phụ trách đếm quả trong một khu vực nhỏ, và mỗi trợ lý đó lại có các phụ tá để giúp đỡ. Cuối cùng, bạn có một mạng lưới đếm quả cực kỳ hiệu quả. Chào mừng bạn đến với thế giới của Cây Đoạn!

Cấu Trúc của Cây Đoạn

Cây đoạn được xây dựng từ một mảng, và nó cho phép chúng ta thực hiện các thao tác trên mảng một cách nhanh chóng và hiệu quả. Cấu trúc của nó là một cây nhị phân, trong đó mỗi nút đại diện cho một đoạn (hoặc một khoảng) của mảng.

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

Quá trình xây dựng cây đoạn bao gồm việc chia mảng thành các đoạn nhỏ và gộp lại trên các nút của cây. Ví dụ, với mảng [2, 1, 5, 3, 4], cây đoạn sẽ được xây dựng như sau:

Mỗi phần tử của mảng trở thành một lá (leaf) của cây.
Mỗi nút (node) trong cây đại diện cho tổng (hoặc một giá trị cụ thể như min, max…) của hai con của nó.

Ví Dụ Cấu Trúc Cây Đoạn

Cho mảng [2, 1, 5, 3, 4], cây đoạn có thể được biểu diễn như sau:

Copy

          [15]
        /      \
     [8]        [7]
    /  \       /  \
  [3]  [5]   [3]  [4]
 /  \   |
[2] [1] [5]

Tại đây, nút gốc có tổng giá trị toàn bộ mảng là 15. Các nút con sẽ chứa tổng các đoạn nhỏ hơn.

Truy Vấn và Cập Nhật

Một trong những ưu điểm của cây đoạn chính là khả năng thực hiện các truy vấn và cập nhật một cách hiệu quả.

1. Truy Vấn Tổng (Sum Query)

Nếu bạn muốn biết tổng số quả từ cây số 2 đến cây số 4, bạn không cần đếm từng cây một. Chỉ cần hỏi cây đoạn, và nó sẽ trả lời ngay lập tức với thời gian phức tạp là O(log n).

2. Cập Nhật (Update)

Khi bạn phát hiện cây số 3 bỗng dưng ra thêm 10 quả, bạn chỉ cần báo cho cây đoạn mà thôi, và nó sẽ nhanh chóng cập nhật thông tin với cùng thời gian phức tạp là O(log n).

Ưu Điểm và Nhược Điểm của Cây Đoạn

Ưu Điểm:

Hiệu Suất Cao: Các thao tác truy vấn và cập nhật đều thực hiện trong O(log n).
Linh Hoạt: Có thể áp dụng cho nhiều loại bài toán như tính tổng, tìm giá trị nhỏ nhất/lớn nhất.
Dễ Cài Đặt: Mặc dù có vẻ phức tạp, nhưng việc cài đặt cây đoạn khá trực quan.

Nhược Điểm:

Tiêu Tốn Bộ Nhớ: Yêu cầu bộ nhớ lớn gấp 4 lần kích thước mảng ban đầu.
Khó Hiểu Cho Người Mới: Có thể khó hiểu cho người mới bắt đầu, cần thời gian để làm quen.
Không Thích Hợp cho Một Số Bài Toán: Đối với bài toán đơn giản, cây đoạn có thể là quá phức tạp.

Ứng Dụng Thực Tế của Cây Đoạn

Cây đoạn có nhiều ứng dụng thực tế trong lập trình:

Quản lý Mảng: Giúp quản lý hiệu quả các đoạn của mảng trong nhiều trường hợp.
Tính Tổng và Tìm Kiếm: Sử dụng để tính tổng, tìm giá trị lớn nhất/nhỏ nhất trong đoạn của mảng.
Ứng dụng trong Đồ Họa: Quản lý và tính toán các đoạn trong đồ họa.
Tối Ưu Hóa: Giúp tối ưu hóa các bài toán liên quan đến lập lịch và quản lý tài nguyên.

Cài Đặt Cây Đoạn Trong C++

Dưới đây là một đoạn mã C++ để cài đặt cây đoạn:

cpp Copy

#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
private:
    vector<int> tree;
    int n;

    void buildTree(vector<int>& arr, int treeIndex, int l, int r) {
        if (l == r) {
            tree[treeIndex] = arr[l];
            return;
        }
        int mid = l + (r - l) / 2;
        buildTree(arr, 2 * treeIndex + 1, l, mid);
        buildTree(arr, 2 * treeIndex + 2, mid + 1, r);
        tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
    }

    void updateTree(int treeIndex, int l, int r, int idx, int val) {
        if (l == r) {
            tree[treeIndex] = val;
            return;
        }
        int mid = l + (r - l) / 2;
        if (idx <= mid) {
            updateTree(2 * treeIndex + 1, l, mid, idx, val);
        } else {
            updateTree(2 * treeIndex + 2, mid + 1, r, idx, val);
        }
        tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
    }

    int queryTree(int treeIndex, int l, int r, int L, int R) {
        if (L > r || R < l) return 0;
        if (L <= l && R >= r) return tree[treeIndex];
        int mid = l + (r - l) / 2;
        return queryTree(2 * treeIndex + 1, l, mid, L, R) + queryTree(2 * treeIndex + 2, mid + 1, r, L, R);
    }

public:
    SegmentTree(vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        buildTree(arr, 0, 0, n - 1);
    }

    void update(int idx, int val) {
        updateTree(0, 0, n - 1, idx, val);
    }

    int query(int L, int R) {
        return queryTree(0, 0, n - 1, L, R);
    }
};

int main() {
    vector<int> arr = {2, 1, 5, 3, 4};
    SegmentTree segTree(arr);
    cout << "Sum of range(1, 3): " << segTree.query(1, 3) << endl;
    segTree.update(2, 10);
    cout << "Sum of range(1, 3) after update: " << segTree.query(1, 3) << endl;
    return 0;
}

Kết Luận

Cây đoạn là một giải pháp mạnh mẽ để xử lý các bài toán liên quan đến mảng. Với khả năng thực hiện các truy vấn và cập nhật trong O(log n), nó mang lại hiệu suất vượt trội so với các phương pháp đơn giản. Mặc dù yêu cầu bộ nhớ lớn và có thể phức tạp để triển khai, những lợi ích mà cây đoạn mang lại là rất đáng giá. Hãy thử nghiệm và áp dụng cây đoạn trong các bài toán của bạn để khám phá sức mạnh của nó!
source: viblo

Cây Đoạn (Segment Tree) - Cấu Trúc Dữ Liệu Hữu Ích trong Lập Trình