vi
new
+10
Avatar
Lâm Phú Cường @cuonglamphu
271 9 5
Đã đăng vào thg 7 17, 6:56 SA 10 phút đọc
497

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à cực kỳ hữu ích trong lập trình nói chung cũng như lập trình thi đấu nói riêng. Nếu bạn từng cảm thấy bối rối với các bài toán về mảng và cần một công cụ hiệu quả để giải quyết chúng, thì cây đoạn chính là một giải pháp tốt. image.png

Vườn cây ăn quả !

Hãy tưởng tượng bạn là một người quản lý vườn cây ăn quả khổng lồ. Mỗi sáng thức dậy, việc đầu tiên của bạn là đếm xem có bao nhiêu quả trên từng cây. Nhưng vườn của bạn có hàng ngàn cây! Chắc chắn bạn không muốn trở thành một "kẻ đếm quả" cả ngày, phải không? image.png Vì vậy, bạn quyết định tuyển một nhóm trợ lý, mỗi người chịu trách nhiệm đếm quả ở một phần nhỏ của vườn. Những trợ lý này lại thuê thêm các phụ tá, mỗi người chỉ cần đếm số quả trên vài cây. Kết quả cuối cùng là bạn có một mạng lưới đếm quả siêu 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, nhưng nó giúp chúng ta thực hiện các thao tác trên mảng một cách nhanh chóng. Cây đoạ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.

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ỏ hơn và gộp lại trong 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:

  1. Mỗi phần tử của mảng là một lá (leaf) của cây.
  2. Mỗi nút (node) trong cây là tổng (hoặc một giá trị nào đó tùy bài toán, ví dụ như min, max,…) của hai con của nó.

Ví dụ, cây đoạn cho mảng [2, 1, 5, 3, 4] có thể trông như sau:


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

Mỗi nút chứa tổng giá trị của đoạn mà nó đại diện. Ví dụ, nút gốc chứa tổng giá trị của toàn bộ mảng [2, 1, 5, 3, 4] là 15. Các nút con chứa tổng giá trị của các đoạn con.

Truy vấn và Cập nhật

Một trong những sức mạnh của cây đoạn 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ả.

Truy vấn tổng (Sum Query):

Hãy tưởng tượng bạn muốn biết tổng số quả trên cây từ cây số 2 đến cây số 4. Thay vì phải tự mình đếm từng cây, bạn chỉ cần hỏi các trợ lý của mình, và họ sẽ cho bạn câu trả lời chỉ trong tích tắc. Điều này giống như bạn chỉ cần hỏi cây đoạn, và nó sẽ trả lời bạn với thời gian phức tạp là O(log⁡n).

Cập nhật (Update):

Một ngày đẹp trời, bạn phát hiện ra rằng cây số 3 bỗng dưng ra thêm 10 quả. Bạn không cần phải cập nhật thủ công số quả trên từng cây một; bạn chỉ cần báo với cây đoạn, và nó sẽ nhanh chóng cập nhật thông tin giúp bạn, cũng với 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:

  1. Hiệu Suất Cao: Với cây đoạn, các thao tác truy vấn và cập nhật đều có thời gian phức tạp là O(logn), rất hiệu quả so với các phương pháp đơn giản như duyệt toàn bộ mảng.
  2. Linh Hoạt: Cây đoạn có thể được sử dụng để giải quyết nhiều loại bài toán khác nhau, từ tính tổng, tìm giá trị nhỏ nhất/lớn nhất đến các bài toán phức tạp hơn như tìm kiếm.
  3. Dễ Cài Đặt: Dù cấu trúc có vẻ phức tạp, nhưng việc cài đặt cây đoạn khá trực quan và dễ hiểu với các bước xây dựng rõ ràng.

Nhược Điểm:

  1. Tiêu Tốn Bộ Nhớ: Cây đoạn yêu cầu bộ nhớ gấp 4 lần kích thước của mảng ban đầu, điều này có thể là vấn đề khi làm việc với các mảng rất lớn.
  2. Khó Hiểu Cho Người Mới: Đối với những người mới bắt đầu, cây đoạn có thể khá khó hiểu và cần một chút thời gian để làm quen.
  3. Không Thích Hợp cho Một Số Bài Toán: Với một số bài toán đơn giản, cây đoạn có thể là quá phức tạp và không cần thiết, cho nên hãy cân nhắc khi sử dụng segment tree cho các bài toán đơn giản.

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

Cây đoạn có rất nhiều ứng dụng thực tế trong lập trình và giải quyết các bài toán cụ thể:

  1. Quản lý Mảng: Cây đoạn giúp quản lý các đoạn của mảng một cách hiệu quả, đặc biệt trong các bài toán yêu cầu truy vấn và cập nhật liên tục.
  2. Tính Tổng và Tìm Kiếm: Cây đoạn có thể được sử dụng để tính tổng, tìm giá trị lớn nhất, nhỏ nhất trong một đoạn của mảng, rất hữu ích trong các bài toán liên quan đến thống kê và phân tích dữ liệu.
  3. Ứng dụng trong Đồ Họa: Trong các ứng dụng đồ họa, cây đoạn có thể được sử dụng để quản lý và tính toán các đoạn của ảnh hoặc các đối tượng hình học.
  4. Tối Ưu Hóa: Cây đoạn giúp tối ưu hóa các bài toán liên quan đến lập lịch, quản lý tài nguyên, và các bài toán liên quan đến chuỗi, mảng, và dữ liệu.

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:


#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;
}

Ví Dụ Minh Họa

Giả sử chúng ta có mảng [2, 1, 5, 3, 4] và muốn xây dựng cây đoạn cho mảng này. Dưới đây là cách cây đoạn được biểu diễn và các bước để xây dựng nó:

Bước 1: Khởi tạo cây

Khởi tạo một mảng tree có kích thước gấp 4 lần kích thước của mảng ban đầu để đảm bảo đủ không gian lưu trữ các giá trị của cây đoạn.

vector<int> tree(4 * n);

Bước 2: Gọi hàm đệ quy để xây dựng cây

void buildTree(vector<int>& arr, int treeIndex, int l, int r) {
    if (l == r) { // Base case: nếu l và r bằng nhau, tức là chỉ có một phần tử
        tree[treeIndex] = arr[l];
        return;
    }
    int mid = l + (r - l) / 2; // Tính chỉ số giữa (mid)
    buildTree(arr, 2 * treeIndex + 1, l, mid); // Xây dựng cây con trái
    buildTree(arr, 2 * treeIndex + 2, mid + 1, r); // Xây dựng cây con phải
    tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2]; // Gộp giá trị của cây con trái và phải
}

Ví dụ từng bước

  1. Gốc cây (treeIndex = 0): Đoạn [2, 1, 5, 3, 4] có tổng là 15.
  2. Chia đoạn thành hai nửa:
    • Nửa trái [2, 1, 5] với tổng 8 (treeIndex = 1).
    • Nửa phải [3, 4] với tổng 7 (treeIndex = 2).
  3. Chia tiếp các đoạn:
    • Đoạn [2, 1, 5] chia thành [2, 1] với tổng 3 (treeIndex = 3) và [5] với tổng 5 (treeIndex = 4).
    • Đoạn [3, 4] chia thành [3] với tổng 3 (treeIndex = 5) và [4] với tổng 4 (treeIndex = 6).

⇒ Kết quả:

Dưới dạng mảng, cây đoạn có thể được biểu diễn như sau:

tree = [15, 8, 7, 3, 5, 3, 4, 2, 1
  • tree[0] = 15 (tổng toàn bộ mảng)
  • tree[1] = 8 (tổng đoạn [2, 1, 5])
  • tree[2] = 7 (tổng đoạn [3, 4])
  • tree[3] = 3 (tổng đoạn [2, 1])
  • tree[4] = 5 (giá trị phần tử 5)
  • tree[5] = 3 (giá trị phần tử 3)
  • tree[6] = 4 (giá trị phần tử 4)
  • tree[7] = 2 (giá trị phần tử 2)
  • tree[8] = 1 (giá trị phần tử 1)

Kết Luận

Cây đoạn là một cấu trúc dữ liệu mạnh mẽ giúp giải quyết các bài toán liên quan đến mảng một cách hiệu quả. Với cây đoạn, bạn có thể thực hiện các truy vấn và cập nhật trên mảng với thời gian phức tạp là O(logn). Điều này cực kỳ hữu ích trong các bài toán yêu cầu thao tác nhiều lần trên mảng, chẳng hạn như tính tổng các phần tử trong một đoạn, tìm giá trị lớn nhất hoặc nhỏ nhất trong một đoạn, và nhiều ứng dụng khác. Dù cây đoạn yêu cầu một lượng bộ nhớ lớn hơn và có thể phức tạp hơn để triển khai, nhưng lợi ích mà nó mang lại là rất đáng kể. Hãy thử áp dụng cây đoạn vào các bài toán của bạn để thấy rõ sức mạnh của nó!

Data Structure Algorithm C/Cpp Lập trình thi đấu segment tree

All rights reserved

Mục lục


Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí