Wiki › Cấu trúc dữ liệu › Mo's Algorithm

Mo's Algorithm

huunguyen Updated Tháng sáu 2, 2026

Thuật toán Mo (Mo's Algorithm) là kỹ thuật xử lý truy vấn offline trên đoạn $[l, r]$ của một mảng tĩnh. Thay vì trả lời từng truy vấn độc lập, ta sắp xếp lại thứ tự các truy vấn rồi dùng một cặp con trỏ trượt dần từ đoạn này sang đoạn kế tiếp. Nhờ thứ tự khéo léo, tổng quãng đường con trỏ di chuyển chỉ là $O ((N + Q) \sqrt{N})$ — nhanh hơn rất nhiều so với cách ngây thơ trả lời mỗi truy vấn trong $O (N)$ (tổng $O (N Q)$ ).

Khi nào dùng: bài toán cho phép từ kết quả của đoạn $[l, r]$ suy ra kết quả của đoạn liền kề ( $[l, r + 1]$ , $[l, r - 1]$ , $[l - 1, r]$ , $[l + 1, r]$ ) bằng thao tác thêm một phần tử hoặc xóa một phần tử trong $O (1)$ (hoặc $O (\log N)$ ). Đây là cứu cánh khi ta không biết cách gộp (merge) kết quả hai nửa đoạn để dùng Segment Tree (ví dụ "đếm số giá trị phân biệt trong đoạn" — không có công thức gộp đơn giản).

Hai điều kiện bắt buộc:

Offline — biết toàn bộ truy vấn trước khi trả lời (để được phép sắp xếp lại).
Mảng không đổi giữa các truy vấn (biến thể có cập nhật sẽ bàn ở phần Mở rộng).

Ý tưởng / Trực giác

Giả sử ta có một "cửa sổ" hiện tại $[c u r L, c u r R]$ cùng kết quả cur_ans của nó, và đã viết được hai hàm:

add(i) — đưa phần tử $a [i]$ vào cửa sổ, cập nhật cur_ans.
remove(i) — bỏ phần tử $a [i]$ khỏi cửa sổ, cập nhật cur_ans.

Để chuyển từ cửa sổ hiện tại sang truy vấn $[l, r]$ , ta chỉ việc nới rộng / thu hẹp hai biên bằng cách gọi add/remove từng bước. Chi phí chuyển giữa hai truy vấn bằng tổng khoảng cách dịch chuyển của hai con trỏ. Nếu xử lý truy vấn theo thứ tự ngẫu nhiên, con trỏ có thể nhảy qua nhảy lại cả $N$ bước mỗi lần → $O (N Q)$ , vô ích.

Mẹo cốt lõi: chia mảng thành các khối (block) kích thước $S \approx \sqrt{N}$ . Sắp xếp truy vấn theo khóa:

Trước hết theo khối chứa $l$ (tức $⌊ l / S ⌋$ ) tăng dần.
Trong cùng một khối, theo $r$ tăng dần.

Vì sao khóa này khiến tổng dịch chuyển nhỏ? Phân tích hai con trỏ riêng biệt:

Con trỏ $r$ : trong cùng một khối của $l$ , các truy vấn được sắp theo $r$ tăng → $r$ chỉ tiến (gần như đơn điệu), đi tối đa $N$ bước cho mỗi khối. Có $\sqrt{N}$ khối nên tổng cho $r$ là $O (N \sqrt{N})$ .
Con trỏ $l$ : mọi $l$ trong cùng một khối nằm gọn trong một dải rộng $S = \sqrt{N}$ . Giữa hai truy vấn liên tiếp, $l$ nhảy tối đa $\sqrt{N}$ bước. Có $Q$ truy vấn nên tổng cho $l$ là $O (Q \sqrt{N})$ .

Cộng lại: $O ((N + Q) \sqrt{N})$ . Mấu chốt là đánh đổi: hy sinh chút trật tự của $l$ (cho nó dao động trong $\sqrt{N}$ ) để $r$ được đơn điệu trong mỗi khối — và $\sqrt{N}$ chính là điểm cân bằng tối ưu giữa hai chi phí này.

Tối ưu zíc-zắc: với khối lẻ thì sắp $r$ giảm dần, khối chẵn thì $r$ tăng dần. Khi đó cuối khối này $r$ đang ở một đầu, đầu khối kế tiếp $r$ tiếp tục từ đúng đầu đó thay vì "tua lại" về 0 — giảm hằng số (thường nhanh gần gấp đôi). Đây là tinh thần của tối ưu Hilbert curve nhưng đơn giản hơn nhiều.

Ví dụ chạy tay

Bài toán: đếm số giá trị phân biệt trong đoạn. Mảng (1-based, đổi sang 0-based khi xử lý):

chỉ số (0-based):  0   1   2   3   4
giá trị a:         3   2   3   1   2

$N = 5 \Rightarrow S = ⌊ \sqrt{5} ⌋ = 2$ . Khối của chỉ số $i$ là $⌊ i / 2 ⌋$ :

chỉ số:  0  1 | 2  3 | 4
khối:    0  0 | 1  1 | 2

Ba truy vấn (đã đổi về 0-based $[l, r]$ ): $Q_{1} = [0, 2]$ , $Q_{2} = [1, 3]$ , $Q_{3} = [0, 4]$ .

Tính khóa sắp xếp (block(l), r) với quy ước khối chẵn → $r$ tăng:

        l  r   block(l)   khóa sắp xếp
Q1      0  2      0        (0, +2)
Q2      1  3      0        (0, +3)
Q3      0  4      0        (0, +4)

Cả ba cùng khối 0 của $l$ , nên sắp theo $r$ tăng: thứ tự xử lý là $Q_{1}, Q_{2}, Q_{3}$ .

Khởi tạo cửa sổ rỗng: curL = 0, curR = -1, cur_ans = 0, mảng tần suất freq toàn 0. Quy ước vòng lặp nới trước, thu sau (sẽ giải thích ở phần Lỗi thường gặp).

Xử lý $Q_{1} = [0, 2]$ — cần curR tiến tới 2, curL giữ 0:

add(0): a=3, freq[3]:0->1  => +1 giá trị mới   cur_ans=1   cửa sổ [3]
add(1): a=2, freq[2]:0->1  => +1 giá trị mới   cur_ans=2   cửa sổ [3,2]
add(2): a=3, freq[3]:1->2  => không mới        cur_ans=2   cửa sổ [3,2,3]
                                                           ^^^^^^^^^^^
Đáp án Q1 = 2   (tập {3,2})

Xử lý $Q_{2} = [1, 3]$ — từ $[0, 2]$ sang $[1, 3]$ : curR 2→3 (add), curL 0→1 (remove):

add(3):    a=1, freq[1]:0->1 => +1 mới     cur_ans=3   cửa sổ [3,2,3,1]
remove(0): a=3, freq[3]:2->1 => còn >0     cur_ans=3   cửa sổ   [2,3,1]
                                                                ^^^^^^^
Đáp án Q2 = 3   (tập {2,3,1})

Xử lý $Q_{3} = [0, 4]$ — từ $[1, 3]$ sang $[0, 4]$ : curR 3→4 (add), curL 1→0 (add lùi):

add(4):  a=2, freq[2]:1->2 => không mới   cur_ans=3   cửa sổ [2,3,1,2]
add(--0):a=3, freq[3]:1->2 => không mới   cur_ans=3   cửa sổ[3,2,3,1,2]
                                                            ^^^^^^^^^^^^^
Đáp án Q3 = 3   (tập {3,2,1})

In kết quả theo chỉ số gốc (idx đã lưu khi đọc): 2 3 3. Quan sát: con trỏ $r$ chỉ đi 0→2→3→4 (đơn điệu, không tua lại), đúng như phân tích.

Cài đặt

Khung chuẩn cho bài "đếm số giá trị phân biệt trên đoạn" (chính là bài distvalq). Lưu ý phải nén giá trị vì $a_{i}$ tới $10^{9}$ nhưng mảng freq chỉ đánh theo chỉ số nén.

#include <bits/stdc++.h>
using namespace std;

int n, q, S;                 // S = kích thước khối ~ sqrt(n)
vector<int> a;               // mảng đã NÉN giá trị về [0, n-1]
vector<int> freq;            // freq[v] = số lần giá trị v xuất hiện trong cửa sổ
long long cur_ans = 0;       // số giá trị phân biệt của cửa sổ hiện tại

struct Query { int l, r, idx; };

// Thêm a[pos] vào cửa sổ
void add(int pos) {
    if (freq[a[pos]] == 0) cur_ans++;   // 0 -> 1: xuất hiện một giá trị MỚI
    freq[a[pos]]++;
}
// Xóa a[pos] khỏi cửa sổ
void remove(int pos) {
    freq[a[pos]]--;
    if (freq[a[pos]] == 0) cur_ans--;   // 1 -> 0: một giá trị BIẾN MẤT
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q;
    a.resize(n);
    vector<int> raw(n);
    for (int i = 0; i < n; i++) cin >> raw[i];

    // --- Nén giá trị: ánh xạ mỗi giá trị về [0, n-1] ---
    vector<int> srt(raw);
    sort(srt.begin(), srt.end());
    srt.erase(unique(srt.begin(), srt.end()), srt.end());
    for (int i = 0; i < n; i++)
        a[i] = lower_bound(srt.begin(), srt.end(), raw[i]) - srt.begin();
    freq.assign(srt.size(), 0);

    S = max(1, (int)(n / sqrt((double)max(1, q)) + 1)); // hoặc đơn giản: sqrt(n)
    S = max(1, (int)sqrt((double)n));                   // dùng sqrt(n) cho dễ hiểu

    vector<Query> qs(q);
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        qs[i] = { l - 1, r - 1, i };    // đổi về 0-based
    }

    // --- Sắp xếp Mo: khối của l tăng; trong khối, r theo zíc-zắc ---
    sort(qs.begin(), qs.end(), [&](const Query& x, const Query& y) {
        int bx = x.l / S, by = y.l / S;
        if (bx != by) return bx < by;
        return (bx & 1) ? (x.r > y.r) : (x.r < y.r);  // khối lẻ: r giảm; chẵn: r tăng
    });

    vector<long long> ans(q);
    int curL = 0, curR = -1;            // cửa sổ rỗng ban đầu
    for (auto& Q : qs) {
        // THỨ TỰ AN TOÀN: nới rộng trước (add), thu hẹp sau (remove)
        while (curR < Q.r) add(++curR);
        while (curL > Q.l) add(--curL);
        while (curR > Q.r) remove(curR--);
        while (curL < Q.l) remove(curL++);
        ans[Q.idx] = cur_ans;
    }
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
    return 0;
}

Để giải bài khác, thường chỉ cần viết lại add/remove và đổi kiểu cur_ans. Ví dụ đếm số cặp phần tử bằng nhau trong đoạn ( $\sum_{v} (\binom{c n t_{v}}{2})$ ):

long long cur_ans = 0;       // số cặp (i<j) trong cửa sổ có a[i]==a[j]
void add(int pos) {
    cur_ans += freq[a[pos]]; // a[pos] ghép với freq[a[pos]] phần tử cùng giá trị đang có
    freq[a[pos]]++;
}
void remove(int pos) {
    freq[a[pos]]--;
    cur_ans -= freq[a[pos]]; // bỏ a[pos] thì mất đúng freq[a[pos]] (sau giảm) cặp
}

Độ phức tạp

Biến thể	Kích thước khối	Thời gian	Bộ nhớ
Mo chuẩn	$\sqrt{N}$	$O ((N + Q) \sqrt{N})$	$O (N + Q)$
Mo + zíc-zắc	$\sqrt{N}$	$O ((N + Q) \sqrt{N})$ , hằng số nhỏ hơn	$O (N + Q)$
Mo có cập nhật (3D)	$N^{2 / 3}$	$O (N^{5 / 3})$	$O (N + Q)$

Lý giải thời gian (đã chứng minh ở phần Trực giác): con trỏ $r$ đơn điệu trong mỗi khối, tổng $O (N \sqrt{N})$ ; con trỏ $l$ nhảy tối đa $\sqrt{N}$ mỗi truy vấn, tổng $O (Q \sqrt{N})$ . Mỗi bước add/remove là $O (1)$ nên không phát sinh thêm log. Nếu add/remove tốn $O (\log N)$ thì toàn bộ thành $O ((N + Q) \sqrt{N} \log N)$ .

Lý giải bộ nhớ: lưu mảng $a$ và danh sách $Q$ truy vấn ( $O (N + Q)$ ), mảng freq kích thước bằng số giá trị phân biệt ( $\leq N$ ), mảng ans ( $O (Q)$ ). Không có cấu trúc đệ quy nào nên tổng $O (N + Q)$ .

Với $N, Q \leq 2 \cdot 10^{5}$ thì $(N + Q) \sqrt{N} \approx 4 \cdot 10^{5} \cdot 450 \approx 1.8 \cdot 10^{8}$ — chạy tốt trong vài giây nhờ hằng số cực nhỏ (chỉ vài phép cộng trên mảng).

⚠️ Lỗi thường gặp

Quên điều kiện offline. Nếu giữa các truy vấn mảng bị thay đổi giá trị, Mo chuẩn sai (không được phép sắp xếp lại như mảng tĩnh). Khi đó phải dùng biến thể Mo có cập nhật ở dưới, hoặc đổi sang Segment Tree / BIT.
Sai thứ tự bốn vòng while. Phải nới rộng trước (add), thu hẹp sau (remove): add(++curR), add(--curL) rồi mới remove(curR--), remove(curL++). Nếu thu hẹp trước, có lúc curL > curR + 1 khiến remove chạm vào phần tử ngoài cửa sổ, làm freq âm và cur_ans sai. Đây là bug kinh điển khó tìm vì code vẫn "chạy" và chỉ sai vài test.
Lệch biên (off-by-one) khi cập nhật con trỏ. Nhớ tăng/giảm con trỏ đúng phía: add(++curR) (tăng rồi mới thêm) nhưng remove(curR--) (xóa phần tử hiện tại rồi mới giảm). Đảo nhầm tiền/hậu tố sẽ bỏ sót hoặc lặp một phần tử ở biên.
Quên nén giá trị / freq tràn chỉ số. $a_{i}$ có thể tới $10^{9}$ trong khi freq chỉ cấp $O (N)$ phần tử. Không nén → truy cập freq[a[pos]] ngoài mảng (UB, RE). Luôn nén về $[0, N - 1]$ trước khi chạy Mo.
Tràn số ở cur_ans. Các bài đếm cặp dùng $(\binom{c n t}{2})$ hay tổng tích có thể vượt $2^{31}$ . Dùng long long cho cur_ans và mọi biến tích lũy; chỉ dùng int thì sai âm thầm (overflow) trên test lớn.
Đổi 0-based/1-based không nhất quán. Đề thường 1-based; nếu trừ 1 cho $l$ mà quên trừ cho $r$ (hoặc ngược lại) thì đoạn lệch một phần tử. Đổi cả hai ngay khi đọc truy vấn.
In kết quả sai thứ tự. Sau khi sắp xếp lại truy vấn, phải lưu chỉ số gốc idx và ghi ans[Q.idx], rồi in theo thứ tự gốc. In trực tiếp trong vòng lặp xử lý sẽ ra thứ tự đã sắp, không khớp đề.
Tưởng dùng được cho min/max trên đoạn. Mo cần thao tác xóa đảo ngược được thao tác thêm. Với min/max, khi xóa phần tử nhỏ nhất ta không khôi phục được min cũ trong $O (1)$ . Những bài "chỉ thêm được, khó xóa" cần kỹ thuật khác (Mo không xóa — rollback Mo / DSU on tree), đừng ép Mo chuẩn vào.

Biến thể / Mở rộng

Mo trên cây (Mo on tree). Để hỏi trên cây con hoặc đường đi, ta "trải phẳng" cây bằng Euler tour thành một mảng rồi áp Mo lên mảng đó:

Cây con của $u$ ứng với một đoạn liên tục $[t i n [u], t o u t [u]]$ trong dãy Euler theo thời điểm vào — đưa thẳng về Mo trên mảng (đây chính là cách giải bài distcolor).
Đường đi $u \to v$ dùng dãy Euler "vào/ra" (mỗi đỉnh xuất hiện 2 lần): phần tử nào xuất hiện đúng 1 lần trong đoạn mới thực sự nằm trên đường đi (thêm/xóa theo cơ chế bật–tắt), xử lý riêng đỉnh LCA.

Mo có cập nhật (Mo 3D). Khi có thêm thao tác gán $a [k] = u$ xen kẽ (như bài distvalq2), ta thêm chiều thứ ba là thời gian $t$ = số cập nhật đã xảy ra trước truy vấn. Khóa sắp xếp thành $(⌊ l / S ⌋, ⌊ r / S ⌋, t)$ với $S = N^{2 / 3}$ . Ngoài bốn vòng while dịch $l, r$ , ta thêm vòng "tua thời gian": chưa đủ cập nhật thì áp cập nhật kế tiếp, dư thì hoàn tác. Mỗi apply/undo nếu chỉ số nằm trong $[c u r L, c u r R]$ phải remove giá trị cũ rồi add giá trị mới. Độ phức tạp $O (N^{5 / 3})$ .

Bài tập luyện

Truy vấn Số Giá trị Phân biệt (distvalq) — (Nâng cao) Đếm số giá trị phân biệt trên đoạn, không cập nhật — bài Mo chuẩn để áp khung add/remove ở trên gần như nguyên xi.
Số màu phân biệt trong cây con (distcolor) — (Kỳ cựu) Trải phẳng cây bằng Euler tour rồi đếm màu phân biệt trên đoạn $[t i n [u], t o u t [u]]$ — luyện kỹ thuật Mo trên cây con.
Truy vấn Số Giá trị Phân biệt II (distvalq2) — (Kỳ cựu) Kiểm tra một đoạn có toàn phần tử phân biệt không, có cập nhật điểm — bài điển hình cho Mo 3D (thêm chiều thời gian, $O (N^{5 / 3})$ ).