tailieunhanh - Các cấu trúc dữ liệu nâng cao cho bài toán truy vấn vùng

Bài viết này trình bày về nội dung của bài toán truy vấn vùng và xây dựng một cấu trúc dữ liệu về cây phân đoạn nhằm đưa ra phương án giải cho một lớp các bài toán cùng dạng. Với cấu trúc xây dựng ở trong bài viết này người đọc dễ dàng áp dụng để giải được một lớp các bài toán cùng dạng và dễ dàng được chấp nhận trên các trang thi trực tuyến. | TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học – Đại học Huế Tập 5, Số 1 (2016) CÁC CẤU TRÚC DỮ LIỆU NÂNG CAO CHO BÀI TOÁN TRUY VẤN VÙNG Trần Việt Khoa Khoa Công nghệ Thông tin, Trường Đại học Khoa học – Đại học Huế Email: TÓM TẮT Lập trình cạnh tranh là một môn thi trí tuệ về lập trình thường được tổ chức trên Internet hay trên mạng nội bộ, thí sinh tham gia cố gắng để viết chương trình giải quyết công việc theo yêu cầu cho trước. Các trường đại học, các hội tin học khác nhau trên thế giới đều chọn phương thức này để tạo sân chơi cho học sinh, sinh viên về kỹ năng lập trình. Bài toán truy vấn vùng là một bài toán thường xuyên gặp trong các kỳ thi lập trình cạnh tranh. Bài toán này được giải với nhiều phương pháp khác nhau, tuy nhiên lời giải tốt nhất chính là sử dụng các cấu trúc dữ liệu như cây phân đoạn, cây nhị phân chỉ mục. Bài báo này trình bày nội dung chính về cây phân đoạn cũng như cách áp dụng nó để giải một số bài toán cùng dạng trong các kỳ thi Olympic tin học. Hơn nữa, nội dung trên cũng là kiến thức bổ sung cho sinh viên, học viên cao học trong phần phân tích và thiết kế thuật toán. Từ khóa: Cây phân khoảng, Cây phân đoạn, Cây chỉ mục nhị phân. 1. GIỚI THIỆU Bài toán truy vấn vùng là một bài toán thường xuyên gặp trong các kỳ thi lập trình cạnh tranh. Bài toán này được giải với nhiều phương pháp khác nhau, tuy nhiên lời giải tốt nhất cho bài toán này chính là sử dụng các cấu trúc dữ liệu như cây phân đoạn, cây nhị phân chỉ mục. Bài toán này trước đây được giải bằng cấu trúc cây phân khoảng (Interval Tree) [3] tuy nhiên việc cài đặt tương đối phức tạp vì đó là một cấu trúc động. Cây phân đoạn (Segment Tree) giải quyết bài toán trên tốt hơn về mặt cài đặt. Nội dung của cấu trúc dữ liệu cây phân đoạn bằng tiếng Việt không nhiều, chưa phổ biến, và cũng không được trình bày trong các giáo trình về cấu trúc dữ liệu và giải thuật, giáo trình về phân tích và thiết kế thuật toán [1, 2, 3]. Các tài liệu nước ngoài đối với phần .