Tổng quan
Cây phân đoạn (Segment Tree) là một cây nhị phân của các giá trị gộp theo khoảng, trả lời truy vấn khoảng — như tổng trên một đoạn con của mảng — và thực hiện cập nhật điểm, cả hai trong thời gian logarit. Mỗi nút lưu giá trị gộp của một đoạn liên tục của mảng.
Gốc bao trùm toàn mảng; mỗi nút chia khoảng của nó thành hai nửa do các con xử lý, cho đến các lá chứa một phần tử. Nhờ đó một truy vấn có thể phủ mọi khoảng bằng cách gộp O(log n) đoạn đã tính sẵn.
Cây phân đoạn hoạt động thế nào?
- Xây đệ quy: giá trị mỗi nút trong là tổng giá trị của hai con của nó.
- Truy vấn tổng khoảng đi xuống từ gốc, lấy trọn các nút nằm hẳn trong khoảng và chia đôi những nút cắt ngang.
- Cập nhật điểm thay đổi một lá, rồi đi ngược lên tính lại giá trị gộp của từng tổ tiên.
- Vì mỗi truy vấn hay cập nhật chạm tối đa hai nút mỗi tầng, công việc là O(log n).
Khi nào nên dùng?
- Truy vấn tổng-khoảng, nhỏ-nhất-khoảng, hay lớn-nhất-khoảng trên một mảng thay đổi được.
- Các bài lập trình thi đấu trộn lẫn nhiều cập nhật với nhiều truy vấn khoảng.
- Ghi sổ theo khoảng như thống kê tích lũy, biểu đồ tần suất, và đếm tần suất theo khoảng.
Phân tích độ phức tạp
Xây cây tốn O(n), còn mỗi truy vấn khoảng và mỗi cập nhật điểm là O(log n). Cấu trúc dùng O(n) bộ nhớ (thường là một mảng phẳng khoảng 2n–4n nút). Cập nhật khoảng cũng có thể đạt O(log n) nhờ lan truyền lười (lazy propagation).
Câu hỏi thường gặp
Khi nào nên dùng cây phân đoạn thay cho mảng tổng tiền tố?
Mảng tổng tiền tố trả lời tổng khoảng trong O(1) nhưng cần O(n) để xây lại sau mỗi cập nhật. Cây phân đoạn giữ cả truy vấn lẫn cập nhật ở O(log n), nên thắng thế khi dữ liệu thay đổi thường xuyên.
Lan truyền lười là gì?
Nó trì hoãn các cập nhật áp cho cả một khoảng bằng cách lưu một giá trị chờ tại nút và chỉ đẩy xuống khi cần, giúp cập nhật khoảng chạy O(log n) thay vì O(n).