Mở đầu
Tìm kiếm nhị phân (hay chặt nhị phân) là một khái niệm không còn xa lạ với những ai học lập trình. Đây là một thuật toán hiệu quả, dễ áp dụng và thường được phối hợp với nhiều kỹ thuật khác.
Bài viết này sẽ khám phá một phương pháp kết hợp tìm kiếm nhị phân với “chính bản thân nó” – được gọi là tìm kiếm nhị phân song song.
So với tìm kiếm nhị phân thông thường, tìm kiếm nhị phân song song là một khái niệm ít được biết đến hơn. Như tên gọi gợi ý, nền tảng của kỹ thuật này vẫn là tìm kiếm nhị phân. Do đó, độc giả nên nắm vững kiến thức cơ bản về tìm kiếm nhị phân để có thể theo dõi nội dung bài viết một cách tốt nhất.
Bài toán minh họa
Meteors
Các bạn có thể nộp thử bài tại đây.
Xét (N) tổ chức cùng tham gia thu gom các mảnh vỡ thiên thạch trên một quỹ đạo hình tròn. Tổ chức thứ (i) đặt mục tiêu thu được ít nhất (p_i) mảnh. Quỹ đạo này được phân thành (M) khu vực, đánh số từ 1 đến (M), trong đó khu vực (M) và khu vực (1) kề nhau. Mỗi khu vực thuộc quyền quản lý của một trong (N) tổ chức.
Các nhà khoa học dự báo sẽ có (K) đợt mưa sao băng. Đợt mưa thứ (i) (xảy ra tại thời điểm (i)) sẽ làm tăng số lượng mảnh vỡ thêm (a_i) đơn vị cho các khu vực có chỉ số nằm trong đoạn ([l_i; r_i]). Lưu ý: nếu (l_i > r_i), đoạn này bao gồm hai phần: ([l_i; M]) và ([1; r_i]).
Yêu cầu đặt ra là: đối với mỗi tổ chức, hãy xác định thời điểm sớm nhất mà tổ chức đó gom đủ số lượng mảnh vỡ theo yêu cầu. Giới hạn:
(1 le N, M, K le 3 times 10^5, 1 le p_i, l_i, r_i le M, 1 le a_i le 10^9)
Cách tiếp cận ban đầu
Đối với từng tổ chức, ta có thể áp dụng tìm kiếm nhị phân trên thang thời gian (từ 1 đến (K)) để tìm thời điểm sớm nhất mà mục tiêu được hoàn thành.
Để kiểm tra xem tại thời điểm (t), tổ chức (i) đã thu được bao nhiêu mảnh, ta cần xem xét tất cả các đợt mưa sao băng xảy ra không muộn hơn (t). Ta có thể dùng một cấu trúc dữ liệu như Fenwick Tree (cây BIT) để cập nhật số mảnh tăng thêm tại các khu vực do các đợt mưa này gây ra, sau đó tính tổng số mảnh tại các khu vực thuộc sở hữu của tổ chức (i).
Phương pháp này có độ phức tạp thời gian để tìm câu trả lời cho một tổ chức (i) là (O((K + |S_i|) times log(K) times log(M))), với (|S_i|) là số khu vực mà tổ chức (i) quản lý. Do đó, tổng độ phức tạp cho tất cả (N) tổ chức sẽ là (O(N times (K + M) times log(K) times log(M))), rõ ràng là vượt quá giới hạn thời gian cho phép.
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 3e5 + 5;
int n, m, k;
int owner[MAXN], req[MAXN], L[MAXN], R[MAXN], A[MAXN], l[MAXN], r[MAXN];
vector<int> pos[MAXN];
struct FenwickTree {
...
} ft;
bool check(int o, int k) {
for (int i = 1; i <= k; i++) {
update(i, 1);
}
long long cnt = 0;
for (int i : pos[o]) {
cnt += ft.get(i);
cnt = min(cnt, 1LL * req[o] + 1);
}
for (int i = 1; i <= k; i++) { update(i, -1); } return cnt >= req[o];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) { cin >> owner[i];
}
for (int i = 1; i <= n; i++) { cin >> req[i];
}
cin >> k;
for (int i = 1; i <= k; i++) { cin >> L[i] >> R[i] >> A[i];
}
for (int i = 1; i <= n; i++) {
l[i] = 0, r[i] = k + 1;
}
for (int i = 1; i <= m; i++) {
pos[owner[i]].push_back(i);
}
ft.build(m + 1);
for (int i = 1; i <= n; i++) {
int l = 0, r = k + 1;
while (l < r) { int g = (l + r) / 2; if (check(i, g)) { r = g; } else { l = g + 1; } } if (r > k) {
cout << "NIEn";
} else {
cout << r << "n";
}
}
return 0;
}
Phương pháp tối ưu
Đặt (check(o, k)) là hàm xác định xem liệu (k) đợt mưa sao băng đầu tiên có đủ để tổ chức (o) đạt được mục tiêu số mảnh đá hay không.
Khi ta tính (check(o, g)), ta phải xử lý thông tin của (g) đợt mưa đầu tiên. Việc xử lý lặp đi lặp lại (g) thông tin này cho mỗi lần gọi hàm (check) với các tổ chức khác nhau (ví dụ (check(o’, g))) là một sự lãng phí tài nguyên tính toán. Liệu có cách nào tận dụng việc xử lý thông tin đến đợt mưa thứ (g) để đồng thời kiểm tra cho nhiều tổ chức khác không?
Phát triển ý tưởng này, ta duy trì một khoảng ([l[i], r[i]]) cho mỗi tổ chức (i), đây là khoảng thời gian (số đợt mưa) chứa đáp án (thời điểm sớm nhất) cho tổ chức đó.
Ta xử lý lần lượt thông tin về các đợt mưa từ 1 đến (K). Tại mỗi bước xử lý đợt mưa thứ (g), ta cập nhật thông tin này vào cây BIT. Đồng thời, ta xác định những tổ chức (i) nào đang có điểm giữa (mid = leftlfloor frac{l[i] + r[i]}{2} rightrfloor) của khoảng tìm kiếm bằng đúng (g). Với những tổ chức (i) này, ta thực hiện kiểm tra (check(i)) (dựa trên trạng thái hiện tại của cây BIT sau (g) đợt mưa). Dựa vào kết quả kiểm tra, ta cập nhật lại khoảng ([l[i], r[i]]) tương tự như trong thuật toán tìm kiếm nhị phân thông thường (nếu đủ thì thu hẹp về nửa trái (r[i] = mid), nếu chưa đủ thì thu hẹp về nửa phải (l[i] = mid + 1)).
Xem xét lại độ phức tạp: trong một ‘lượt’ xử lý toàn bộ (K) thông tin đợt mưa:
- Chi phí cập nhật BIT cho (K) đợt mưa và truy vấn tổng cho các khu vực (mỗi khu vực được truy vấn tối đa một lần trong hàm check cho chủ sở hữu của nó qua các lần lặp) là (O((K + M) times log(M))).
- Đối với mỗi tổ chức (t), khoảng tìm kiếm ([l[t], r[t]]) được giảm đi một nửa.
Do đó, ta chỉ cần lặp lại quá trình xử lý (K) đợt mưa này khoảng (log(K)) lần cho đến khi khoảng ([l[i], r[i]]) của mọi tổ chức (i) thu hẹp lại chỉ còn một giá trị (độ dài bằng 1). Tổng độ phức tạp thời gian là (O((K + M + N) times log(K) times log(M))). Nếu không xóa dữ liệu cây BIT giữa các lượt, độ phức tạp không gian sẽ là (O((K + M + N) log K)).
Hiện thực thuật toán
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 3e5 + 5;
int n, m, k;
int owner[MAXN], req[MAXN], L[MAXN], R[MAXN], A[MAXN], l[MAXN], r[MAXN];
vector<int> pos[MAXN];
struct FenwickTree {
...
} ft;
bool check(int o) {
long long cnt = 0;
for (int i : pos[o]) {
cnt += ft.get(i);
cnt = min(cnt, 1LL * req[o] + 1);
}
return cnt >= req[o];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) { cin >> owner[i];
}
for (int i = 1; i <= n; i++) { cin >> req[i];
}
cin >> k;
for (int i = 1; i <= k; i++) { cin >> L[i] >> R[i] >> A[i];
}
for (int i = 1; i <= n; i++) {
l[i] = 0, r[i] = k + 1;
}
for (int i = 1; i <= m; i++) {
pos[owner[i]].push_back(i);
}
int processing = 1;
vector<vector> queries;
while (processing) {
processing = 0;
queries.assign(k + 5, vector(0));
ft.build(m);
for (int o = 1; o <= n; o++) { if (l[o] >= r[o]) continue;
processing = 1;
queries[(l[o] + r[o]) / 2].push_back(o);
}
for (int ki = 0; ki <= k; ki++) {
if (ki) {
if (L[ki] <= R[ki]) {
ft.add(L[ki], R[ki], A[ki]);
}
else {
ft.add(L[ki], m, A[ki]);
ft.add(1, R[ki], A[ki]);
}
}
for (int o : queries[ki]) {
if (check(o)) r[o] = ki;
else l[o] = ki + 1;
}
}
queries.clear();
}
for (int o = 1; o <= n; o++) {
if (r[o] <= k) cout << r[o] << "n";
else cout << "NIEn";
}
return 0;
}
Trong đoạn mã minh họa, hàm (check(o)) thực chất được biểu diễn qua việc tính (count(o)) – tổng số mảnh đá mà tổ chức (o) thu được. Giá trị này được lấy từ cây BIT được quản lý trong hàm đệ quy (solve(s, l, r)). Hàm (solve) ban đầu được gọi ở cấp 1. Các lệnh gọi đệ quy từ hàm cấp (i) sẽ thuộc cấp (i+1). Thiết kế này đảm bảo rằng các hàm (solve) cùng cấp có thể chia sẻ trạng thái cây BIT mà không cần ‘rollback’ hay xóa dữ liệu.
Mô hình tổng quát
Bài toán Meteors chỉ là một ví dụ và có thể chưa phản ánh hết mọi khía cạnh của thuật toán. Trên thực tế, tìm kiếm nhị phân song song đôi khi được áp dụng một cách ‘ẩn’, sử dụng các nguyên lý đã phân tích nhưng với hình thức khác biệt, khiến việc đưa ra một khuôn mẫu cứng nhắc trở nên khó khăn.
Dù vậy, để giúp nhận biết các tình huống có thể áp dụng kỹ thuật này, ta có thể tạm hình dung cấu trúc tổng quát của tìm kiếm nhị phân song song như sau:
Khi nào nên sử dụng?
Tìm kiếm nhị phân song song phát huy hiệu quả khi cần thực hiện nhiều phép tìm kiếm nhị phân có cấu trúc tương tự nhau. Do đó, các bài toán phù hợp thường liên quan đến việc xử lý một loạt các truy vấn giống nhau, mà mỗi truy vấn riêng lẻ có thể được giải quyết bằng tìm kiếm nhị phân. Thêm vào đó, hàm kiểm tra (check function) trong các phép tìm kiếm nhị phân này thường phụ thuộc vào việc xử lý một tiền tố (prefix) của một chuỗi các sự kiện hoặc cập nhật đã cho.
Một dạng bài toán tiêu biểu là tìm thời điểm xảy ra sự kiện đầu tiên (sớm nhất) mà mỗi điều kiện trong một tập hợp các điều kiện cho trước được thỏa mãn.
Cấu trúc thuật toán chung
Xét một dạng bài toán tổng quát: Cho (Q) thao tác cập nhật được thực hiện tuần tự và (K) điều kiện cần kiểm tra. Với mỗi điều kiện, hãy xác định chỉ số (thời điểm) của cập nhật sớm nhất mà sau khi thực hiện xong, điều kiện đó được thỏa mãn. (Giả sử bài toán đảm bảo tính đơn điệu: một khi điều kiện được thỏa mãn tại thời điểm (t), nó sẽ luôn được thỏa mãn tại mọi thời điểm (t’ > t)).
Để hiện thực thuật toán, chúng ta cần:
- Một cấu trúc dữ liệu phù hợp để thực thi hiệu quả các thao tác cập nhật và kiểm tra điều kiện.
- Hai mảng (l) và (r), lưu trữ giới hạn dưới và giới hạn trên của khoảng chỉ số cập nhật chứa đáp án cho mỗi điều kiện.
- Một cơ chế (ví dụ: danh sách hoặc vector) để nhóm các điều kiện cần kiểm tra tại cùng một điểm giữa (mid).
Luồng thuật toán tổng quát có thể mô tả như sau:
p = 0;
update(t):
while (p < t) update_info(++p, +1);
while (p > t) update_info(p--, -1);
solve(s, l, r):
if (l == r):
for each i in s: ans[i] = l;
return;
mid = (l + r) / 2;
update(mid);
for each i in s:
if (count(i) >= require[i]):
add i to left_set;
else:
add i to right_set;
s.clear();
solve(left_set, l, mid);
solve(right_set, mid + 1, r);
Trong nhiều bài toán thực tế, tập hợp các ‘điều kiện’ không được nêu rõ ràng ngay từ đầu. Chúng ta thường cần phân tích, biến đổi bài toán gốc thành các bài toán con, và sau đó áp dụng tìm kiếm nhị phân song song để giải quyết các bài toán con này.
Ví dụ áp dụng
Hãy thử vận dụng kỹ thuật này vào bài toán Kết nối chơi game.
Trong bài toán đó, ta có thể coi ‘điều kiện thứ (i)’ (trong số (m) điều kiện) là yêu cầu: tất cả các học sinh yêu thích trò chơi thứ (i) phải thuộc cùng một thành phần liên thông (tức là có thể kết nối với nhau qua các máy tính đã được nối).
‘Cập nhật thứ (j)’ (trong số (Q) cập nhật) tương ứng với hành động: tạo một kết nối giữa máy tính của học sinh (U[j]) và học sinh (V[j]).
Như vậy, bài toán đã được đưa về dạng quen thuộc: với mỗi điều kiện (mỗi game), tìm thời điểm (chỉ số cập nhật) sớm nhất mà nó được thỏa mãn. Thuật toán giải quyết sẽ tương tự như cấu trúc chung đã trình bày ở phần trước.
