Kỹ thuật nhị phân tổng hợp (overall binary search) là một phương pháp hiệu quả để giải quyết các bài toán yêu cầu tìm kiếm giá trị thứ k trong một phạm vi dữ liệu hoặc thực hiện nhiều truy vấn trên một tập hợp dữ liệu có khả năng thay đổi.
Hãy xem xét một bài toán đơn giản: tìm phần tử lớn thứ x trong một mảng. Cách tiếp cận trực quan là sắp xếp mảng rồi chọn phần tử ở vị trí thứ x. Một cách khác là sử dụng nhị phân. Ta chọn một giá trị mid, đếm số phần tử trong mảng nhỏ hơn hoặc bằng mid. Nếu số lượng này lớn hơn hoặc bằng x, ta tiếp tục tìm kiếm trong khoảng [l, mid]; ngược lại, tìm trong khoảng [mid+1, r].
Việc đếm số phần tử nhỏ hơn hoặc bằng mid có thể tốn thời gian nếu ta lặp lại trên toàn bộ mảng mỗi lần. Tuy nhiên, ta có thể tối ưu bằng cách chỉ xem xét các phần tử có giá trị nằm trong phạm vi hiện tại của truy vấn. Dữ liệu có thể được hỗ trợ bởi cấu trúc cây chỉ số nhị phân (Fenwick tree) hoặc chuẩn hóa phạm vi (discretization) nếu giá trị quá lớn.
Cách tiếp cận này trở nên mạnh mẽ hơn khi có nhiều truy vấn. Thay vì xử lý từng truy vấn riêng lẻ, ta có thể áp dụng nhị phân tổng hợp.
Hãy hình dung các truy vấn như những quả bóng và phạm vi giá trị có thể là câu trả lời tạo thành một hình chữ nhật. Trong mỗi bước của nhị phân tổng hợp, ta xác định giá trị mid và phân loại từng quả bóng (truy vấn) dựa trên việc câu trả lời có nằm trong khoảng [l, mid] hay [mid+1, r]. Quá trình này tương tự như việc thả những quả bóng rơi xuống các tầng dưới của hình chữ nhật cho đến khi chúng chạm đáy, nơi mà câu trả lời được xác định.
Khi có nhiều quả bóng (nhiều truy vấn), ta sẽ phân phối chúng vào các nhánh tương ứng của quá trình nhị phân. Điều quan trọng là phải đảm bảo độ phức tạp thời gian hợp lý.
Ví dụ 1: HDU 5412
Bài toán yêu cầu tìm phần tử nhỏ thứ k trong một khoảng, hỗ trợ sửa đổi điểm dữ liệu.
1 #include<cstdio>
2 int n,q,a[100001],sum[300001],ans[300001],que1[300001],que2[300001],bit[300001];
3 int I[300001],type[300001],ql[300001],qr[300001],k[300001],cnt;
4 // Thêm một mục vào hệ thống truy vấn
5 inline void ins(int t,int l,int r,int x){type[++cnt]=t,ql[cnt]=l,qr[cnt]=r,k[cnt]=x,I[cnt]=cnt;}
6 // Cập nhật cây chỉ số nhị phân tại vị trí i với giá trị x
7 inline void Ins(int i,int x){for(;i<=n;bit[i]+=x,i+=i&-i);}
8 // Truy vấn tổng từ 1 đến i trong cây chỉ số nhị phân
9 inline int Qur(int i){int Sum=0;for(;i;Sum+=bit[i],i-=i&-i);return Sum;}
10 // Hàm đệ quy nhị phân tổng hợp
11 void divide(int l,int r,int low,int upp){
12 if(l>r) return;
13 // Nếu phạm vi giá trị chỉ còn một, gán kết quả cho các truy vấn
14 if(low==upp) {for(int i=l;i<=r;++i) if(type[I[i]]==3) ans[I[i]]=low; return;}
15 int mid=low+upp>>1,cl=0,cr=0; // mid là điểm giữa của phạm vi giá trị
16 // Phân loại các truy vấn và cập nhật cây chỉ số nhị phân
17 for(int i_=l,i;i_<=r;++i_){
18 i=I[i_];
19 if(type[i]==1) {if(k[i]<=mid) Ins(ql[i],1), que1[++cl]=i; else que2[++cr]=i;} // Truy vấn loại 1: kiểm tra giá trị
20 if(type[i]==2) {if(k[i]<=mid) Ins(ql[i],-1), que1[++cl]=i; else que2[++cr]=i;} // Truy vấn loại 2: sửa đổi
21 if(type[i]==3){ // Truy vấn loại 3: tìm k-th nhỏ trong khoảng
22 int tmp=Qur(qr[i])-Qur(ql[i]-1); // Số phần tử trong khoảng [ql[i], qr[i]] nhỏ hơn hoặc bằng mid
23 if(k[i]<=sum[i]+tmp) que1[++cl]=i; // Nếu k nhỏ hơn hoặc bằng số lượng hiện tại + số phần tử mới, truy vấn thuộc về nhánh trái
24 else que2[++cr]=i, sum[i]+=tmp; // Ngược lại, thuộc về nhánh phải và cập nhật số lượng
25 }
26 }
27 // Hoàn tác các thay đổi trên cây chỉ số nhị phân
28 for(int i_=l,i;i_<=r;++i_){
29 i=I[i_];
30 if(type[i]==1) if(k[i]<=mid) Ins(ql[i],-1);
31 if(type[i]==2) if(k[i]<=mid) Ins(ql[i],1);
32 }
33 // Sắp xếp lại các truy vấn cho các bước đệ quy tiếp theo
34 for(int i=1;i<=cl;++i) I[l+i-1]=que1[i];
35 for(int i=1;i<=cr;++i) I[l+cl+i-1]=que2[i];
36 // Gọi đệ quy cho hai nửa phạm vi giá trị
37 divide(l,l+cl-1,low,mid); divide(l+cl,r,mid+1,upp);
38 }
39 int main(){
40 scanf("%d",&n);
41 // Khởi tạo mảng và thêm các phần tử ban đầu dưới dạng truy vấn loại 1
42 for(int i=1;i<=n;++i) scanf("%d",a+i), ins(1,i,i,a[i]);
43 scanf("%d",&q);
44 // Xử lý các truy vấn
45 for(int i=1,t,x,y,z;i<=q;++i){
46 scanf("%d",&t);
47 if(t==1) scanf("%d%d",&x,&y), ins(2,x,x,a[x]), ins(1,x,x,y), a[x]=y; // Sửa đổi: thêm truy vấn loại 2 và loại 1
48 else scanf("%d%d%d",&x,&y,&z), ins(3,x,y,z); // Truy vấn tìm k-th nhỏ
49 }
50 // Bắt đầu quá trình nhị phân tổng hợp
51 divide(1,cnt,1,1000000000);
52 // In kết quả cho các truy vấn tìm k-th nhỏ
53 for(int i=1;i<=cnt;++i) if(ans[i]) printf("%d\n",ans[i]);
54 return 0;
55 }
Ví dụ 2: Luogu P3332
Bài toán yêu cầu tìm phần tử lớn thứ k trong một khoảng, hỗ trợ thêm phần tử vào khoảng.
1 #include <cstdio>
2
3 typedef long long LL;
4 const int MN = 50005; // Giới hạn kích thước mảng
5
6 int N, Q; // N: kích thước mảng, Q: số lượng truy vấn
7
8 // Lưu trữ thông tin truy vấn: loại (opt), giới hạn trái (L), giới hạn phải (R), giá trị (V)
9 int opt[MN], L[MN], R[MN]; LL V[MN];
10 // P: mảng chứa chỉ số của các truy vấn, được sắp xếp lại trong quá trình nhị phân
11 int P[MN];
12 // s1, s2: các mảng tạm thời để phân loại truy vấn
13 int s1[MN], s2[MN], t1, t2;
14
15 // Sum: lưu trữ tổng các giá trị đã được xem xét cho mỗi truy vấn
16 LL Sum[MN];
17 // Ans: mảng lưu kết quả cuối cùng cho các truy vấn loại 2 (tìm k-th lớn)
18 int Ans[MN];
19
20 // b1, b2: hai cây chỉ số nhị phân để hỗ trợ tính tổng trên khoảng
21 LL b1[MN], b2[MN];
22 // Hàm cập nhật cây chỉ số nhị phân
23 inline void Add(LL *b, int i, LL x) { for(; i <= N; i += i & -i) b[i] += x; }
24 // Hàm truy vấn tổng từ 1 đến i trong cây chỉ số nhị phân
25 inline LL Qur(LL *b, int i) { LL A = 0; for(; i; i -= i & -i) A += b[i]; return A; }
26 // Hàm cập nhật khoảng [l, r] với giá trị x bằng cách sử dụng hai cây chỉ số
27 inline void Add(int l, int r, LL x) {
28 ++r; // Điều chỉnh để r là cận trên không bao gồm
29 Add(b1, l, x), Add(b2, l, (l - 1) * x); // Cập nhật điểm đầu
30 Add(b1, r, -x), Add(b2, r, -(r - 1) * x); // Cập nhật điểm cuối
31 }
32 // Hàm truy vấn tổng trên khoảng [l, r] sử dụng hai cây chỉ số
33 inline LL Qur(int l, int r) {
34 --l; // Điều chỉnh để l là cận dưới không bao gồm
35 // Công thức tính tổng trên khoảng dựa trên hai cây chỉ số
36 return r * Qur(b1, r) - Qur(b2, r) - l * Qur(b1, l) + Qur(b2, l);
37 }
38
39 // Hàm đệ quy nhị phân tổng hợp
40 void Solve(int l, int r, int lb, int rb) {
41 // Trường hợp cơ sở: phạm vi giá trị chỉ còn một phần tử
42 if (lb == rb) {
43 for (int i = l; i <= r; ++i)
44 if (opt[P[i]] == 2) // Nếu là truy vấn loại 2 (tìm k-th lớn)
45 Ans[P[i]] = lb; // Gán kết quả
46 return ;
47 }
48 int mid = lb + rb >> 1; // Tính giá trị trung vị
49 t1 = t2 = 0; // Khởi tạo lại bộ đếm cho mảng tạm thời
50 // Phân loại các truy vấn dựa trên giá trị trung vị
51 for (int i = l; i <= r; ++i) {
52 if (opt[P[i]] == 1) { // Truy vấn loại 1: thêm phần tử vào khoảng
53 if (V[P[i]] <= mid) // Nếu giá trị nhỏ hơn hoặc bằng mid
54 s1[++t1] = P[i]; // Đưa vào mảng s1 (nhánh trái)
55 else { // Nếu giá trị lớn hơn mid
56 Add(L[P[i]], R[P[i]], 1); // Cập nhật cây chỉ số để đếm các phần tử trong khoảng
57 s2[++t2] = P[i]; // Đưa vào mảng s2 (nhánh phải)
58 }
59 }
60 else { // Truy vấn loại 2: tìm k-th lớn trong khoảng
61 // Tính tổng số phần tử trong khoảng hiện tại cộng với các phần tử đã thêm
62 LL num = Sum[P[i]] + Qur(L[P[i]], R[P[i]]);
63 if (num >= V[P[i]]) // Nếu tổng đủ lớn để chứa k-th lớn
64 s2[++t2] = P[i]; // Đưa vào mảng s2 (nhánh phải)
65 else { // Nếu tổng chưa đủ
66 Sum[P[i]] = num; // Cập nhật tổng đã xem xét
67 s1[++t1] = P[i]; // Đưa vào mảng s1 (nhánh trái)
68 }
69 }
70 }
71 // Hoàn tác các thay đổi trên cây chỉ số nhị phân cho các phần tử lớn hơn mid
72 for (int i = l; i <= r; ++i) {
73 if (opt[P[i]] == 2) continue; // Bỏ qua truy vấn loại 2
74 if (V[P[i]] > mid)
75 Add(L[P[i]], R[P[i]], -1); // Hoàn tác cập nhật
76 }
77 // Sắp xếp lại mảng P dựa trên sự phân loại vào s1 và s2
78 int pos = l;
79 for (int i = 1; i <= t1; ++i)
80 P[pos++] = s1[i];
81 for (int i = 1; i <= t2; ++i)
82 P[pos++] = s2[i];
83 int M = l + t1 - 1; // Vị trí phân chia
84 // Gọi đệ quy cho hai nửa phạm vi giá trị
85 Solve(l, M, lb, mid);
86 Solve(M + 1, r, mid + 1, rb);
87 }
88
89 int main() {
90 scanf("%d%d", &N, &Q);
91 // Đọc dữ liệu truy vấn
92 for (int i = 1; i <= Q; ++i) {
93 scanf("%d%d%d%lld", opt + i, L + i, R + i, V + i);
94 P[i] = i; // Khởi tạo mảng P với thứ tự truy vấn ban đầu
95 }
96 // Bắt đầu quá trình nhị phân tổng hợp với phạm vi giá trị từ -N đến N
97 Solve(1, Q, -N, N);
98 // In kết quả cho các truy vấn loại 2
99 for (int i = 1; i <= Q; ++i) {
100 if (opt[i] == 1) continue; // Bỏ qua truy vấn loại 1
101 printf("%d\n", Ans[i]);
102 }
103 return 0;
104 }