Tài liệu Cách sử dụng interval tree, binary indexed tree

Mô tả:

CÁCH SỬ DỤNG INTERVAL TREE, BINARY INDEXED TREE QUA MỘT SỐ BÀI TOÁN QUI HOẠCH ĐỘNG Cấu trúc dữ liệu (CTDL) là thành tố quan trọng để đưa ra được một giải thuật có hiệu quả. Trong những năm gần đây, khi giới hạn về bộ nhớ không còn là rào cản cho các bài tập tin học thì các bài toán với kích thước dữ liệu lớn xuất hiện phổ biến trong các kỳ thi. Để có được một chương trình hiệu quả (đo bằng tốc độ tính toán) khi giải các bài tập như vậy, việc sử dụng các CTDL để lưu trữ thông tin là một điều kiện tiên quyết. Có nhiều loại CTDL khác nhau. Tuy nhiên đối với mức độ khó của các bài thi cấp quốc gia có thể kể đến các CTDL sau: 1. Ngăn xếp (stack) 2. Hàng đợi hai đầu (double queue) 3. Đống (heap) 4. RMQ (Range Minimum Query) 5. IT (Interval Tree) 6. BIT (Binarry Indexed Tree) Trong chuyên đề này, tôi không có ý định trình bày lại các CTDL nói trên. Trình bày chi tiết về chủ đề này đã được thầy Lê Minh Hoàng trình bày trong các chuyên đề bồi dưỡng giáo viên chuyên cũng như trong sách giáo khoa chuyên tin (Tập 2). Ở đây, tôi chỉ dừng lại ở việc phân tích cách sử dụng hai cấu trúc IT và BIT khi giải một số bài toán quy hoạch động. Qua đó khái quát hóa một số nguyên lý chung (theo đánh giá chủ quan của tôi) trong việc áp dụng các cấu trúc này.