Mo's Algorithm

Wiki › Cấu trúc dữ liệu

huunguyen · Last updated 8, Tháng 4, 2026, 16:01

Mo's Algorithm là kỹ thuật offline trả lời các truy vấn đoạn $[l, r]$ trong $O ((N + Q) \sqrt{N})$ bằng cách sắp xếp thứ tự truy vấn để giảm tổng số bước di chuyển con trỏ.

Điều kiện: Có thể thêm/xóa phần tử khỏi đoạn hiện tại trong $O (1)$ , và bài toán offline (biết tất cả truy vấn trước).

Ý tưởng

Chia mảng thành các block kích thước $\sqrt{N}$ . Sắp xếp truy vấn theo:

Block của $l$ tăng dần.
Trong cùng block: $r$ tăng dần (block lẻ) hoặc giảm dần (block chẵn — tối ưu Hilbert).

Di chuyển $[c u r L, c u r R]$ đến $[l, r]$ bằng cách thêm/xóa từng phần tử.

Cài đặt chuẩn

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

const int MAXN = 1e5 + 5;
int a[MAXN], cnt[MAXN];
long long cur_ans = 0;   // kết quả hiện tại của đoạn [curL, curR]
int freq[MAXN];          // tần suất mỗi giá trị

// Thêm/xóa phần tử — tùy bài toán
void add(int pos) {
    freq[a[pos]]++;
    if (freq[a[pos]] == 1) cur_ans++;   // ví dụ: đếm số phân biệt
}

void remove(int pos) {
    freq[a[pos]]--;
    if (freq[a[pos]] == 0) cur_ans--;
}

int main() {
    int n, q; cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];

    int block = max(1, (int)sqrt(n));

    struct Query { int l, r, idx; };
    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].l--; queries[i].r--;   // 0-based
        queries[i].idx = i;
    }

    // Sắp xếp Mo (với Hilbert curve optimization)
    sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
        int ba = a.l / block, bb = b.l / block;
        if (ba != bb) return ba < bb;
        return (ba & 1) ? a.r > b.r : a.r < b.r;
    });

    vector<long long> ans(q);
    int curL = 0, curR = -1;

    for (auto& [l, r, idx] : queries) {
        while (curR < r) add(++curR);
        while (curL > l) add(--curL);
        while (curR > r) remove(curR--);
        while (curL < l) remove(curL++);
        ans[idx] = cur_ans;
    }

    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}

Ví dụ: Đếm số phân biệt trong đoạn

// Với add/remove như trên (cur_ans = số giá trị có freq > 0)
// → trả lời "đoạn [l,r] có bao nhiêu giá trị phân biệt"

Ví dụ: Số cặp bằng nhau trong đoạn

long long cur_ans = 0;
int freq[MAXN];

void add(int pos) {
    cur_ans += freq[a[pos]];   // thêm a[pos]: tạo thêm freq[a[pos]] cặp mới
    freq[a[pos]]++;
}

void remove(int pos) {
    freq[a[pos]]--;
    cur_ans -= freq[a[pos]];
}

Mo's Algorithm trên cây

Mo trên cây: flatten cây bằng Euler tour, áp Mo trên mảng Euler:

// Với mỗi đỉnh u: vào lúc tin[u], ra lúc tout[u]
// Truy vấn (u,v):
//   - Nếu u và v trong cùng một nhánh: đoạn [tin[u], tin[v]] (u nông hơn)
//   - Ngược lại: đoạn [tout[u], tin[v]] + LCA(u,v)

Mo's Algorithm với cập nhật (Mo 3D)

Thêm chiều thứ 3 là thời gian cập nhật. Độ phức tạp $O (N^{5 / 3})$ :

// Block size = N^{2/3}
// Sắp xếp theo (block_l, block_r, time)

Độ phức tạp

Variant	Block size	Độ phức tạp
Mo chuẩn	$\sqrt{N}$	$O ((N + Q) \sqrt{N})$
Mo + Hilbert	$\sqrt{N}$	$O ((N + Q) \sqrt{N})$ hằng số nhỏ hơn
Mo 3D (update)	$N^{2 / 3}$	$O (N^{5 / 3})$

Khi nào dùng Mo's Algorithm?

Truy vấn đoạn offline, không có cập nhật (hoặc ít cập nhật).
Thêm/xóa phần tử $O (1)$ , nhưng không có cách query $O (\log N)$ .
Thay thế Segment Tree khi không biết cách merge kết quả.

Bình luận

Không có bình luận tại thời điểm này.