Truy vấn Bitwise OR trên khoảng [L, R] bằng C++

Cho mảng nguyên, tìm bitwise OR của tất cả số trong đoạn [L, R]. 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

Cách vét cạn

Duyệt từng phần tử trong đoạn, tích lũy OR. O(N×Q).

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);
    int queries[][2] = { { 1, 3 }, { 4, 5 } };
    int q = sizeof(queries) / sizeof(queries[0]);
    for(int i = 0; i < q; i++) {
        long ans = 0;
        for(int j = queries[i][0]; j <= queries[i][1]; j++)
            ans |= arr[j];
        cout << ans << "\n";
    }
    return 0;
}

Kết quả

7 3

Cách hiệu quả: Prefix Bit Count

Tiền xử lý số lần mỗi bit xuất hiện đến chỉ số i. Bit b xuất hiện trong đoạn [L, R] nếu count[b][R] - count[b][L-1] > 0. Khi đó set bit b trong kết quả. O(32) mỗi truy vấn ≈ O(1).

Ví dụ

#include <bits/stdc++.h>
using namespace std;
#define bitt 32
#define MAX (int)1e5
int prefixbits[bitt][MAX];

void bitcount(int *arr, int n) {
    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)) ? 1 : 0;
            prefixbits[j][i] += prefixbits[j][i - 1];
        }
    }
}

int check(int l, int r) {
    long ans = 0;
    for (int i = 0; i < 32; i++) {
        int x = (l == 0) ? prefixbits[i][r] : prefixbits[i][r] - prefixbits[i][l - 1];
        if (x != 0) ans |= (1LL << i);
    }
    return ans;
}

int main() {
    int arr[] = {7, 5, 3, 5, 2, 3};
    int n = sizeof(arr) / sizeof(int);
    bitcount(arr, n);
    int queries[][2] = {{1, 3}, {4, 5}};
    int q = sizeof(queries) / sizeof(queries[0]);
    for (int i = 0; i < q; i++)
        cout << check(queries[i][0], queries[i][1]) << "\n";
    return 0;
}

Kết quả

7 3

Giải thích

Bitwise OR của một đoạn = 1 ở bit b nếu có ít nhất một số trong đoạn có bit b = 1. Dùng prefix count kiểm tra điều kiện này O(1).

Kết luận

Giải quyết truy vấn Bitwise OR trên khoảng bằng Prefix Bit Count. Cách vét cạn O(NQ) và cách tối ưu O(N×32 + Q) kèm code C++.