Cấu trúc dữ liệu nâng cao

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 5)

Cấu trúc dữ liệu nâng cao

Implicit Treap

Thời gian (Time) O(log N)
Không gian (Space) O(N)

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.
Cấu trúc dữ liệu nâng cao

Link-Cut Tree

Thời gian (Time) O(log N) amortized
Không gian (Space) O(N)

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).
Cấu trúc dữ liệu nâng cao

Persistent Segment Tree

Thời gian (Time) O(log N) mỗi phiên bản
Không gian (Space) O(N log N)

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.
Cấu trúc dữ liệu nâng cao

Splay Tree

Thời gian (Time) O(log N) amortized
Không gian (Space) O(N)

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.
Cấu trúc dữ liệu nâng cao

Wavelet Tree

Thời gian (Time) O(log Sigma)
Không gian (Space) O(N log Sigma)

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.