Mo's Algorithm · Nhóm: Cấu trúc dữ liệu
Thuật toán Mo (Mo's Algorithm) trả lời offline nhiều truy vấn đoạn bằng cách sắp thứ tự truy vấn theo khối của đầu trái rồi tới đầu phải, sau đó dùng hai con trỏ dịch cửa sổ dần từ truy vấn này sang truy vấn kế.
Thu gom toàn bộ truy vấn rồi sắp theo khối của điểm trái, cùng khối thì sắp theo điểm phải.
Duy trì cửa sổ hiện tại cùng giá trị tổng của cửa sổ đó.
Với mỗi truy vấn, dịch hai con trỏ tới đúng đoạn cần hỏi rồi ghi lại đáp án theo thứ tự gốc.
Nhờ sắp khéo, tổng quãng đường di chuyển của hai con trỏ qua mọi truy vấn chỉ còn cỡ (n cộng q) nhân căn n, thay vì tính lại từng đoạn từ đầu.
def mo(a, queries, B): # answer range-sum queries offline
queries.sort(key=lambda q: (q.l // B, q.r))
curL, curR, cur = 0, -1, 0
ans = [0] * len(queries)
for q in queries: # move window to [q.l, q.r]
while curR < q.r: curR += 1; cur += a[curR]
while curL > q.l: curL -= 1; cur += a[curL]
while curR > q.r: cur -= a[curR]; curR -= 1
while curL < q.l: cur -= a[curL]; curL += 1
ans[q.id] = cur
return ans
Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.