Tác giả: Nguyễn RR Thành Trung
Tiếp nối chuỗi bài viết về các thuật toán chia căn, trong bài viết này chúng ta sẽ bàn về kĩ thuật tăng tốc độ trả lời truy vấn bằng cách sắp xếp chúng theo một thứ tự nhất định, còn gọi là Mo's algorithm.
Cho một dãy số gồm phần tử. Cần thực hiện truy vấn, mỗi truy vấn yêu cầu tìm . (Mode của một tập hợp là giá trị xuất hiện nhiều lần nhất trong tập hợp đó). Giới hạn: .
Khi đọc đề một bài toán truy vấn kiểu này, có lẽ CTDL đầu tiên mà các bạn nghĩ đến là Interval Tree. Nhưng có điều gì đó không ổn trong bài này: Khi có thông tin của 2 nút con và , rất khó để tìm được bất kỳ thông tin hữu ích nào của .
Chúng ta xuất phát từ thuật toán duyệt hồn nhiên như sau:
Code đơn giản như sau:
function mode(l, r):
// Khởi tạo mảng count = toàn 0
res = -1;
for i = l .. r:
count[A[i]] += 1;
if res == -1 or count[A[i]] > count[res]:
res = A[i];
return res;
Dễ thấy, thuật toán duyệt này có độ phức tạp . Có 2 lý do chính khiến thuật toán này chạy chậm:
Ta có thể cải tiến được như sau:
Sau khi trả lời truy vấn , để trả lời truy vấn , bạn chỉ cần thay đổi mảng đếm một cách phù hợp. Cụ thể:
Để cập nhật số lần xuất hiện lớn nhất thì có thể dùng thêm set.
Như vậy, độ phức tạp của ta là tổng , nhân thêm để đếm và tìm phần tử lớn nhất của mảng đếm.
Thuật toán Mo là một cách sắp xếp lại các truy vấn, sao cho tổng không quá .
Thứ tự các truy vấn được định nghĩa qua hàm so sánh dưới đây.
S = sqrt(N);
bool cmp(Query A, Query B) // so sánh 2 truy vấn
{
if (A.l / S != B.l / S) {
return A.l / S < B.l / S;
}
return A.r < B.r;
}
Giải thích:
Chứng minh:
Mo's algorithm có độ phức tạp là . Để hiểu tại sao độ phức tạp của thuật toán đạt được như vậy, chúng ta hãy cùng xem việc di chuyển các đoạn thành :
Vậy, độ phức tạp là hay .
Sử dụng Mo's Algorithm, bạn đã có thể thu được một thuật toán hoàn chỉnh cho bài này với độ phức tạp :
Vì tổng các thao tác thêm và xóa khi áp dụng Mo's Algorithm không quá , ta thu được một thuật toán với độ phức tạp này.
Với mục đích làm bài toán khó hơn, ta xét trường hợp mà CTDL của ta chỉ cho phép thực hiện đúng 2 thao tác:
Một ví dụ của CTDL loại này là Disjoint set, và việc xử lý truy vấn xuất hiện trong bài toán Codechef - GERALD07.
Cách làm vẫn là áp dụng Mo's algorithm, tuy nhiên vì không thể xóa phần tử, nên ta không thể di chuyển từ sang một cách dễ dàng được.
Để đơn giản, chúng ta chỉ xét những truy vấn mà và rơi vào 2 block khác nhau. Để giải quyết việc không di chuyển ngược được, sau khi trả lời truy vấn , chúng ta cần dùng Rollback để đưa l về cuối block chứa l. Sau đó, khi trả lời truy vấn , chúng ta chỉ cần thực hiện Insert từ đến và từ đến cuối block chứa .
Chi tiết cài đặt:
rt = sqrt(n);
init(); // this initializes our data structure (clears it)
snapshot();
for all queries q
if q.r - q.l + 1 <= rt + 1 // we process light queries
for j := q.l to q.r
insert(j);
store answer for query q;
rollback();
last_bucket = -1;
for all queries q
if q.r - q.l + 1 <= rt + 1: continue;
bucket = q.l / rt;
if bucket != last_bucket
init();
l = (bucket + 1) * rt; // right border of the bucket
r = q.r;
for j := l to r
insert(j);
last_bucket = bucket;
while r < q.r
insert(++r);
snapshot();
for j := q.l to l - 1
insert(j);
store answer for query q;
rollback();
Các bạn có thể đọc thêm về cách cải tiến tốc độ chạy của Mo sử dụng TSP và Hilbert curve tại đây.