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

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.