Implicit Treap
Mô tả nguyên lý
Treap ngầm định lưu trữ vị trí mảng qua kích thước cây con, hỗ trợ đảo đoạn, cắt nối mảng.
Cài đặt mẫu (Implementation)
// Kết hợp BST và Heap dựa trên trọng số ngẫu nhiên không cần khóa tường minh.
Link-Cut Tree
Mô tả nguyên lý
Cấu trúc dữ liệu động quản lý rừng cây, hỗ trợ thêm/xóa cạnh và truy vấn đường đi nhanh chóng.
Cài đặt mẫu (Implementation)
// Dựa trên cấu trúc Splay Tree để quản lý các đường đi ưu tiên (preferred paths).
Persistent Segment Tree
Mô tả nguyên lý
Cây phân đoạn lưu trữ toàn bộ lịch sử các phiên bản thay đổi dữ liệu theo thời gian.
Cài đặt mẫu (Implementation)
// Mỗi lần cập nhật chỉ tạo mới các node trên đường đi thay vì sao chép toàn bộ cây.
Splay Tree
Mô tả nguyên lý
Cây nhị phân tự cân bằng đưa nút vừa truy cập lên gốc thông qua các phép xoay liên tục (splay operation).
Cài đặt mẫu (Implementation)
// Tự động tối ưu hóa các nút thường xuyên truy cập gần gốc để tăng tốc độ truy xuất.
Wavelet Tree
Mô tả nguyên lý
Cấu trúc dữ liệu nén mạnh mẽ hỗ trợ truy vấn tần suất, chọn lọc và thống kê trên mảng.
Cài đặt mẫu (Implementation)
// Phân chia bảng chữ cái thành hai nửa tại mỗi tầng cây để lưu trữ các bit vector.