Phân chia là gì?

Phân chia là một cấu trúc dữ liệu dễ hiểu và rất phổ biến, đôi khi có thể giải quyết nhiều vấn đề động mà cây phân đoạn hoặc cây BIT không thuận tiện. Tuy nhiên, nhược điểm là độ phức tạp có thể cao hơn.

Làm thế nào để thực hiện phân chia?

Phân chia thực chất là một cách tiếp cận bạo lực, nhưng không hoàn toàn. Khi xử lý truy vấn \([l, r]\), thay vì tính tổng các phần tử từ 1 đến \(l-1\) và từ 1 đến \(r\) rồi lấy hiệu, phân chia sẽ chia dãy thành các khối và tính trước cho mỗi khối. Khi truy vấn, nếu khoảng chứa các khối nguyên, ta có thể lấy kết quả trực tiếp, còn phần lẻ ở hai đầu thì tính riêng.

Nếu độ dài dãy là \(n\), độ dài của mỗi khối là \(B\), số lần truy vấn là \(q\), độ phức tạp của phân chia là \(O(q(2B + \frac{n}{B}))\). Độ phức tạp tối ưu đạt được khi \(B = \sqrt{n}\), đưa ra độ phức tạp \(O(q \sqrt{n})\).

Khi cần cập nhật, nếu cập nhật một giá trị đơn, chỉ cần cập nhật giá trị đó và thông tin trong khối chứa nó, thường là \(O(1)\) hoặc \(O(B)\) (tức \(O(\sqrt{n})\)). Nếu cập nhật một khoảng, thường cập nhật đồng bộ cho các khối nguyên là \(O(1)\), còn các khối lẻ có thể cần \(O(B)\), dẫn đến độ phức tạp \(O(B + \frac{n}{B})\), tức \(O(\sqrt{n})\).

Thuật toán Mo là gì?

Thuật toán Mo, do Mo Tao phát minh, là một thuật toán giải quyết các vấn đề truy vấn khoảng dựa trên ý tưởng phân chia, với độ phức tạp \(O(n \sqrt{n})\). Thông thường, các bài toán Mo yêu cầu offline. Nếu bài toán yêu cầu online, không thể sử dụng Mo.

Nếu biết kết quả của khoảng \([l, r]\), ta có thể tính kết quả của các khoảng \([l, r+1], [l+1, r], [l, r-1], [l-1, r]\) trong \(O(k)\) thời gian, thì thuật toán Mo có thể giải quyết \(q\) truy vấn với độ phức tạp \(O(kq\sqrt{n})\).

Thường \(k = 1\), đôi khi \(k = \log n\).

Làm thế nào để thực hiện thuật toán Mo?

Đầu tiên, bạn cần xác định cách tính nhanh kết quả của các khoảng kề, ví dụ như đếm số lượng số khác nhau trong khoảng bằng cách sử dụng bucket.

Biết cách tính kết quả của các khoảng kề chưa đủ, vì khi truy vấn, bạn có thể di chuyển "nhảy" qua lại giữa hai đầu dãy, khiến hiệu suất kém. Do đó, cần tối ưu.

Cách tối ưu là sắp xếp các truy vấn theo thứ tự cụ thể. Thay vì sắp xếp theo \(l\) và \(r\) tăng dần, Mo Tao đề xuất chia dãy thành các khối và sắp xếp theo \(bel_l\) (khối chứa \(l\)) và \(bel_r\) (khối chứa \(r\)).

Độ phức tạp giảm khi \(B = \sqrt{\frac{n^2}{q}}\), đưa ra độ phức tạp trung bình \(O(n \sqrt{n})\), phù hợp cho quy mô \(10^5\) và đôi khi \(10^6\).

Một tối ưu khác là sắp xếp chẵn lẻ, giúp giảm thời gian di chuyển.

Cách thực hiện thuật toán Mo?

Lõi của thuật toán Mo là hai hàm Add và Del, dùng để cập nhật kết quả khi thêm hoặc bớt phần tử vào khoảng. Phần còn lại thường giống nhau, có thể sử dụng mẫu mã.

Ví dụ:

int m = read(); // m là số truy vấn
for (int i = 1; i <= m; i++) {
    q[i].l = read();
    q[i].r = read();
    q[i].id = i;
}
sort(q + 1, q + m + 1, cmp);
for (int i = 1; i <= m; i++) {
    while (L > q[i].l) Add(--L);
    while (R < q[i].r) Add(++R);
    while (L < q[i].l) Del(L++);
    while (R > q[i].r) Del(R--);
    ans[q[i].id] = nowAns;
}
for (int i = 1; i <= m; i++) cout << ans[i] << "\n";

Ví dụ

A - Tính tổng khoảng:

void Add(int p) { nowAns += a[p]; return; }
void Del(int p) { nowAns -= a[p]; return; }

B - Đếm số khác nhau:

void Add(int p) {
    if (!c[a[p]]) nowAns++;
    c[a[p]]++; return;
}
void Del(int p) {
    if (c[a[p]] == 1) nowAns--;
    c[a[p]]--; return;
}

C - XOR số chọn:

void Add(int p) {
    nowAns += c[a[p] ^ X];
    c[a[p]]++; return;
}
void Del(int p) {
    nowAns -= c[a[p] ^ X];
    c[a[p]]--; return;
}

D - Truy vấn Mo / Câu hỏi của B:

void Add(int p) {
    nowAns -= c[a[p]] * c[a[p]];
    c[a[p]]++;
    nowAns += c[a[p]] * c[a[p]]; return;
}
void Del(int p) {
    nowAns -= c[a[p]] * c[a[p]];
    c[a[p]]--;
    nowAns += c[a[p]] * c[a[p]]; return;
}

E - Mảng mạnh mẽ:

void Add(int p) {
    nowAns -= c[a[p]] * c[a[p]] * a[p];
    c[a[p]]++;
    nowAns += c[a[p]] * c[a[p]] * a[p]; return;
}
void Del(int p) {
    nowAns -= c[a[p]] * c[a[p]] * a[p];
    c[a[p]]--;
    nowAns += c[a[p]] * c[a[p]] * a[p]; return;
}

F - Nỗi lo của faebdc:

void Add(int p) {
    cnt[++c[a[p]]]++;
    if (c[a[p]] > nowAns) nowAns = c[a[p]]; return;
}
void Del(int p) {
    if (cnt[c[a[p]]] == 1 && nowAns == c[a[p]]) nowAns--;
    cnt[c[a[p]]--]--; return;
}

G - XOR và Số ưa thích:

void Add(int p) {
    nowAns += c[sum[p] ^ k];
    c[sum[p]]++; return;
}
void Del(int p) {
    c[sum[p]]--;
    nowAns -= c[sum[p] ^ k]; return;
}

H - Bài toán Rmq / mex:

void Add(int p) {
    c[a[p]]++;
    if (c[a[p]] == 1) bt.set(a[p], 0); return;
}
void Del(int p) {
    c[a[p]]--;
    if (!c[a[p]]) bt.set(a[p], 1); return;
}

ans[q[i].id] = bt._Find_first();

I - Poklon:

void Add(int p) {
    if (c[a[p]] == 2) nowAns--;
    c[a[p]]++;
    if (c[a[p]] == 2) nowAns++; return;
}
void Del(int p) {
    if (c[a[p]] == 2) nowAns--;
    c[a[p]]--;
    if (c[a[p]] == 2) nowAns++; return;
}

J - BaoBao Yêu Đọc Sách:

void Add(int p) {
if (!c[a[p]]) nowCnt++;
c[a[p]]++; return;
}
void Del(int p) {
if (c[a[p]] == 1) nowCnt--;
c[a[p]]--; return;
}

n = read(), m = 0, L = 1, R = 0;
sq = sqrt(n), Bas = 0, nowAns = 0, cnt = 0;
for (int i = 1; i