Cây & Đồ thị

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

Cây & Đồ thị

Centroid Decomposition

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

Mô tả nguyên lý

Phân rã trọng tâm cây để giải quyết các bài toán đếm đường đi khoảng cách hoặc cây phân cấp.

Cài đặt mẫu (Implementation)

// Tìm tâm trọng tâm (centroid) của cây, chia nhỏ cây thành các bài toán con độc lập qua đệ quy.
Cây & Đồ thị

Heavy-Light Decomposition (HLD)

Thời gian (Time) O(log^2 N) mỗi truy vấn
Không gian (Space) O(N)

Mô tả nguyên lý

Phân rã cây thành các đường đi nặng/nhẹ để thực hiện truy vấn trên cây cực nhanh bằng Segment Tree.

Cài đặt mẫu (Implementation)

// Chia các cây con thành các chuỗi đường đi nặng để tối ưu hóa việc cập nhật và truy vấn đường đi trên cây.