06.1 - Segment Tree

Giới thiệu

Cây phân đoạn là cấu trúc dữ liệu cho phép thực hiện các truy vấn đoạn trên mảng một cách hiệu quả, trong khi vẫn cho phép sửa đổi mảng. Các bài toán có thể giải quyết được có thể bao gồm: Tính tổng các phần tử liên tiếp trong một đoạn [l,r]. Hoặc tìm phần tử lớn nhất, nhỏ nhất trong một đoạn như vậy với độ phức tạp O(logn). Giữa lúc trả lời các câu hỏi như vậy, cây phân đoạn cũng cho phép thay đổi mảng với các thao tác như thay đổi giá trị của một phần tử hoặc thậm chí thay đổi giá trị của cả một đoạn (Ví dụ như gán một  giá trị của đoạn [l,r], hoặc cộng thêm vào các phần tử trong đoạn [l,r] một giá trị nào đó).

Nói chung, cây phân đoạn là một cấu trúc dữ liệu linh động và có thể giải quyết được rất nhiều bài toán. Ngoài ra, cũng có thể áp dụng cấu trúc cây phân đoạn để trả lời được các câu hỏi phức tạp hơn là việc tìm tổng, tìm giá trị lớn nhất, nhỏ nhất trong một đoạn. Đặc biệt, cây phân đoạn cũng có thể được tổng quát hóa thành cây phân đoạn có cấu trúc phức tạp hơn với dữ liệu lớn hơn. Ví dụ, cây phân đoạn hai chiều, ta có thể giải các bài toán tính tổng hoặc tìm min, max trên một phần con của một mảng hai chiều nhất định chỉ với chi phí về mặt thời gian là O(log2n).

Một tính chất quan trọng của cây phân đoạn đó là chỉ cần bộ nhớ tuyến tính, nó chỉ cần 4n đỉnh để thể hiện được mảng có kích thước n. 

Các phần lý thuyết nền tảng về cây phân đoạn (segment tree) các em đọc trong các tài liệu tham khảo được dẫn dưới đây. Trong mục này chúng ta chủ yếu thảo luận sâu qua các bài tập để thấy được ứng dụng của cây phân đoạn.

(Nguồn: chuyên đề duyên hải Bắc Bộ 2021)

Tài liệu tham khảo

CP - Algorithm - Segment tree

VNOI - Cây phân đoạn

Competitive Programming 4, Book 1, Chaper 2

Tài liệu chuyên đề hội thảo Duyên Hải Bắc Bộ 2021

Thảo luận bài tập

Nhiệm vụ 1.1 -  Truy vấn hình vuông  - Duyên hải Bắc Bộ 2021

Nhiệm vụ 1.2 - Knight Tournament  - Codeforce Round #207 - A

Nhiệm vụ 1.3 - UVa 11402 - Ahoy, Pirates

Nhiệm vụ 1.4. Xenia and Bit Operations - Codeforce Round #197 - D

Nhiệm vụ 1.5. Xor on Segment - Codeforce Round #149 - E