Trong bài này, chúng ta được cung cấp một mảng các số nguyên. Chúng tôi có nhiệm vụ tìm theo từng bit HOẶC của tất cả các số có trong phạm vi đã cho, ví dụ:
Input: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
Output:
3
7
1 OR 3 = 3
2 OR 3 OR 4 = 7
Input: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
Output:
7
7 Trong bài toán đã cho, chúng ta sẽ tiếp cận nó với cách tiếp cận brute force và sau đó kiểm tra xem nó có thể hoạt động với các ràng buộc cao hơn hay không. Nếu không, thì chúng tôi cũng sẽ tối ưu hóa cách tiếp cận của mình để làm việc cho các hạn chế cao hơn.
Phương pháp tiếp cận vũ phu
Trong cách tiếp cận này, chúng tôi chỉ đơn giản là sẽ duyệt qua từng phạm vi và tính toán OR theo từng bit của tất cả các số trong phạm vi đó và in ra câu trả lời của chúng tôi.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = { 7, 5, 3, 5, 2, 3 };
int n = sizeof(arr) / sizeof(int); // size of our array
int queries[][2] = { { 1, 3 }, { 4, 5 } }; // given queries
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for(int i = 0; i < q; i++) { // traversing through all the queries
long ans = 0;
for(int j = queries[i][0]; j <= queries[i][1]; j++) // traversing through the range
ans |= arr[j]; // calculating the answer
cout << ans << "\n";
}
return 0;
} Đầu ra
7 3
Cách tiếp cận này có độ phức tạp về thời gian là O (N * Q) trong đó N là kích thước mảng của chúng ta và Q là số lượng truy vấn hiện tại như bạn có thể thấy, độ phức tạp này sẽ không hoạt động đối với các ràng buộc cao hơn, vì vậy bây giờ chúng tôi sẽ tối ưu hóa cách tiếp cận của mình để nó cũng hoạt động cho các ràng buộc cao hơn.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng tôi sẽ tính toán số bit tiền tố, và sau đó chúng tôi sẽ kiểm tra xem một trong hai số có một bộ bit cụ thể hay không. Nếu có, thì chúng tôi đưa phần này vào câu trả lời; khác, chúng tôi để lại một chút.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
#define bitt 32
#define MAX (int)10e5
int prefixbits[bitt][MAX];
void bitcount(int *arr, int n) { // making prefix counts
for (int j = 31; j >= 0; j--) {
prefixbits[j][0] = ((arr[0] >> j) & 1);
for (int i = 1; i < n; i++) {
prefixbits[j][i] = arr[i] & (1LL << j);
prefixbits[j][i] += prefixbits[j][i - 1];
}
}
return;
}
int check(int l, int r) { // calculating the answer
long ans = 0; // to avoid overflow we are taking ans as long
for (int i = 0; i < 32; i++) {
int x;
if (l == 0)
x = prefixbits[i][r];
else
x = prefixbits[i][r] - prefixbits[i][l - 1];
if (x != 0)
ans = (ans | (1LL << i));
}
return ans;
}
int main() {
int arr[] = {7, 5, 3, 5, 2, 3};
int n = sizeof(arr) / sizeof(int); // size of our array
bitcount(arr, n);
int queries[][2] = {{1, 3}, {4, 5}}; // given queries
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for (int i = 0; i < q; i++) {
cout << check(queries[i][0], queries[i][1]) << "\n";
}
return 0;
} Đầu ra
7 3
Phương pháp này có độ phức tạp về thời gian là O (N) , trong đó N là kích thước mảng của chúng ta để cách tiếp cận này có thể hoạt động với các ràng buộc cao hơn.
Giải thích về đoạn mã trên
Trong cách tiếp cận này, chúng tôi đang tính toán số lượng bit tiền tố và lưu trữ nó. Bây giờ chúng ta tính toán một truy vấn, chúng ta đi qua số tiền tố đó và loại bỏ số bit của l-1 để chúng ta có số lượng bit trong phạm vi [l, r] bây giờ như chúng ta đã biết nếu bit được đặt trong bất kỳ số nào vì vậy nếu bạn lấy theo bitwise HOẶC với bất kỳ số nào khác, bit sẽ vẫn được đặt vì vậy bằng cách sử dụng thuộc tính này của bitwise HOẶC, chúng tôi kiểm tra xem số lượng bit không phải là 0 có nghĩa là một số có bit đặt có trong phạm vi không, vì vậy chúng tôi đặt bit đó của câu trả lời và tiếp tục qua vòng lặp và cuối cùng in câu trả lời.
Kết luận
Bài viết này giải quyết một vấn đề để tính toán Truy vấn cho từng bit HOẶC trong phạm vi chỉ số [L, R] của mảng đã cho. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.