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