Cho mảng nhị phân, nhiều truy vấn: mỗi truy vấn cho chỉ số idx, trả về số lượng 0 và 1 ở bên trái (chỉ số < idx). Ví dụ:
arr = {0,1,1,1,0,0,0,1,0,0}, queries = {2,4,1,0,5} query 1 (idx=2): zeros=1, ones=1 query 2 (idx=4): zeros=1, ones=3 ...
Cách đơn giản O(N×Q)
Mỗi truy vấn duyệt từ 0 đến idx-1 đếm.
Cách hiệu quả O(N+Q): Mảng tiền tố
Xây dựng pref[i][0] = số 0 từ 0 đến i-1, pref[i][1] = số 1 từ 0 đến i-1. Trả lời truy vấn idx bằng pref[idx][0] và pref[idx][1] O(1).
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main() {
int nums[] = {1,0,0,1,1,0,0,1,0,0};
int queries[] = {2,4,1,0,5};
int n = sizeof(nums)/sizeof(nums[0]);
int pref[n][2];
int zeros = 0, ones = 0;
for (int i = 0; i < n; i++) {
pref[i][0] = zeros;
pref[i][1] = ones;
if (nums[i] == 0) zeros++; else ones++;
}
int q = sizeof(queries)/sizeof(queries[0]);
for (int i = 0; i < q; i++)
cout << "\nquery " << i+1 << ": zeros = " << pref[queries[i]][0] << ",ones =" << pref[queries[i]][1];
return 0;
}
Kết quả
query 1: zeros = 1,ones =1 query 2: zeros = 2,ones =2 query 3: zeros = 0,ones =1 query 4: zeros = 0,ones =0 query 5: zeros = 2,ones =3
Kết luận
Trả lời truy vấn số 0/1 bên trái chỉ số bằng mảng tiền tố O(N+Q). Code C++.