Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Trong chuyên đề này ta sẽ nhắc tới 2 loại cấu trúc đặc biệt , đó là Interval Tree và Binary Index Tree. Đó là 2 cách tổ chức dữ liệu rất thông minh , việc tổ chức này cũng dẫn tới việc tìm ra những thuật toán hay với cấp độ trung bình thấp O(NlogN) . Và để trình bày ý tưởng của các thuật toán này ta sẽ xem xét nó thông qua các bài toán cụ thể để có thể hiểu rõ hơn. | Chuyên đề cấu trúc dữ liệu đặc biệt Nguyễn Minh Hiếu CHUYÊN ĐỀ CẤU TRÚC DỮ LIỆU ĐẶC BIỆT A . Lý thuyết Trong chuyên đề này ta sẽ nhắc tới 2 loại cấu trúc đặc biệt đó là Interval Tree và Binary Index Tree. Đó là 2 cách tổ chức dữ liệu rất thông minh việc tổ chức này cũng dẫn tới việc tìm ra những thuật toán hay với cấp độ trung bình thấp O NlogN . Và để trình bày ý tưởng của các thuật toán này ta sẽ xem xét nó thông qua các bài toán cụ thể để có thể hiểu rõ hơn. I . Interval Tree Bài toán Cho N hình chữ nhật trong mặt phẳng toạ độ. Hãy tính diện tích bị phủ bởi N hình chữ nhật này. Giới hạn 1 N 2000. Các toạ độ đều là số nguyên . Time limit 0.5 s bộ nhớ 200 KB. Phân tích Đối với bài toán này ta có thể giải bằng giải thuật thông thường với cấp độ O N2 . Đó là sắp xếp các hình chữ nhật theo toạ độ Y sau đó tính diện tích bị phủ giữa 2 khe. Tổng diện tích bị phủ sẽ là tổng diện tích bị phủ giữa 2 khe H.1 . C1 C2 C3 C4 C5 C6 C7 C8 B1 B2 B3 B4 B5 B6 B7 B8 Hình 1 Ở hình 1 ta thấy có các khe B1B2 B2B3 . B7B8. Vì đã sắp xếp các HCN tăng dần theo tung độ nên với mỗi khe ta chỉ cần thao tác đơn giản là xét từ 1 - N những HCN nào phủ lên khe đó mà thôi. Có tất cả khoảng N 2 - 1 khe với mỗi khe ta xét N HCN - Cấp độ chính xác O 2 N2 . Rõ ràng với N 2000 thì trong vòng 0.5 s chương trình khó có thể trả ra kết quả ngay được. Trang 1 Chuyên đề cấu trúc dữ liệu đặc biệt Nguyễn Minh Hiếu Chắc hẳn rất nhiều bạn cũng sẽ nghĩ ra thuật toán này và có thể sẽ băn khoăn một điều rằng liệu có cách gì để chỉ xét mỗi hình chữ nhật đúng một lần hay không Cấu trả lời là nếu muốn chỉ xét 1 lần thì hiện thời mình cũng không biết nhưng mà mình biết có thuật toán có thể đáp ứng yêu cầu với số lần xét là 2 lần Nội dung thuật toán và cách làm Nếu như ở thuật toán O N2 ta chỉ xét các khe theo hoành độ các khe B thì ở đây ta lại quan tâm tới khe theo tung độ các khe C . Tuy nhiên về mặt bản chất thuật toán vẫn không có gì thay đổi vẫn chỉ là tính diện tích giữa các khe hoành độ mà thôi. Ta sẽ phân tách
