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

Cho mảng nguyên, tìm bitwise AND của tất cả số trong đoạn [L, R]. Ví dụ:

Input: arr[] = {1, 3, 1, 2, 32, 3, 3, 4, 4}, q[] = {{0, 1}, {3, 5}} Output: 1 0 1 AND 3 = 1 2 AND 3 AND 4 = 0 Input: arr[] = {1, 2, 3, 4, 5, 10, 10, 12, 16, 8}, q[] = {{0, 4}, {1, 3}} Output: 0 8

Cách vét cạn

Duyệt đoạn, tích lũy AND. Khởi tạo ans với tất cả bit = 1. O(N×Q).

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int main() {
    int ARR[] = { 10, 10, 12, 16, 8 };
    int n = sizeof(ARR) / sizeof(int);
    int queries[][2] = { {0, 2}, {3, 4} };
    int q = sizeof(queries) / sizeof(queries[0]);
    for(int i = 0; i < q; i++) {
        long ans = (1LL << 32) - 1; // all bits 1
        for(int j = queries[i][0]; j <= queries[i][1]; j++)
            ans &= ARR[j];
        cout << ans << "\n";
    }
    return 0;
}

Kết quả

8 0

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

Bit b trong kết quả AND = 1 khi và chỉ khi tất cả số trong đoạn đều có bit b = 1. Tức count[b][R] - count[b][L-1] == (R - L + 1). O(32) mỗi truy vấn.

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 == r - l + 1) ans |= (1LL << i);
    }
    return ans;
}

int main() {
    int ARR[] = { 10, 10, 12, 16, 8 };
    int n = sizeof(ARR) / sizeof(int);
    memset(prefixbits, 0, sizeof(prefixbits));
    bitcount(ARR, n);
    int queries[][2] = {{0, 2}, {3, 4}};
    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ả

2 0

Giải thích

Bitwise AND giữ bit b = 1 chỉ khi mọi số trong đoạn đều có bit b = 1. Prefix count cho phép kiểm tra điều kiện này O(1).

Kết luận

Giải quyết truy vấn Bitwise AND 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++.