Truy vấn giá trị nhỏ nhất trong đoạn (Range Minimum Query)¶
Bạn được cho một mảng $A[1..N]$. Bạn phải trả lời các truy vấn đến có dạng $(L, R)$, yêu cầu tìm phần tử nhỏ nhất trong mảng $A$ giữa các vị trí $L$ và $R$.
RMQ có thể xuất hiện trực tiếp trong các bài toán hoặc có thể được áp dụng trong một số nhiệm vụ khác, ví dụ: bài toán Tổ tiên chung thấp nhất (Lowest Common Ancestor).
Giải pháp (Solution)¶
Có rất nhiều cách tiếp cận và cấu trúc dữ liệu có thể mà bạn có thể sử dụng để giải quyết tác vụ RMQ.
Những cái được giải thích trên trang web này được liệt kê dưới đây.
Đầu tiên là các cách tiếp cận cho phép sửa đổi mảng giữa các lần trả lời truy vấn.
- Sqrt-decomposition - trả lời mỗi truy vấn trong $O(\sqrt{N})$, tiền xử lý được thực hiện trong $O(N)$. Ưu điểm: một cấu trúc dữ liệu rất đơn giản. Nhược điểm: độ phức tạp tồi tệ hơn.
- Segment tree - trả lời mỗi truy vấn trong $O(\log N)$, tiền xử lý được thực hiện trong $O(N)$. Ưu điểm: độ phức tạp thời gian tốt. Nhược điểm: lượng mã lớn hơn so với các cấu trúc dữ liệu khác.
- Fenwick tree - trả lời mỗi truy vấn trong $O(\log N)$, tiền xử lý được thực hiện trong $O(N \log N)$. Ưu điểm: mã ngắn nhất, độ phức tạp thời gian tốt. Nhược điểm: Cây Fenwick chỉ có thể được sử dụng cho các truy vấn có $L = 1$, vì vậy nó không áp dụng cho nhiều bài toán.
Và đây là những cách tiếp cận chỉ hoạt động trên các mảng tĩnh, tức là không thể thay đổi giá trị trong mảng mà không tính toán lại cấu trúc dữ liệu hoàn chỉnh.
- Sparse Table - trả lời mỗi truy vấn trong $O(1)$, tiền xử lý được thực hiện trong $O(N \log N)$. Ưu điểm: cấu trúc dữ liệu đơn giản, độ phức tạp thời gian tuyệt vời.
- Sqrt Tree - trả lời truy vấn trong $O(1)$, tiền xử lý được thực hiện trong $O(N \log \log N)$. Ưu điểm: nhanh. Nhược điểm: Phức tạp để cài đặt.
- Disjoint Set Union / Arpa's Trick - trả lời truy vấn trong $O(1)$, tiền xử lý trong $O(n)$. Ưu điểm: ngắn, nhanh. Nhược điểm: chỉ hoạt động nếu tất cả các truy vấn được biết trước, tức là chỉ hỗ trợ xử lý off-line các truy vấn.
- Cartesian Tree và Thuật toán Farach-Colton và Bender - trả lời truy vấn trong $O(1)$, tiền xử lý trong $O(n)$. Ưu điểm: độ phức tạp tối ưu. Nhược điểm: lượng mã lớn.
Lưu ý: Tiền xử lý là quá trình xử lý sơ bộ mảng đã cho bằng cách xây dựng cấu trúc dữ liệu tương ứng cho nó.